Schedules and batch size

The schedule 1, 1/2, 1/3, 1/4 and so on possesses a curious property: its terms shrink to zero, yet their sum diverges, and the partial sums grow without bound. The sum of the squares converges, approaching a finite limit; the first ten terms add to 2.929, and the first thousand add to 7.485. The first ten squares add to 1.550, and the complete infinite series adds to 1.645.

A learning-rate schedule is a rule that specifies the step at each iteration instead of holding it fixed [S:63:314-314]. A fixed step possesses the problem of the previous section: it settles at a noise floor. A schedule that shrinks can descend lower, because the floor is proportional to the step, but it must not shrink too rapidly, or the procedure ceases moving before it arrives. !Running totals for three schedules, on a logarithmic iteration axis. Left: the total travel $\sum {\eta }_t$. The schedule $1/t^2$ levels off at ${\pi }^2/6\approx 1.645$, so a run starting farther than that can never arrive; $1/t$ reaches 7.485 after a thousand steps; $1/\sqrt{t}$ grows faster and leaves the frame. Right: the total squared step $\sum {\eta }_t^2$, the noise budget. The squares of $1/\sqrt{t}$ keep growing, so its noise never averages away, while those of $1/t$ and $1/t^2$ stay below 1.645. Only $1/t$ passes both tests. The figure is schematic. Status: schematic.

The two requirements are the conditions a schedule must satisfy for the convergence proof to proceed [S:46:28-28]; write t for the iteration number and η_t for the step at that number.

$$\sum _{t=1}^{\infty }{\eta }_t=\infty ,\sum _{t=1}^{\infty }{\eta }_t^2<\infty .$$

That line says: the steps must add up to unlimited total size, while their squares must add up to a finite quantity of noise. The summation symbol with an upper limit of infinity means the limit of the finite sums as more terms are added. [F01]

The first sum is the total budget of step sizes; if it is finite, the multipliers run out of total size, and with a bounded gradient the run can travel only a bounded distance. The second sum is the total noise the procedure admits; each squared step weighs that step's noise, and if the sum of squares is infinite, the noise never averages away. The schedule 1/t satisfies both conditions, whereas 1/t² fails the first and 1/√t fails the second.

The failure of 1/t² is visible in numbers. Its total is π²/6, approximately 1.645, so a procedure whose gradient never exceeds one in length, and which starts farther than that from the answer, can never arrive, however long it continues. The reason is the rate of shrinkage. The terms of 1/t² fall like the square of the index, and the sum of such terms is finite, while the terms of 1/√t fall more slowly than those of the already divergent 1/t. The failure of 1/√t is slower in appearance: at iteration 10,000 its value is 0.01, while 1/t at the same iteration is 0.0001, so the square-root schedule is still stepping a hundred times harder, and the noise it admits never settles.

The same contrast appears in the batch. The schedule controls the noise by shrinking the step, and the batch controls it by averaging. The two are partial substitutes: enlarging the batch reduces the noise without slowing the procedure, and it is sometimes employed in place of a decaying step [S:46:30-31].

Worked example: for η_t = 1/t the first ten steps add to 1 + 1/2 + … + 1/10 = 2.929, and the first thousand add to 7.485. The sums of squares are 1.550 and 1.645, and the second is the limit π²/6: it never exceeds 1.645, however long the run. So the total of the step sizes is unlimited, while the noise the run admits has a fixed budget.

A schedule that halves the step behaves in a related manner. Each halving lowers the floor but slows the contraction, and the analysis states that the step must be maintained for twice as long after each halving [S:46:28-29]. Three halvings therefore cost 1 + 2 + 4 = 7 units of time to purchase a factor of eight in accuracy.

Batch size is the other knob: doubling the batch halves the variance, so it halves the guaranteed gap and shrinks the radius of the ball by √2 at twice the cost per iteration. For a fixed step, the number of iterations required to reach the ball is determined by the curvature, not by the batch, so the total work to a given gap is approximately the same either way [S:46:31-31]. Batch size is therefore selected by what the hardware performs well, not by a theorem about accuracy [S:46:31-32].

A schedule is also a statement about what you will report: with a fixed step the final iterate is a sample from the ball, so printing it quotes the noise as if it were the answer. With a schedule that satisfies the two conditions the ball contracts and the iterate converges to the minimum [S:46:29-29]. The difference determines whether the number at the end is an answer or a sample.

The conditions are a test, not a recipe: they indicate which schedules can work, not which one is fastest, and every constant in the analysis is unknown in practice [S:44:477-477]. A schedule that satisfies both tests can still be far too slow, and a schedule that fails them can appear satisfactory for a short run. The conditions remove the schedules that cannot work; they do not rank the ones that can, so a comparison at a fixed budget is the only way to choose.

The formal statement. Suppose $f$ is $L$-smooth and $m$-strongly convex, and each stochastic gradient is unbiased with variance at most ${\sigma }^2$. With step ${\eta }_k\le 1/L$ at step $k$, the expected gap obeys

$$\mathbb{E}[f({\theta }_K)]-f({\theta }^{\ast })\le \prod _{k=1}^K(1-{\eta }_{k}m)[f({\theta }_0)-f({\theta }^{\ast })]+\frac{L{\sigma }^2}{2}\sum _{k=1}^K{\eta }_k^2\prod _{j=k+1}^K(1-{\eta }_{j}m).$$

The display says that the gap is the starting gap shrunk by a product, plus a noise term in which each squared step is weighted by the product of all the contraction factors that follow it. If the steps sum to infinity and their squares sum to a finite total, both terms vanish, so the gap tends to zero [S:46:28-28]. Those two series are the Robbins and Monro conditions.

The derivation. Start from the one-step recursion $\mathbb{E}[f({\theta }_{k+1})]-f({\theta }^{\ast })\le (1-{\eta }_{k}m)[f({\theta }_k)-f({\theta }^{\ast })]+{\eta }_k^{2}L{\sigma }^2/2$ [S:46:29-29]. Apply it $K$ times and collect terms. Each squared step is multiplied by the products of the contractions that come after it, not left bare. Split the noise sum at half the run. For the early steps the product of later contractions is at most $\exp (-m{\sum }_{j=K/2}^K{\eta }_j)$, which tends to zero because the steps sum to infinity, and the whole squared-step total is bounded. For the late steps the products are at most one, and the tail of the squared-step sum tends to zero because that sum is finite. So the noise term vanishes. The logarithm of the first product is at most $-m\sum {\eta }_k$, which tends to minus infinity when the steps sum to infinity. That is the whole argument, and it omits no step.

The two conditions pull in opposite directions. The first asks for enough total travel. The second asks for a finite total of squared steps, which is the total noise the run admits. The schedule $1/t$ satisfies both. The schedule $1/t^2$ has a finite sum, so the schedule supplies only a bounded total of step sizes, and with a bounded gradient the run can travel only a bounded distance. The schedule $1/\sqrt{t}$ has a divergent sum of squares, so the noise keeps arriving at full strength.

The edge case. The core's picture is a floor that moves down when the step shrinks. That picture is exact for a fixed step and misleading for a schedule. With a schedule there is no floor at any single step: the bound is the unrolled sum above, and a schedule can fail while every individual step looks small. The schedule $1/t^2$ is the clean example. At step ten its value is $0.01$, which looks harmless, and the run still cannot cross the finite total of $1.645$.

What the core hid. The core said that a shrinking schedule goes lower because the floor is proportional to the step. The rigorous statement is weaker and more useful. The conditions are sufficient rather than necessary, and they say nothing about speed. A schedule can satisfy both and still be far too slow, and one that violates the second can look fine for a short run. The core's last paragraph says as much, and the derivation shows why the test cannot be sharpened into a recipe.

Batch as a second schedule. Doubling the batch halves the variance, which halves the noise term without touching the product. That is why a growing batch can stand in for a decaying step [S:46:30-31]. The total work stays roughly the same, because a larger batch buys fewer steps. The choice between the two is a choice about what the hardware does well, not about the mathematics.

Original sources. The two series conditions come from Robbins and Monro, and Bottou, Curtis and Nocedal quote them in that form [S:46:28-28]. Murphy names the sequence of steps a learning rate schedule and lists the constant, exact-line-search and backtracking options [S:63:314-316]. The halving rule, with twice as many steps after each halving, is derived in Bottou as a consequence of the fixed-step bound [S:46:28-29].

An open question. The conditions separate schedules that can work from those that cannot, and they do not rank the survivors. The field has not settled which schedule is fastest at a fixed budget. A schedule also interacts with the batch size, which can substitute for it [S:46:30-31]. Murphy lists step decay, exponential decay, polynomial decay, warmup and cyclical schedules, and gives a reason for each that is empirical rather than proved [S:63:326-326]. Evidence that would settle a comparison: a fixed budget, several seeds, the median and the spread of the final loss, and a statement of which hyperparameters were tuned for each schedule.

A frontier result. Averaging the iterates can beat reading the last one. Polyak and Ruppert showed that the running average of the iterates reaches the best asymptotic rate available to a stochastic gradient method, matching methods that use second-order information [S:63:327-327]. The average costs one vector of storage and one addition per step, and it turns the noise that a schedule leaves behind into a smaller error.

What to read next. Read Bottou section 4.2 for the diminishing-step theorem and the halving argument [S:46:28-29]. Read Murphy sections 8.4.3 and 8.4.4 for the catalogue of schedules and for averaging [S:63:326-327]. Read Bubeck section 6.3 for variance reduction as the alternative to a decaying step [S:43:108-108]. Then read the AdaGrad section of Dive into Deep Learning for a schedule built per coordinate [S:69:561-562].