Learning Rates and Convergence

Gradient descent updates parameters by

where $f$ is the objective (loss) function and $\eta > 0$ is the learning rate (also called the step size). At each iteration the algorithm moves opposite to the gradient — the direction of steepest local increase — scaled by $\eta$. The gradient tells you which direction to move; the learning rate tells you how far. This decoupling is exactly why the learning rate is such a delicate quantity: the gradient direction is determined by the geometry of $f$, but the step length is a free choice that must be matched to that geometry to behave well. Two properties of $f$ control what "matched" means. Smoothness: $f$ is $L$-smooth if its gradient is $L$-Lipschitz, $\|\nabla f(x) - \nabla f(y)\| \le L\|x-y\|$, which bounds how fast the gradient can change and hence how curved $f$ can be. Strong convexity: $f$ is $\mu$-strongly convex if $f(x) - \frac{\mu}{2}\|x\|^2$ is convex, which lower-bounds curvature and guarantees a unique minimizer. Together $L$ and $\mu$ define the condition number $\kappa = L/\mu \ge 1$, the single number that most tightly controls how hard an objective is to optimize with a fixed-step method. A learning rate schedule is a rule $\eta_k$ that may change over iterations $k$, rather than a single fixed constant. Schedules exist because the optimal constant rate for fast initial progress is often too aggressive for fine convergence near the minimum, and vice versa; varying $\eta_k$ lets an optimizer be aggressive early and cautious late, which is the guiding principle behind step decay, exponential decay, cosine annealing, and warmup schedules used throughout deep learning.

The mechanism has two layers: the descent step itself (unchanged from plain Gradient Descent), and the rule that produces $\eta_k$ at each iteration. The pseudocode below implements full-batch gradient descent with a general schedule, plus an optional backtracking line search that adaptively certifies a safe step size at every iteration — a concrete algorithm for turning the theory below into a robust implementation. ``` function GRADIENT_DESCENT(f, grad_f, theta_0, schedule, max_iters, tol): theta = theta_0 for k = 0, 1, 2, ..., max_iters - 1: g = grad_f(theta) if norm(g) < tol: return theta # converged: near-stationary point eta_k = schedule(k, theta, g, f) # constant / decaying / line-search theta = theta - eta_k g return theta function CONSTANT_SCHEDULE(eta): return function(k, theta, g, f): return eta function STEP_DECAY_SCHEDULE(eta0, drop, every): return function(k, theta, g, f): return eta0 drop^floor(k / every) function EXPONENTIAL_DECAY_SCHEDULE(eta0, rate): return function(k, theta, g, f): return eta0 exp(-rate k) function BACKTRACKING_LINE_SEARCH(eta_init, shrink, c): return function(k, theta, g, f): eta = eta_init while f(theta - eta g) > f(theta) - c eta dot(g, g): eta = eta shrink # Armijo sufficient-decrease condition return eta ```

Step-by-step reading of the algorithm: 1. Gradient evaluation. Compute $g_k = \nabla f(\theta_k)$; this is the same cost as in plain gradient descent and does not depend on the schedule. 2. Stopping check. If $\|g_k\|$ is below tolerance, $\theta_k$ is (approximately) a stationary point and the loop terminates — this is the correctness base case. 3. Schedule evaluation. The schedule function decides $\eta_k$. A constant schedule ignores $k$; decaying schedules shrink $\eta_k \to 0$ over time; the line-search schedule tests candidate step sizes against the Armijo condition

which certifies that the step produces at least a fraction $c$ of the decrease predicted by the local linear (first-order Taylor) approximation. 4. Update. Apply $\theta_{k+1} = \theta_k - \eta_k g_k$. 5. Repeat until convergence or the iteration budget is exhausted. Backtracking line search is the practical bridge between theory and practice: instead of hand-picking a single global $\eta$, it re-derives a locally safe step size at every iteration by directly testing the sufficient-decrease condition, at the cost of extra function evaluations per step.

Per-iteration cost. Each plain gradient-descent step costs $O(d)$ arithmetic beyond the gradient computation itself, where $d$ is the parameter dimension (the update is a vector subtraction and scalar multiply). The dominant cost is computing $\nabla f(\theta_k)$, which for a dataset of $n$ points is typically $O(nd)$ for full-batch gradients — the schedule computation itself (constant, step decay, exponential decay) is $O(1)$ per step. Backtracking line search adds $O(t \cdot \text{cost of } f)$ per outer iteration, where $t$ is the number of shrink attempts, each costing one function evaluation.

Convergence rate — smooth convex case. Suppose $f$ is convex and $L$-smooth. A standard descent lemma states that for any $\eta \le 1/L$,

Derivation sketch: $L$-smoothness gives the quadratic upper bound $f(y) \le f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$. Substituting $y = x - \eta \nabla f(x)$ yields $f(\theta_{k+1}) \le f(\theta_k) - \eta\|\nabla f(\theta_k)\|^2 + \frac{L\eta^2}{2}\|\nabla f(\theta_k)\|^2$, and choosing $\eta \le 1/L$ makes the coefficient of $\|\nabla f(\theta_k)\|^2$ at most $-\eta/2$, so the loss is monotonically non-increasing. This is exactly why $\eta < 2/L$ is the divergence boundary: past $2/L$ the coefficient flips positive and the bound no longer guarantees decrease. Summing this inequality over $k$ steps and using convexity (which relates gradient norm to suboptimality) gives the classical rate

with the optimal constant choice $\eta = 1/L$. This is a sublinear rate: to halve the error you need roughly to double the iteration count.

Convergence rate — strongly convex case. If in addition $f$ is $\mu$-strongly convex, choosing $\eta = 1/L$ gives the sharper, linear (geometric) rate

where $\kappa = L/\mu$ is the condition number. This means error shrinks by a constant multiplicative factor each iteration — exponentially fast in $k$ — but the factor $(1-1/\kappa)$ approaches 1 as $\kappa$ grows, so ill-conditioned problems (large $\kappa$) converge arbitrarily slowly even though the rate is technically linear. This is the precise mathematical reason poorly scaled features or highly elongated loss bowls make training slow.

Divergence for $\eta > 2/L$. For the simplest case $f(\theta) = \frac{L}{2}\theta^2$ (a pure quadratic with curvature $L$), gradient descent gives $\theta_{k+1} = (1 - \eta L)\theta_k$, so $\theta_k = (1-\eta L)^k \theta_0$. This converges to 0 iff $|1 - \eta L| < 1$, i.e. iff $0 < \eta < 2/L$; at $\eta = 2/L$ the iterates oscillate with constant magnitude, and for $\eta > 2/L$, $|1 - \eta L| > 1$ and $|\theta_k| \to \infty$ geometrically. This single closed-form example is the rigorous backbone behind the informal claim "too large a learning rate causes divergence" — it is not a heuristic, it is provable exactly.

Tradeoffs. Constant $\eta = 1/L$ guarantees stability but only sublinear convergence for merely convex objectives, and requires knowing (or estimating) $L$, which is often unavailable in practice for nonconvex deep networks. Decaying schedules trade a slower theoretical worst-case rate for empirical robustness to a misestimated $L$. Line search removes the need to know $L$ at all but pays extra function evaluations per step — a real cost when $f$ is expensive, as in large-batch training.

Take the 1-D quadratic $f(\theta) = \theta^2$, so $f'(\theta) = 2\theta$, minimum at $\theta^* = 0$, and $L = 2$ (the Lipschitz constant of $f'$). The threshold for guaranteed non-divergence is $\eta < 2/L = 1$. Start at $\theta_0 = 5$.

For $\eta = 1.1 > 1 = 2/L$: since $1 - \eta L = 1 - 2.2 = -1.2$, we get $\theta_k = 5(-1.2)^k$, whose magnitude grows without bound — this is provable divergence, not slow convergence, matching exactly the closed-form analysis above. For $\eta = 0.5 = 1/L$, $1 - \eta L = 0$, so the iterate reaches the exact minimum in a single step — the theoretically optimal rate for this perfectly conditioned quadratic. For $\eta = 0.1$, convergence is geometric but slow, shrinking by a factor of $0.8$ each step; it takes about $k \approx 30$ steps to reach $\theta_k < 0.01$, versus one step at the optimal rate. For $\eta = 0.9$, the iterate oscillates in sign but still shrinks in magnitude by a factor of $0.8$ per step, since $|1 - 0.9 \times 2| = 0.8$ — oscillation alone does not imply divergence, only $|1-\eta L| > 1$ does. This table demonstrates all three qualitative regimes predicted by the theory: monotone slow convergence, one-shot optimal convergence, oscillatory-but-convergent behavior, and true divergence — from a single formula $\theta_k = (1-\eta L)^k \theta_0$, exactly as derived in the Complexity & correctness section.

Cauchy's original steepest-descent method used a fixed, hand-chosen step and could diverge or crawl exactly as shown above; it took over a century of convex analysis — culminating in the smoothness- and strong-convexity-based bounds used today — to turn "try a step and see" into a provable theory of step-size selection. The condition-number-dependent linear rate derived in this article is the direct descendant of that analysis, and it directly motivates why later methods reweight or precondition gradients, foreshadowing both Stochastic Gradient Descent and Momentum Methods.

Learning-rate schedules are load-bearing infrastructure in essentially every production machine learning system. Deep learning frameworks such as PyTorch and TensorFlow ship dozens of built-in schedulers (step decay, cosine annealing, exponential decay, one-cycle) precisely because no single constant rate works across model scales. Large language model training runs use carefully tuned warmup-then-decay schedules — a short initial phase with small $\eta$ to avoid destabilizing randomly initialized weights, followed by cosine or linear decay to fine-tune late in training. Learning-rate finders (used in fastai and elsewhere) automate the search for a good constant rate by scanning $\eta$ over orders of magnitude and plotting the resulting loss curve. Recommendation systems, reinforcement learning agents, and classical convex solvers (logistic regression, SVMs, LASSO) all rely on the same smoothness/strong-convexity theory to choose safe step sizes or line-search parameters. The condition-number argument also explains why feature normalization and batch normalization are so effective in practice: they directly reduce $\kappa$, letting a single learning rate work well across all parameter directions.

Ask the tutor: How does mini-batch noise in stochastic gradient descent change the safe range for the learning rate compared to full-batch gradient descent?