Choosing a step size

One parameter, one objective f(x) = 2x², three step sizes. Start at x = 1 and apply the update of the previous section; the gradient of 2x² is 4x, so one step replaces x by x − η(4x) = (1 − 4η)x, and a single number predicts the entire trajectory. Each row of the table below evaluates that factor for a different step size, and the rows cover the three regimes a one-knob quadratic can show.

!Three runs of the update $x\leftarrow (1-4\eta )x$ from $x=1$ on $f(x)=2x^2$. At $\eta =0.1$ the setting falls by a factor 0.6 each step; at $\eta =0.25$ one step lands on the minimum; at $\eta =0.6$ the sign alternates and the distance grows by 1.4 each step, reaching $-2.744$ after three. Right: the multiplier $1-4\eta$ stays inside $\pm 1$ exactly for $0<\eta <0.5$, the interval bounded by $2/L$ with $L=4$. The figure is schematic. Status: schematic.

The first row progresses slowly: it still moves, but it removes only 40 per cent of the distance at each iteration. The second row reaches the minimum in one step and remains there. The third row overshoots, reverses sign, and amplifies: after three iterations it sits farther from zero than it began, and its objective is 15.06 against the initial 2. The objective and the starting point are the same in every row, so each difference between them comes from the multiplier alone.

The learning rate is the number η, the multiplier on the gradient, and it is the one setting every gradient procedure must select. An insufficient step produces slow progress; an excessive step fails to converge, or diverges outright [S:27:235-235]. The table demonstrates both extremes in one dimension: a modest step yields a modest improvement, while an excessive step yields a growing oscillation.

The boundary is determined by curvature. Write L for the largest curvature of the objective, the maximal rate at which the gradient can change. On a one-parameter quadratic the gradient at distance x from the minimum is exactly Lx, because the derivative of ½Lx² is Lx, so substituting it into the update gives

$$x_{t+1}=(1-\eta L)x_t,$$

and the distance from the minimum is multiplied by the same factor at every iteration. A geometric sequence tends to zero exactly when its ratio has modulus below one, and that factor has absolute value below one precisely when η is below 2/L. For the table L = 4, the second derivative of 2x², so the interval is 0 < η < 0.5, the middle row sits at η = 1/L = 0.25, and the last row lies outside the interval. [F01]

Worked example: the table cannot show the fourth regime, a little inside the edge. At η = 0.49 the factor is 1 − 4(0.49) = −0.96. The distance from zero falls by 4 per cent at every iteration while its sign flips, so the run converges by zigzagging. Each entry in the table is a power of 1 − 4η: at η = 0.1 the factor is 0.6, and at η = 0.6 it is −1.4.

The verbal rule follows from the factor. A step below 1/L is cautious, a step at 1/L arrives at the minimum of a one-knob quadratic, and a step between 1/L and 2/L approaches while oscillating. At exactly 2/L the factor is −1 and the trajectory alternates between two points indefinitely. Above 2/L the distance grows without bound [S:63:314-314].

The interval is exact only for a quadratic. On a curved objective the curvature changes along the trajectory, so a step that is safe at the commencement can be excessive later. A long thin valley is poorly conditioned, with curvatures spread over a wide range, and makes the procedure zigzag [S:63:316-316]. The boundary 2/L also requires L, which the machine rarely knows in advance [S:63:315-315]. The practical response is to measure the curvature or to search along the step, and the next section supplies the inequality that makes a search provable.

The formal statement. Take one knob and the quadratic $f(x)=\frac{L}{2}{x}^2$ with $L>0$, whose gradient is $Lx$. Run $x_{t+1}=x_t-\eta L{x}_t$ from any start. Then $x_t=(1-\eta L{)}^t{x}_0$ at every step, and $x_t\to 0$ for every start exactly when $0<\eta <2/L$. The hypotheses are a quadratic with positive curvature $L$, a constant step $\eta$, and exact arithmetic.

The derivation. Substitute the gradient into the update: $x_{t+1}=x_t-\eta L{x}_t=(1-\eta L)x_t$. The factor does not depend on $x_t$, so induction gives the power. A geometric sequence tends to zero exactly when its ratio has modulus below one, and $|1-\eta L|<1$ is two inequalities. The right one, $1-\eta L<1$, holds for every positive $\eta$. The left one, $1-\eta L>-1$, gives $\eta <2/L$. So the window has a finite top and no positive bottom, and its top comes from overshoot rather than from slowness. At $\eta =2/L$ the factor is $-1$, and the run alternates between $x_0$ and $-x_0$ forever.

The edge case. With several knobs the factor stops being one number. On $f(\theta )=\frac{1}{2}{\theta }^{\top }H\theta$ the error obeys $e_{t+1}=(I-\eta H)e_t$, so along the eigenvector with curvature ${\lambda }_i$ the error is multiplied by $1-\eta {\lambda }_i$. A step of $1/L$ sets the factor for the largest curvature to zero and leaves every other factor alone. The rule that $1/L$ lands on the bottom is therefore a one-knob fact: it holds because in one dimension there is only one curvature to match. In $d$ dimensions, with $m$ the smallest curvature, the slowest factor is $1-m/L$, and Bach states the consequence plainly: the smallest eigenvalue sets the rate for all of them [S:77:131-131].

Bach also computes the constant step that is best in the worst case over the whole spectrum, and the factor for $1/L$ is slightly larger than the best one [S:77:130-130]. The core's choice is the right first answer and not the best one. The difference is visible only when the curvatures are spread, which the one-knob table cannot show.

What the core hid. The core used the table to display three regimes and then stated the window as a property of the curvature. It hid the fact that the top of the window is a stability boundary, not a performance boundary. Below $2/L$ every run converges, and how fast it converges depends on the smallest curvature. The one-knob example cannot show that, because there the smallest and largest curvatures are the same number. The core also hid where $L$ comes from: the window is exact only if you know the curvature, and section 17.3 replaces that knowledge with a bound.

Original sources. Murphy states the quadratic boundary as an if-and-only-if for steepest descent, with the largest eigenvalue in the denominator, and then gives the general smooth condition $\eta <2/L$ [S:63:314-315]. Bach derives the same conclusion in the form that every step below $2/L$ gives exponential convergence [S:77:130-130]. The line-search alternative has its own account: Murphy gives the exact step for a quadratic and the Armijo test for everything else [S:63:315-316], and Boyd and Vandenberghe prove that backtracking terminates [S:44:478-479].

An open question. The window needs $L$, and a training run rarely has it. The field has not settled how to pick a step when the curvature is unknown and a line search is too expensive. The heuristics in the corpus are local: undo a step that raised the loss and shrink it, or raise it when the loss fell [S:27:235-235]. Deisenroth and coauthors prove that the undo rule gives monotonic convergence [S:27:236-236], which is a guarantee about not getting worse rather than about speed. Evidence that would settle a proposal: a sweep over problems with different spectra, an online estimate of $L$ with its cost counted, and a measured step count that matches the $1/L$ count.

A frontier result. AdaGrad removes the single step and gives each coordinate its own. It accumulates squared gradients and divides by their square root [S:69:561-562], so the effective rate falls like $t^{-1/2}$ and no global $L$ is needed [S:69:562-562]. That rate is the one section 17.6 rejects: a per-coordinate step whose size decays like $t^{-1/2}$ has a divergent sum of squares, so AdaGrad is not an instance of the schedule class that section proves. Its guarantee comes from its own analysis, not from the Robbins–Monro series, which are sufficient for that proof and not necessary [S:46:28-28]. The method is still the reason a sparse feature can take a large step while a dense one takes a small step.

What to read next. Read Murphy section 8.2.2 for the boundary and the Armijo test [S:63:314-316]. Read Boyd and Vandenberghe section 9.2 for backtracking and its termination proof [S:44:478-479]. Read Bach section 5.2.1 for the best constant step over a known spectrum [S:77:130-130]. Then read the AdaGrad section of Dive into Deep Learning for the per-coordinate step [S:69:561-562].