Gradient Descent

Consider a differentiable function $f: \mathbb{R}^n \to \mathbb{R}$ that we want to minimize — in machine learning, $f$ is typically an empirical loss function of model parameters $x \in \mathbb{R}^n$ averaged over a training set. The gradient $\nabla f(x)$ is the vector of partial derivatives, and it points in the direction of steepest increase of $f$ at $x$. It follows immediately that $-\nabla f(x)$ points in the direction of steepest decrease, which is the entire justification for the algorithm's core move.

Gradient descent is the iterative scheme

where $\eta > 0$ is the learning rate (or step size), and $t = 0, 1, 2, \dots$ indexes iterations starting from some initial guess $x_0$. In the specific case called batch gradient descent, when $f(x) = \frac{1}{m}\sum_{i=1}^{m} f_i(x)$ is an average loss over $m$ training examples, the gradient $\nabla f(x_t) = \frac{1}{m}\sum_i \nabla f_i(x_t)$ is computed using all $m$ examples at every single step. This is what distinguishes it from Stochastic Gradient Descent, which approximates the same gradient using a single example or small mini-batch, trading accuracy for speed. The algorithm's correctness on convex problems rests on a key fact from Convex Functions and Convex Sets: for a convex differentiable function, every point where $\nabla f(x) = 0$ is a global minimizer, not merely a local one. This means gradient descent's stopping criterion — a vanishing gradient — is exactly the right signal to chase, with no risk of settling into a spurious local trap. The rate at which the algorithm approaches this minimizer depends on two further structural properties: smoothness (a bound on how fast the gradient itself can change, formalized via a Lipschitz constant $L$) and, optionally, strong convexity (a lower-curvature bound $\mu$). These two constants govern the choice of learning rate and the resulting convergence rate, discussed in full below.

The mechanism is deliberately simple: evaluate the gradient, take a scaled step against it, check for convergence, repeat. The entire complexity of applying gradient descent well lies in choosing $\eta$ and in evaluating $\nabla f$ efficiently, not in the control flow itself. ``` Algorithm: Batch Gradient Descent Input: differentiable convex objective f, learning rate η, initial point x0, tolerance ε, max iterations T_max Output: approximate minimizer x 1. x ← x0 2. for t = 0, 1, 2, ..., T_max - 1: 3. g ← ∇f(x) # full-batch gradient: average over ALL training points 4. if ‖g‖ < ε: 5. return x # gradient ~0 ⇒ (near) global minimum, by convexity 6. x ← x - η g # step against steepest ascent direction 7. return x # ran out of iterations; may not have fully converged ``` For a supervised learning loss $f(x) = \frac{1}{m}\sum_{i=1}^m \ell(x; a_i, b_i)$ over data pairs $(a_i, b_i)$, line 3 expands into a full pass over the dataset: ``` Compute full-batch gradient: 1. g ← 0-vector of length n 2. for i = 1 to m: 3. g ← g + ∇_x ℓ(x; a_i, b_i) 4. g ← g / m 5. return g ``` Two practical refinements are worth stating precisely, because they anticipate later material without changing the core idea: 1. Fixed vs. decaying step size. A constant $\eta$ suffices for convergence guarantees on smooth convex functions, but many implementations decay $\eta_t$ over time (e.g., $\eta_t = \eta_0 / \sqrt{t}$) to squeeze out faster practical convergence, foreshadowing the deeper analysis in Learning Rates and Convergence. 2. Convergence check. In practice, stopping is triggered by $\|\nabla f(x_t)\| < \varepsilon$, by a small relative change in $f$, or simply by a fixed iteration budget — the pseudocode above shows the gradient-norm criterion because it connects directly to the optimality condition of convex functions.

Per-iteration cost. For batch gradient descent on $m$ training examples with $n$ parameters, computing the full gradient costs $O(mn)$ time in the typical case where each per-example gradient $\nabla_x \ell(x; a_i, b_i)$ costs $O(n)$ (e.g., linear models) — more generally $O(m \cdot C)$ where $C$ is the cost of one example's gradient. Space is $O(n)$ for storing $x$ and $g$, plus $O(mn)$ if the dataset itself must reside in memory (often unavoidable regardless of the optimizer). This per-step cost is the central practical drawback of the batch method: every single update requires a full pass over the data, which is why Stochastic Gradient Descent exists — it estimates the same gradient direction from a subsample at a fraction of the cost per step.

Number of iterations to reach accuracy $\epsilon$. This is where convexity and smoothness earn their keep. Assume:

• $f$ is convex and differentiable.
• $f$ is $L$-smooth: $\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|$ for all $x, y$ (the gradient doesn't change too fast).
• A global minimizer $x^*$ exists with $f^* = f(x^*)$.

Claim (convex, smooth case). With fixed step size $\eta = 1/L$, gradient descent satisfies

Proof sketch. $L$-smoothness gives the quadratic upper bound (the descent lemma):

Substituting $y = x_{t+1} = x_t - \eta \nabla f(x_t)$ and using $\eta = 1/L$:

So the objective is guaranteed to strictly decrease at every step (this is the descent property, the invariant underlying correctness). Convexity gives the supporting-hyperplane inequality $f(x_t) \le f^* + \nabla f(x_t)^\top(x_t - x^*)$, which after algebraic manipulation with the previous bound produces a telescoping sum:

Since $f(x_t)$ is non-increasing (from the descent property), the minimum term $f(x_T) - f^*$ is at most the average of the sum, giving the stated $O(1/T)$ rate. $\blacksquare$

Claim (strongly convex case). If additionally $f$ is $\mu$-strongly convex ($f(y) \ge f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2$), then with $\eta = 1/L$,

a linear (geometric) convergence rate — exponentially fast in $T$, governed by the condition number $\kappa = L/\mu$. Smaller $\kappa$ (well-conditioned problems) means faster convergence; this is the theoretical seed for why Momentum Methods and adaptive preconditioning matter, since they effectively reduce the effective condition number the algorithm experiences.

Honest tradeoffs.

• The $O(1/T)$ and linear rates require knowing or bounding $L$ (or $\mu$); in practice $\eta$ is tuned empirically or found via line search.
• Convexity is essential to correctness: on non-convex losses (e.g., deep networks), gradient descent still decreases $f$ under the same smoothness argument, but it can only be shown to converge to a stationary point ($\|\nabla f\| \to 0$), which may be a saddle point or local minimum, not the global one.
• Batch gradient descent's per-step cost of $O(mn)$ makes it unattractive for large $m$ — this is precisely the gap Stochastic Gradient Descent closes at the cost of noisier updates and a slower, sublinear-in-expectation convergence guarantee even under strong convexity.

Take the simple convex quadratic $f(x) = \frac{1}{2} m^{-1}\sum_{i=1}^m (x - a_i)^2$ — batch gradient descent on the mean-squared-error objective for estimating a single scalar parameter $x$ from data. Let the (tiny) training set be $a = \{1, 3, 8\}$, so $m = 3$. The objective is $f(x) = \frac{1}{6}\left[(x-1)^2 + (x-3)^2 + (x-8)^2\right]$, with

This is $L$-smooth with $L = 1$ (the second derivative is constant at 1) and strongly convex with $\mu = 1$, so $\kappa = 1$ — a perfectly conditioned 1-D problem. The true minimum is at $x^* = 4$ (the mean of the data), with $f^* = f(4) = \frac{1}{6}(9 + 1 + 16) = \frac{26}{6} \approx 4.333$. Using $\eta = 1/L = 1$ and starting at $x_0 = 10$:

With the theoretically optimal step size for this well-conditioned quadratic, gradient descent reaches the exact minimum in a single step — consistent with the linear-convergence bound, since $\kappa = 1$ implies $(1 - \mu/L)^T = 0$ for $T \ge 1$. Now watch what happens with a poorly chosen learning rate, $\eta = 2.5$ (exceeding $2/L = 2$, the classical stability threshold for quadratics):

The iterate oscillates with growing amplitude and diverges — $f(x_t)$ is increasing, violating the descent property, exactly because $\eta > 2/L$ breaks the smoothness-based inequality used in the proof. This trace demonstrates concretely why the choice of $\eta$ relative to $L$ is not a minor tuning detail but the entire hinge on which the correctness proof depends.

Gradient-based iterative minimization traces back to 19th-century numerical analysis, long before "machine learning" existed as a field, and was later absorbed wholesale into optimization theory and then into learning algorithms.

Gradient descent and its variants form the optimization backbone of essentially every trainable model in modern machine learning. Linear and logistic regression, support vector machines with smooth surrogate losses, and generalized linear models are commonly fit with batch or mini-batch gradient descent when closed-form solutions are unavailable or too costly for high-dimensional data. Every major deep learning framework — PyTorch, TensorFlow, JAX — implements gradient descent as the base case from which stochastic and adaptive optimizers (SGD with momentum, Adam, RMSProp) are built, all sharing the same core update rule analyzed here. Recommendation systems, computer vision pipelines, and large language model pretraining all reduce, at the lowest level, to variants of this single iterative rule applied at massive scale with mini-batches replacing full-batch gradients. Convex optimization solvers used in operations research, control theory, and statistics (e.g., ridge regression, Lasso via proximal gradient methods) also rely on the exact convergence theory developed for convex smooth objectives here, extended with proximal or projected variants for constrained and non-smooth cases.

Ask the tutor: How does adding momentum change the convergence guarantees of gradient descent on ill-conditioned convex problems?