Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule

Introduction

Gradient descent (GD) is a simple iterative algorithm to minimize an objective function $f$ by producing better and better estimates via the update

GD dates back nearly two hundred years to the work of Cauchy , yet it (and its variants) remain a primary workhorse in modern optimization, engineering, and machine learning due to the practical efficacy, simplicity, and scalability. It is of both theoretical and practical importance to analyze the convergence of GD and moreover to optimize parameters so that this convergence is as fast as possible.

A central fact in convex optimization is that with a prudent choice of the stepsize schedule $\{\alpha_{t}\}$—the onlyIn convex optimization, we typically view the initialization $x_{0}$ as part of the problem instance rather than a parameter choice, since $x_{0}=0$ without loss of generality after a possible translation of the objective function $f$. parameters of the algorithm—running GD from any initialization $x_{0}$ produces iterates which optimize $f$ to arbitrary accuracy. Quantifying this statement leads to two intertwined questions: How fast does $x_{n}$ converge to a minimizer $x^{*}$ of $f$? And what stepsize choice $\{\alpha_{t}\}$ leads to the fastest convergence rate?

This series of papers revisits these classical questions in the fundamental setting of smoothIn the non-smooth setting, it is classically known that acceleration is impossible, and moreover GD achieves the minimax-optimal convergence rate with simple monotonically decaying stepsize schedules like $\alpha_{t}\asymp 1/\sqrt{t}$ . convex optimization. Our overarching goal is to understand how much mileage can be obtained by simply optimizing the stepsize choice for GD.

Note that this is markedly different from the past forty years of literature on accelerating the convergence rate for GD. That literature—starting from Nesterov’s seminal work in 1983 —achieves faster convergence rates by modifying the GD algorithm with extra building blocks such as momentum, auxiliary sequences, or other internal dynamics. See the related work section or the recent survey . In contrast, we investigate the basic question of: can we accelerate convergence without changing the GD algorithm—just by optimizing the stepsizes?

The standard analysis of GD uses a constant stepsize schedule, i.e., $\alpha_{t}=\bar{\alpha}$ for all iterations $t$; see e.g. the textbooks among many others. For example, $\bar{\alpha}=1/M$ in the setting of $M$-smooth convex objectives, or $\bar{\alpha}=2/(M+m)$ if the objectives are additionally $m$-strongly convex. This prescription is based on the following fact:

This is provably correct. For example, in the strongly convex setting, this $\bar{\alpha}$ provides the optimal contraction rate—a larger stepsize $\alpha_{t}>\bar{\alpha}$ can lead to overshooting the target $x^{*}$, and a smaller stepsize $\alpha_{t}<\bar{\alpha}$ can lead to undershooting $x^{*}$.

However, it is well-known that even after optimizing the constant $\bar{\alpha}$, this constant stepsize schedule leads to a slow convergence rate. (Hence the intensive research on accelerated GD.) Moreover, even though many alternative stepsize schedules have been proposed in both theory and practice—e.g., exact line search, Armijo-Goldstein rules, Polyak-type schedules, Barzilai-Borwein-type schedules, etc., see the related work section—none of these alternative schedules have led to an analysis that outperforms the slow “unaccelerated” rate of constant stepsize GD. Conventional wisdom therefore dictates that slow convergence is unavoidable, unless one modifies GD by adding extra building blocks beyond choosing stepsizes, e.g., via momentum.

The premise of this series of papers is that this is wrong. Why might the constant stepsize schedule $\alpha_{t}=\bar{\alpha}$ be sub-optimal? Certainly it is optimal if GD is only run for $n=1$ iteration—this is the assertion (1.2). However, it is sub-optimal for $n$ steps of GD, for any $n>1$. Briefly, this is because the statement for $n=1$ requires the worst-case problem instance (the objective function $f$ and initialization $x_{0}$) to align with the choice of stepsize $\alpha_{t}\neq\bar{\alpha}$ so that the convergence is slow, and for $n>1$, the worst-case problem instances for each individual step might not align. This suggests an algorithmic opportunity:

We refer to this algorithmic idea as hedging between worst-case problem instances. (See §2 for a fully worked-out example.)

Of course, using non-constant stepsizes is not a new idea—for the special case of minimizing convex quadratics, it has been known that this enables faster convergence since Young’s seminal paper in 1953 . In particular, for quadratic optimization, the optimal stepsize schedule is not constant, but given by the inverse roots of Chebyshev polynomials; the order of these stepsizes is irrelevant for the convergence rate (assuming exact arithmetic); and the resulting convergence rate is the so-called accelerated rate that is optimal among all Krylov-subspace algorithms , including even modifications of GD that use momentum or internal dynamics. See the related work section §1.2 for further details.

However, while the advantage of non-constant stepsizes has been well-understood for quadratic optimization for 70 years (and nowadays is even taught in many introductory optimization courses), it has remained entirely open whether this phenomenon extends to any setting of convex optimization beyond quadratics. In particular, it was unclear whether any stepsize schedule could lead to any speedup over the textbook GD convergence rate—even by a constant factor.

This gap is due to several reasons. First, many phenomena from the quadratic case are simply false in the setting of general convex optimization: e.g., the stepsize schedule based on roots of the Chebyshev polynomials is provably bad for the convex setting [5, Chapter 8], and the order of the stepsizes dramatically affects the convergence rate in the convex setting [5, Chapter 8]. Second, any approach for establishing the advantage of a non-constant stepsize schedule must track how progress in the current iteration is affected by previous iterations—and this effect of history appeared to only be explicitly computable in the quadratic setting, essentially since that is the only case in which the GD map is linear (hence tractable to track after repeated iterations).

1 Contribution and discussion

In this initial paper, we show that GD can converge faster for smooth convex optimization by using certain time-varying, non-monotonic stepsize schedules. This answers the hedging question (1.3) in the affirmative. This series of papers publishes and extends the first author’s 2018 Master’s Thesis (advised by the second author), which proved such a result for the first time, see the related work section §1.2. In particular, Chapter 8 of the thesis showed for the first time that a constant-factor improvement over the unaccelerated rate is possible in the smooth strongly convex setting, and Chapter 6 of the thesis showed for the first time that an asymptotic acceleration is possible in any setting beyond quadratics. (The latter result proves that arcsine-distributed random stepsizes achieve the fully accelerated rate $\Theta(\sqrt{\kappa}\log 1/\varepsilon)$ if the convex functions are separable; this will be detailed in a forthcoming paper.) Prior to this thesis, the only result for acceleration via choosing stepsizes was for the special case of quadratic optimization, due to Young in 1953.

Conceptually, we deviate from traditional analyses of GD (and other optimization algorithms) by directly analyzing the cumulative progress of all the steps of the algorithm, rather than combining separate bounds for the progress of individual steps. As mentioned above, this global analysis of multi-step descent is provably necessary to show any benefit for any deviation from the constant stepsize schedule. Indeed, separately analyzing the progress for each iteration—as done, e.g., in standard GD analyses, in exact line search, or in standard offline-to-online convex optimization reductions—is provably too shortsighted and unavoidably leads to pessimistic, unaccelerated convergence rates. The key difficulty is how to track how different iterations affect progress in other iterations. Previously, this could be accomplished only for the special case of quadratics because then the GD update is linear. We show that this can be accomplished for general convex setting by this by using long-range consistency conditions between the gradients seen along the algorithm’s trajectory. We provide a high-level overview of these new conceptual ideas in §2.

Below, we formally state our main result in §1.1.1, and then discuss the improved convergence rate in §1.1.2, the proposed stepsize schedule in §1.1.3, and the generality of the result in §1.1.4.

where $x^{*}$ denotes the unique minimizer of $f$, $x_{n}$ denotes the output of $n$ steps of GD using the Silver Stepsize Schedule (defined in §3), and $\tau_{n}$ denotes the $n$-step Silver Convergence Rate (defined in §3). Moreover, $\tau_{n}$ undergoes the following phase transition at $n^{*}=\Theta(\kappa^{\log_{\rho}2})$:

Acceleration regime. For $n\leqslant n^{*}$,

In particular, in order to achieve a final error $\|x_{n}-x^{*}\|^{2}\leqslant\varepsilon$, it suffices to run GD using the Silver Stepsize Schedule for

1.2 Discussion of Silver Convergence Rate

Our rate $\Theta(\kappa^{\log_{\rho}2}\log 1/\varepsilon)$ lies between the textbook rate $\Theta(\kappa\log 1/\varepsilon)$ for GD and the accelerated rate $\Theta(\sqrt{\kappa}\log 1/\varepsilon)$ due to Nesterov in 1983 . We emphasize that before the thesis that this paper is based upon, it was unknown if any improvement over the unaccelerated rate—even a constant factor—was achievable by any stepsize schedule. Our convergence rate is faster than all known GD stepsize schedules for convex optimization, including constant stepsize schedules, Polyak-type schedules, Barzilai-Borwein-type schedules, Goldstein-Armijo-type schedules, exact line search, etc.

A distinctive feature of the Silver Convergence Rate $\tau_{n}$ is that it undergoes a phase transition: $\tau_{n}$ switches from super-exponential to exponential in the horizon $n$. This transition occurs at $n^{*}\asymp\kappa^{\log_{\rho}2}$, which is the number of iterations required to make the error decrease by a constant factor. See Figure 2. The reason for these two regimes is that beyond $n^{*}$, the new stepsizes converge quadratically fast to their stationary value; details in §4.

Acceleration regime. This regime encapsulates the advantage of multi-step descent: the super-exponentiality of the $n$-step bound makes it better than composing the $1$-step bound $n$ times. This super-exponential regime interpolates the $\kappa$ dependence between the unaccelerated rate (achieved at $n=1$) and our partially accelerated rate (achieved at $n\gtrsim n^{*}$).

Saturation regime. Here, the benefit of multi-step descent becomes negligible: $\tau_{2n}\approx\tau_{n}^{2}$ for $n\geqslant n^{*}$.Note that $\tau_{2n}\leqslant\tau_{n}^{2}$; intuitively this amounts to the statement that the optimal $2n$-step schedule is at least as good as repeating the optimal $n$-step schedule twice. We call this inequality rate monotonicity, see §4. The statement $\tau_{2n}\approx\tau_{n}^{2}$ therefore states that this bound is nearly tight. Briefly, this rate saturation occurs because the Silver Stepsize Schedule is approximately periodic with period $n^{*}$, see §1.1.3.

The convergence rate in Theorem 1.1 is independent of the dimension $d$ and thus can be extended to infinite-dimensional Hilbert space. This is because our analysis only uses consistency conditions for the GD trajectory to arise from a convex function—and these consistency conditions are dimension-independent . This is in common with classical analyses of GD and Nesterov-style acceleration.

We conjecture the Silver Stepsize Schedule has the fastest convergence rate among all possible choices of GD stepsize schedules. We prove optimality for the $n=2$ case of [5, Chapter 8] in §2; this proof readily extends to small $n$, and we will address the question of optimality for all $n$ in a shortly forthcoming paper.

1.3 Discussion of Silver Stepsize Schedule

The Silver Stepsize Schedule is defined recursively in a fully explicit way. We briefly overview the construction; see §3 for full details. The $1$-step schedule $h^{(1)}$ is initialized to the constant $\bar{\alpha}=2/(1+1/\kappa)$ that is classically known to be optimal for $1$-step descent. We then recursively define the $2n$-step schedule $h^{(2n)}$ as

This recursive construction produces (normalized) stepsize schedules that follow the pattern

This schedule simplifies in the limit $n\to\infty$: the $i$-th normalized stepsize is given by $a_{B(i)}$, where $B(i)$ denotes the smallest power of $2$ in the binary expansion of $i$. Note that no entries of the $b$ sequence appear.

For the special case of quadratic optimization, the order of the stepsizes is well-known to be irrelevant for the convergence rate. In contrast, in the general setting of convex optimization, the order of the stepsizes provably does matter [5, Chapter 8]. For example, it can be shown that the convergence rate in Theorem 1.1 becomes greater than $1$ (i.e., not even contractive) if one reverses the order of the $2$-step Silver Stepsize Schedule.

The Silver Stepsize Schedule generates a fractal, see Figure 1. This is due to our recursive construction, and is directly evident from the aforementioned fact that the $i$-th stepsize depends on the sparsity pattern of the binary expansion of $i$. This fractal structure aligns with the numerical observations in , and is in stark contrast with all classical stepsize schedules which, if time-varying, decay monotonically in the iteration number $i$, e.g., as $1/i$.

The Silver Stepsize Schedule is not periodic as it is continually changes. However, it is approximately periodic with period $n^{*}\asymp\kappa^{\log_{\rho}2}$, see Figure 1. This is another facet of the rate saturation phenomenon discussed in §1.1.2. See §4 for details.

Theorem 1.1 is stated for horizons $n$ that are powers of $2$. For arbitrary integers $n$, one can simply run the Silver Stepsize Schedule for the largest power of $2$ below $n$, or better, run for all powers of $2$ in the binary expansion of $n$. This affects the average per-step-rate by only a small constant factor. We moreover conjecture that simply using $n$ steps of the infinite-horizon Silver Stepsize Schedule leads to the same convergence rate modulo a lower-order term. This seems reasonable since only logarithmically many stepsizes are changed, but we have not attempted to prove this. Orthogonally, if the horizon is not set in advance, then one can, e.g., do a “doubling” trick by exploiting the fact that the first $2^{i}-1$ stepsizes are identical for all $n\geqslant 2^{i}$. Specifically, for each $i$, decide on iteration $2^{i}-1$ whether to stop at $n=2^{i}$ iterations, or repeat roughly the same amount of effort and go to $2^{i+1}-1$ iterations.

1.4 Discussion of problem setting

Theorem 4.1 uses distance as the progress measure. This can be replaced by other standard progress measures such as function suboptimality or gradient norm, in the initial or final condition or both, since these measures are equivalent for $\kappa$-conditioned functions. This black-box replacement affects the rate by only a lower-order term. Moreover, this equivalence factor can be avoided by re-doing our analysis in a conceptually identical way for the desired progress measures (possibly also with minor changes to the stepsize schedule; e.g., for gradient norm contraction, it appears that one should reverse the order [5, Chapter 8]).

It is well-known that smoothness is required for acceleration: otherwise, GD cannot be accelerated even with momentum or other internal dynamics [45, Chapter 3].

Theorem 1.1 is stated for the strongly convex setting, but this can be relaxed to the non-strongly convex setting. Indeed, all our core conceptual ideas extend: the advantage of time-varying, non-monotonic stepsizes, proving this advantage via multi-step descent rather than iterating the greedy $1$-step bound, certifying multi-step descent via recursive gluing, etc. The adaptation requires only minor technical modifications to the stepsize schedule, certificate recursion, and progress measure. These details will appear in a shortly forthcoming paper.

We mention that by standard black-box reductions (see e.g., or [12, page 285]), Theorem 1.1 immediately implies accelerated rates for the (non-strongly) convex setting by running GD with the Silver Stepsize Schedule on a quadratically regularized objective, i.e., $f(\cdot)+\delta\|\cdot-y\|^{2}$ for appropriate choices of $\delta$ and $y$. This gives an analogous partially accelerated rate of $\varepsilon^{-\log\rho_{2}}\approx\varepsilon^{-0.7864}$ iterations to obtain $\varepsilon$ function suboptimality. This is intermediate between the textbook unaccelerated rate $\Theta(\varepsilon^{-1})$ and Nesterov’s accelerated rate $\Theta(\varepsilon^{-1/2})$ from 1983 . This strongly suggests that acceleration in the (non-strongly) convex case surpasses the $\Theta(1/(T\log T))$ conjecture in . The aforementioned forthcoming paper will address this via a direct analysis that bypasses regularization.

2 Related work

For quadratic optimization, the GD map becomes linear, which enables three equivalent approaches to acceleration. One approach, taken by Young in 1953 is to choose non-constant stepsizes that are the inverses of the roots of Chebyshev polynomials . A second approach is to use momentum, achieved for example by Hestenes and Stiefel’s Conjugate Gradient Method in 1952 and Polyak’s Heavy Ball Method in 1964 . This equivalence arises because momentum amounts to a three-term recurrence, which if the coefficients are chosen appropriately, generates the same sequence of Chebyshev polynomials; see e.g. [66, Ch. 5]. A third approach is to use the limiting distribution of the roots of the Chebyshev polynomials: the arcsine distribution . This equivalence is due to the fact that the order of stepsizes does not affect convergence in the quadratic case, thus as the horizon $n\to\infty$, one might as well draw stepsizes i.i.d. from the equilibrium measure. It is important to emphasize that the elegant equivalences between these three approaches—varying stepsizes, momentum, and equilibrium measures—breaks down beyond the special case of quadratic optimization.

The above discussion concerns only the convergence rate, not stability. In settings with noisy gradients or inexact arithmetic, the order of the stepsizes may significantly affect the convergence rate of GD, even for quadratic optimization. This question of stability to roundoff errors was already raised in Young’s original paper . In such settings, it is desirable to find permutations of the Chebyshev roots for which GD trajectories are maximally stable. An effective approach is to interleave the roots of Chebyshev polynomials of increasing degree . This leads to a fractal pattern, superficially similar to our proposed stepsize schedule; see for a recent discussion and additional results. However, we emphasize that this fractal is not only fundamentally different but also arises due to entirely different considerations—stability rather than fast convergence.

If the quadratic function’s Hessian has additional spectral structure, then improved results are possible. This is because the different viewpoints discussed above are classically known to extend to this situation via potential theory; see the excellent survey and the references within. This enables further refinements of the methods described above for structured quadratics and sometimes also perturbations away from quadratics; see e.g., .

2.2 The general case of convex optimization

For constant stepsize, the optimal convergence rate for GD is $\Theta(\kappa\log 1/\varepsilon)$ in the strongly convex setting, and $\Theta(1/\varepsilon)$ in the convex setting; see, e.g., the textbooks . This is often called the unaccelerated rate for GD. Many alternative stepsize schedules have been proposed in both theory and practice. We highlight several well-studied schedules. One family of well-studied strategies adaptively chooses stepsizes either by minimizing the function value over the line spanned by the gradient. This mininimization can be performed exactly via line search , or approximately via Goldstein-Armijo-type schedules . Alternatively, it can be done by minimizing the estimated distance to the optimum via Polyak-type schedules . Another family is Barzilai-Borwein-type schedules, which are quasi-Newton methods that approximate the Hessian using the past step’s change in iterate and gradient . None of these strategies are known to accelerate beyond the case of quadratics.

The conventional approach for achieving faster convergence is to consider variations of GD that use auxiliary sequences of iterates and/or different update directions than the gradient. This is of course more powerful than just changing the stepsizes, and can be interpreted from a control theory perspective as adding internal dynamics to the algorithm. Accelerated rates were first shown in Nesterov’s seminal work in 1983 , and since then, many other accelerated algorithms and analyses have been proposed , as well as fruitful interpretations via continuous-time analysis . These accelerated algorithms require only $\Theta(\sqrt{\kappa}\log 1/\varepsilon)$ iterations, or $\Theta(1/\sqrt{\varepsilon})$ in the convex case, which is known to be minimax-optimal up to a constant for any algorithm that uses only gradient information . Much work has recently sharpened this constant, culminating in exactly matching upper and lower bounds . This recent line work exploits the idea that the worst-case convergence of optimization algorithms can be numerically computed via semidefinite programming (SDP) . This has also enabled using computer-automated SDP-analyses to investigate richer classes of algorithms, such as robust versions of accelerated methods , proximal algorithms , operator splitting , line search , biased stochastic gradient methods , inexact Newton’s method , among many others. This area of research is extremely active and we refer the reader to the excellent recent survey for a comprehensive set of references and a detailed historical account.

Although many time-varying stepsize schedules have been considered for GD, no convergences analyses improved over the textbook unaccelerated rate beyond the quadratic case. In 2018, Altschuler’s MS thesis considered time-varying stepsize schedules in several settings, all through the unifying lens of hedging and multi-step descent. In Chapter 8 of the thesis, the PESTO framework was used to show for the first time the advantage of using time-varying stepsize schedules for GD beyond the quadratic setting. Explicit solutions were given for $n=2,3$ in the strongly convex setting. This showed that a constant-factor improvement over the textbook unaccelerated GD rate was indeed possible. A key difficulty in extending this to larger horizons $n$ is that the search for optimal stepsizes is non-convex. In 2022, Das Gupta et al. combined Branch & Bound techniques with the PESTO SDP to develop algorithms that perform this search numerically, and as an example used this to compute good approximate schedules in the convex setting for larger values of $n$ up to $50$. Grimmer very recently developed a technique to round these Branch & Bound solutions to exact rational certificates. This allowed him to extend these approximate stepsize schedules up to $n=127$ in order to get a larger constant-factor improvement, and conjectured that dynamic stepsizes might lead to an accelerated rate of $O(1/(T\log T))$. By extending a recursive application of the $2$-step solution in , the present paper rigorously proves acceleration for all horizons $n$, and in particular obtains the first asymptotic improvements over the textbook unaccelerated GD rate—not just by a constant factor.

3 Organization

In §2, we provide an overview of the core conceptual ideas via the key case $n=2$. §3 formally defines the Silver Stepsize Schedule and the Silver Convergence Rate $\tau_{n}$, §4 establishes the claimed properties of $\tau_{n}$, and §5 proves that $\tau_{n}$ is a valid bound on the convergence rate of the Silver Stepsize Schedule. §6 discusses future directions. Some technical details are deferred to the Appendix.

Conceptual overview: two-step case (n=2𝑛2n=2)

This section provides a complete analysis for the minimal non-trivial horizon length: $n=2$. (No hedging can occur if $n=1$.) Our goal here is to provide further intuition for the core concepts of hedging and multi-step descent, and explain concretely how these manifest in the design and analysis of the Silver Stepsize Schedule. Indeed, the $n=2$ case captures most of the core intuition and ideas, and the result for general $n$ is essentially just an amped-up version thereof. These results first appeared in Altschuler’s thesis [5, Chapter 8]; we refer to there for a lengthier treatment.

For simplicity, in this section we denote the stepsizes by $\alpha$ and $\beta$, so that the algorithm is

and the worst-case convergence rate over a function class $\mathcal{F}$ is

The question of optimal stepsizes is therefore the minimax problem

To motivate why non-constant stepsizes might be helpful, in §2.1 we first briefly recall the classical result of which solves this for the case of quadratic $\mathcal{F}$. Then in §2.2, we solve this problem for convex $\mathcal{F}$ by presenting the $2$-step Silver Stepsize Schedule from [5, Theorem 8.11], proving its convergence rate via multi-step descent, and proving its optimality via hedging.

What is the optimal stepsize schedule $(\alpha,\beta)$ for the class $\mathcal{F}$ of quadratic functions $f$ that are $m$-strongly convex and $M$-smooth? Without loss of generality after translating, $f(x)=\frac{1}{2}x^{T}Hx$ where $mI\preceq H\preceq MI$. By definition of GD, $x_{1}=(1-\alpha H)x_{0}$ and $x_{2}=(1-\beta H)x_{1}$, thus

Observe that as one ranges over all possible choices of the stepsizes $(\alpha,\beta)$, the polynomial $p$ ranges over the set $\mathcal{P}$ of all degree $2$ polynomials satisfying the normalizing condition $p(0)=1$. Therefore finding optimal stepsizes $(\alpha,\beta)$ is equivalent to finding an optimal polynomial $p\in\mathcal{P}$.

What is the optimal polynomial? By the above display and properties of the spectral norm,

Thus the optimal polynomial $p\in P_{2}$ is the one with minimal $L_{\infty}$ norm over the interval $[m,M]$. It is classically known that this is the (translated and scaled) Chebyshev polynomial of the first kind, see e.g., . Thus the optimal stepsizes $(\alpha^{*},\beta^{*})$ are the inverses of the roots \tfrac{M+m}{2}\raisebox{0.86108pt}{\scriptstyle\pm}\tfrac{M-m}{2\sqrt{2}} of the Chebyshev polynomial, in either order. These are the symmetric marked points in Figure 3, left.

Crucially, observe that these two stepsizes are different—hence the advantage of non-constant schedules in the quadratic setting. We now interpret this phenomenon in two ways that are essential to our intuition for the convex setting. This discussion is based on [5, Chapters 1 and 2].

Why is $\bar{\alpha}:=\tfrac{2}{M+m}$ suboptimal for $2$ steps of GD when it is optimal for $1$? Recall that it is optimal for $1$ step because GD overshoots when using a longer step $\alpha>\bar{\alpha}$ on the sharp function $f(x)=\tfrac{M}{2}x^{2}$, and undershoots when using a shorter step $\alpha<\bar{\alpha}$ on the shallow function $f(x)=\tfrac{m}{2}x^{2}$. The algorithmic opportunity is that these worst-case functions are different for short-step GD and long-step GD. This is why using a short step and a long step—each individually suboptimal—can lead to faster overall convergence than using $\bar{\alpha}$ twice. We refer to this misalignment of worst-case functions as hedging. See Figure 3, left.

There is a dual interpretation of hedging via multi-step descent. By (2.2), the worst-case rate for $2$ steps is

Contrast this with the greedy analysis, which bounds the worst-case rate after $2$ iterations by the product of the worst-case rates for $1$ step with $\alpha$ or $\beta$, namely

Observe that the greedy analysis (2.4) is so shortsighted that it not only leads to worse bounds for any given stepsize schedule, but moreover leads to the wrong prescription of stepsizes. Indeed, optimizing this convergence rate (2.4) over $(\alpha,\beta)$ leads to $\alpha=\beta=\tfrac{2}{M+m}$ which is the constant schedule. This necessity of multi-step descent explains why the mainstream approach for convex optimization is constant stepsizes: previous approaches were unable to analyze multi-step descent. (This is only tractable in the quadratic setting because the gradient operator is linear, see (2.2).)

2 Optimal stepsizes for convex optimization

We now turn to the convex setting. Let $\mathcal{F}$ denote the set of $m$-strongly convex and $M$-smooth functions. Young’s Chebyshev schedule is then provably badThis is not just a failure of analysis techniques: even for mild condition numbers like $\kappa=10$, using the $2$-step Chebyshev Schedule in either order makes GD divergent (i.e., the contraction rate is larger than $1$). We are not aware of a reference for this, but it can be shown e.g., by using the SDP-analysis framework of ..What are the optimal $2$ stepsizes? Certainly the above discussion of hedging motivates using non-constant stepsizes, but proving this requires multi-step descent, and that has been the longstanding stumbling block preventing progress beyond the quadratic setting.

We show below that the $2$-step convergence rate $R(\alpha,\beta;\mathcal{F})$ is minimized by the stepsizes $(\alpha,\beta)$ that are defined by the system of equations

and moreover the optimal $2$-step convergence rate $R^{*}$ is given by this equalized value.

The equations (2.5) can be solved explicitly, to give the alternative expressions

where $S=\sqrt{M^{2}+(M-m)^{2}}$. These are the formulas given in [5, Thm. 8.10], and is the $n=2$ case of the Silver Stepsize Schedule and (square-rooted) Silver Convergence Rate defined in §4.

This $n=2$ solution showcases the key phenomena that also occur for larger $n$:

Provable advantage of dynamic stepsizes. Since $R^{*}<(\tfrac{M-m}{M+m})^{2}$, this proves that it is possible to improve over standard GD by dynamically changing the stepsize. (Recall that $\tfrac{M-m}{M+m}$ is the textbook unaccelerated rate for 1 step of GD.) This mirrors how for quadratics, the optimal 2-step rate (2.3) is better than the squared optimal $1$-step rate (2.4).

Stepsize splitting. Since $\alpha^{*}<\frac{2}{M+m}<\beta^{*}$, the optimal stepsize $\frac{2}{M+m}$ for $n=1$ splits into a short step $\alpha^{*}$ and long step $\beta^{*}$. For general $n$, the Silver Stepsize Schedule mirrors this splitting at every scale: it splits the largest stepsize into a shorter and longer step.

Unique, asymmetric solution. Unlike the quadratic case, here the stepsize order is essential for fast convergence: the splitting requires the small stepsize to be first.We remark that the order may change for different progress measures, see [5, Chapter 8.2]. As a consequence, here the optimal stepsize schedule is unique. See Figure 3, right.

Milder splitting. Even ignoring order, the stepsize values differ from the quadratic case. This occurs because the class of convex functions is richer than the class of quadratics, thus the supremum defining the worst-case rate $R(\alpha,\beta;\mathcal{F})$ is over more functions, thus it is harder to misalign the worst-cases by hedging. The result is less aggressive hedging and partial acceleration: the improvement over the $1$-step rate is smaller than in the quadratic case.

We now turn to proving that Theorem 1.1 holds in the case $n=2$, and moreover that the proposed Silver Stepsize Schedule is optimal among all $2$-step schedules.

Consider any strong-convexity and smoothness parameters $0<m\leqslant M<\infty$. The unique optimal $2$-step schedule $(\alpha^{*},\beta^{*})\in\operatorname*{argmin}_{\alpha,\beta}R(\alpha,\beta;\mathcal{F})$ and the corresponding optimal $2$-step rate $R^{*}$ are as stated in Remark 2.1.

The proof has two parts: an upper bound on $R(\alpha^{*},\beta^{*},\mathcal{F})$ that proves that our $2$-step schedule achieves the claimed rate, and a matching lower bound that proves optimality (and in fact uniqueness too). We do this below via multi-step descent and hedging, respectively.

2.2 Upper bound: rate certification via multi-step descent

As discussed above, in order to prove any benefit of deviating from the constant stepsizes, we must directly analyze the cumulative multi-step descent of all iterations. This requires capturing how different iterations affect other iterations’ progress. We do this by exploiting long-range consistency conditions between the information that GD sees along its trajectory.

Our starting point is a known result on convex interpolability, recalled next. There is a set of consistency conditions that any $f\in\mathcal{F}$ must satisfy at any set of points $\{x_{i}\}_{i\in\mathcal{I}}$: the co-coercivity

must be non-negative for every pair of points $x,y\in\mathcal{I}$. Of particular interest to us is the converse: there are consistency conditions on a set of data $\{(x_{i},g_{i},f_{i})\}_{i\in\mathcal{I}}$ that ensure it is $\mathcal{F}$-interpolable, i.e., there exists $f\in\mathcal{F}$ satisfying $g_{i}=\nabla f(x_{i})$ and $f_{i}=f(x_{i})$ for each $i\in\mathcal{I}$. Specifically, a celebrated line of work on convex interpolability culminated in a beautiful theorem of which states that $\{(x_{i},g_{i},f_{i})\}_{i\in\mathcal{I}}$ is $\mathcal{F}$-interpolable if and only if

is non-negative for every pair of indices $i,j\in\mathcal{I}$.

We apply these conditions along the trajectory of GD. Specifically, we take $\mathcal{I}:=\{0,1,\dots,n,*\}$ to index the GD iterates and the optimum, and let $\{(x_{i},g_{i},f_{i})\}_{i\in\mathcal{I}}$ denote the first-order dataThis is purely an analysis device and does not change the GD algorithm (which neither knows the optimum nor queries function values). Including function values simplifies the interpolability conditions and thus our analysis.. The upshot is that this theorem enables replacing the supremum over functions $f\in\mathcal{F}$ by the data $\{(x_{i},g_{i},f_{i})\}_{i\in\mathcal{I}}$ in the definition of the worst-case rate $R(\alpha,\beta;\mathcal{F})$. Note that this replacement is lossless since the interpolability conditions in the theorem are necessary and sufficient.

From the perspective of hedging, these co-coercivity conditions $\{Q_{ij}\geqslant 0\}_{i\neq j\in\mathcal{I}}$ generate all possible long-range consistency constraints on the objective function given the GD trajectory. From the perspective of multi-step descent, they generate all possible valid inequalities with which one can prove convergence rates for GD. Let us explain how we use this in the case $n=2$.

It suffices to prove the rate certification identity

for some non-negative choice of multipliers $\lambda_{ij}$. Indeed, since $Q_{ij}\geqslant 0$ is non-negative for any objective function $f\in\mathcal{F}$, the rate certification identity implies

which proves the claimed rate. It remains to construct non-negative $\lambda_{ij}$ for the rate certification identity. This is done in [5, Theorem 8.10]. For completeness, we include the explicit values here, in slightly simpler (but equivalent) form:

Here, the rows and columns are indexed by $0,1,*$, in that order. ∎

Of course, the challenge in such a proof is finding the multipliers $\lambda_{ij}$. When we prove our result for general $n$, we prove that the multipliers for the $2n$-length Silver Stepsize Schedule are recursively built from repeating the multipliers for the $n$-length Silver Stepsize Schedule twice, modulo a low rank and sparse correction expressible in closed form. With this recursion, (i) the multipliers for the $n=2$ case above can be derived formulaically from the textbook proof for $n=1$, and (ii) the proof for the case of general $n$ mirrors the proof for $n=2$, at least in spirit.

2.3 Lower bound: optimality and uniqueness via hedging

for all non-trivialWe call such stepsizes non-trivial since if a stepsize is outside this interval, then clipping it to the interval improves convergence. This can be proved by noticing that, of the four hard functions in this proof, all but the fourth apply if $\alpha\geqslant 1/M$, and all but the third apply if $\alpha\leqslant 1/m$. By optimizing the resulting analogous bounds (2.10) for the cases $\alpha<1/M$ and $\alpha>1/m$, it follows that clipping to the interval $[1/M,1/m]$ leads to faster convergence. stepsizes $\alpha,\beta\in[1/M,1/m]$, where

This suffices since it is straightforward to verify that $\min_{\alpha,\beta}\underline{R}(\alpha,\beta)$ is minimized uniquely at $(\alpha^{*},\beta^{*})$ with value $R^{*}$; this yields the two defining equations in (2.5). Indeed, this verification can be done by hand by case enumeration, or simpler, it can be rigorously proven using standard symbolic computation techniques such as quantifier elimination .

It remains to prove (2.10). We do this by exhibiting four “hard-to-optimize” functions $f\in\mathcal{F}$ for which the $2$-step convergence rate of GD from initialization $x_{0}=1$ is given by these four values. The first two functions are the quadratics $f(x)=\frac{\lambda}{2}x^{2}$ for $\lambda\in\{\alpha,\beta\}$, in which case $x_{2}=(1-\lambda\alpha)(1-\lambda\beta)$. The other two functions are piecewise quadratic. It is perhaps simplest to state these functions via their second derivative since then any function value can be obtained by integrating from the minimum $x^{*}=0$. The third function is given by $f^{\prime\prime}(x)=M$ for $x\geqslant 0$ and $f^{\prime\prime}(x)=m$ otherwise, in which case $x_{2}=(1-M\alpha)(1-m\beta)$. The fourth function is given by $f^{\prime\prime}(x)=m$ for $x\geqslant\frac{1-m\alpha}{1+\alpha(M-m)}$ and $f^{\prime\prime}(x)=M$ otherwise, in which case $x_{2}=\frac{(1-m\alpha)(1-M\beta)}{1+\alpha(M-m)}$. This proves the desired identity (2.10). ∎

It is insightful to contrast these four hard functions defining the $2$-step rate functionThe rate optimality identity (2.10) actually holds with equality over all non-trivial stepsizes $\alpha,\beta\in[1/M,1/m]$, although this is unnecessary for our purposes. with the analog for the quadratic case. Recall from (2.3) that in the quadratic setting, the $2$-step rate function $R(\alpha,\beta\;\mathcal{F})=\sup_{m\leqslant\lambda\leqslant M}|(1-\alpha\lambda)(1-\beta\lambda)|$. Although this seems to requires infinitely many $\lambda$, it was shown in [5, Chapter 5.2.2] that one can replace the continuum $[m,M]$ with the $3$ extrema of Chebyshev polynomials, i.e.,

in the sense that minimizing this over $(\alpha,\beta)$ yields Young’s $2$-step Chebyshev Schedule. These three values of $\lambda$ correspond to “hard-to-optimize” quadratic functions $f(x)=\tfrac{\lambda}{2}x^{2}$. How are they different from the hard functions in the above proof? The first two quadratics are common between the quadratic and convex case, but the remaining functions differ. In particular, the third and fourth functions in the convex case are non-quadratic. In words, the richness of the convex function class enables changing the curvature in different places, which enables more alignment of the bad convergence rates for the individual stepsizes. This makes it provably harder to hedge in the convex setting. Note also that the denominator of the fourth function is singlehandedly responsible for the asymmetry in $\bar{R}(\alpha,\beta)$, and thus in the optimal schedule the convex setting.

This proof can be extended to establish the optimality of the Silver Stepsize Schedule, as will be detailed in a shortly forthcoming paper.

Silver Stepsize Schedule

For simplicity of exposition, from here on we restrict to horizons $n$ that are powers of $2$ (see §1.1.3 for a discussion of extensions to general $n$), and we set $m=1/\kappa$ and $M=1$ to reduce notational overhead (this is without loss of generality after a possible rescaling).

We construct auxiliary stepsize sequences $y_{n},z_{n}$, that are normalized in a certain way to lie in the interval $$. The particular normalization (a certain linear fractional transformation defined in §3.2) simplifies the recursive stepsize splitting by making it a quadratic equation.

Explicitly, initialize the sequences $y_{1}=z_{1}=1/\kappa$, and define $y_{n},z_{n}$ recursively from $z_{n/2}$ as the solutions to the defining equations

This is the direct analog of the stepsize splitting detailed for the case $n=2$ in §2.2. Denoting $\xi=1-z_{n/2}$, the explicit solution is

The following lemma collect several simple observations about these sequences. See §4 for a detailed discussion of how $y_{n},z_{n}$ both increase to their limits $y_{n},z_{n}\to 1$, exponentially fast when they are close to , and then doubly exponentially fast when they are close to $1$.

The sequence $z_{n}$ is monotonically increasing from $z_{1}=1/\kappa$ to $\lim_{n\to\infty}z_{n}=1$. For all $n$,

Moreover, the above inequality $y_{n}\leqslant z_{n}$ is strict for any $\kappa>1$.

2 Silver Stepsizes

from the Normalized Silver Stepsizes $y_{n},z_{n}$ via the linear fractional transformation $\psi$ given by

We remark that this mapping $\psi$ has the following special values

Moreover, the above inequality $a_{n}\leqslant b_{n}$ is strict for any $\kappa>1$.

3 Silver Stepsize Schedule

Let $h^{(n)}$ denote the Silver Stepsize Schedule of length $n$. Denote its $n/2$-th stepsize by $a_{n}$ and its $n$-th by $b_{n}$. As overviewed briefly in §1.1.3, we recursively construct

See Figure 1 for an illustration of this pattern, and see §1.1.3 for a discussion of the emergent fractal, dependence on the horizon, and patterns for small $n$.

This can be viewed as a geometric distribution that takes value $a_{2^{i}}$ with probability $2^{-i}$.

4 Silver Convergence Rate

Of course, from just this definition it is not yet clear why we call $\tau_{n}$ a rate; in §5 we prove that $\tau_{n}$ is the convergence rate of the Silver Stepsize Schedule. Note that since $z_{n}$ is monotonically increasing (Lemma 3.1), this rate $\tau_{n}$ is monotonically decreasing from the textbook unaccelerated rate $\tau_{1}=((\kappa-1)/(\kappa+1))^{2}$ to $\lim_{n\to\infty}\tau_{n}=0$. In the following section, we provide a complete understanding of exactly how fast $\tau_{n}$ converges to .

Analysis of the Silver Convergence Rate

Here we prove the bound on the Silver Convergence Rate $\tau_{n}$ in our main result (Theorem 1.1). We restate this bound for convenience.

Denote $i^{*}:=\lfloor\log_{\rho}\frac{\kappa}{3}\rfloor$ and $n^{*}:=2^{i^{*}}$. Then for any $n$ that is a power of $2$, we have the following bound on $\tau_{n}$.

Acceleration regime. If $n\leqslant n^{*}$, then

This result establishes $n^{*}\asymp\kappa^{\log_{\rho}2}$ as the location of a phase transition. There, the Silver Convergence Rate $\tau_{n}$ switches from super-exponential to exponential in the horizon $n$. See the introduction for a detailed discussion of this phase transition and the intuition behind it in terms of how the Silver Stepsize Schedule is effectively periodic with periodic of length $n^{*}$.

For simplicity, we make no attempt to optimize the constants in the $\Theta$ and the choice of $i^{*}$ (the $1/3$ in the theorem statement is arbitrary). Our proofs make crude constant bounds to ease the exposition, and it is straightforward to tighten these. However, as established by our upper and lower bounds, our proofs are already tight up to reasonable constant factors.

The section is organized as follows. In §4.1, we provide a heuristic derivation of Theorem 4.1 that explains the phase transition via Taylor expanding the dynamics in the two regimes. This gives the central intuition for the result and its proof. In §4.2, we make these Taylor expansions precise to conclude the proof of Theorem 4.1.

The phase transition in $\tau_{n}=(\tfrac{1-z_{n}}{1+z_{n}})^{2}$ is a consequence of the phase transition in the dynamics of the auxiliary sequence $z_{n}$. To explain this, it is convenient to simplify notation by re-indexing $n=2^{i}$ so that iterations of the dynamical process are indexed by $i=0,1,2,3,\dots$ rather than $n=1,2,4,8\dots$. It is helpful to also re-parameterize

where $\Psi:(0,1)\to(0,1)$ is the monotone bijection

The significance of this re-parameterization to $h_{i}$ is that

Thus, proving a fast convergence rate amounts to lower bounding $h_{i}$.

What do the dynamics of $h_{i}$ look like? At initialization, $z_{1}=1/\kappa$ (see §3), thus

Then the iterations of this process increase $h_{i}$ exponentially fast to $1$ when it is sub-constant size, and then doubly-exponentially fast when $h_{i}$ is of constant size. (This dichotomy is the source of the phase transition in Theorem 4.1.)

To analyze these dynamics, let $H:(0,1)\to(0,1)$ denote the update function sending $h_{i}$ to $h_{i+1}$. Then $H=\Psi\circ F\circ\Psi^{-1}$ where $F(z)=z(1-z+\sqrt{1+(1-z)^{2}})$ is the function that updates $z_{n}$ to $z_{2n}=F(z_{n})$, see Section 3. A direct algebraic computation gives the explicit expression

Taylor expanding $H$ around $h\approx 0$ and $h\approx 1$ illustrates the markedly different dynamics in these two regimes; see Figure 6.

Thus, in this regime, each $h_{i}$ increases by a factor of roughly $\rho$, thus $h_{i}\approx\rho^{i}h_{0}\approx\rho^{i}/(2\kappa)$, thus the Silver Convergence Rate is roughly

This regime lasts for only $i\approx\log_{\rho}\kappa$ iterations (aka horizon $n=2^{i}\approx\kappa^{\log_{2}\rho}$) because at that point $h_{i}\asymp\rho^{i}/\kappa\asymp 1$ is of constant size. This is the phase transition.

In words, the key phenomenon here is that the average rate $\tau_{n}^{1/n}$ stays essentially the same as $n$ increases—in contrast to the acceleration regime, in which the average rate improves in $n$. Indeed, the Taylor expansion (4.6) indicates that in the saturation regime, $\tau_{n}=\left(1-h_{i}\right)^{2}\approx(1-h_{i-1})^{4}=\tau_{n/2}^{2}$. By repeating this argument and then using the fact that $\tau_{n^{*}}=\exp(-\Theta(1))$ which follows from the acceleration regime, we obtain

If the approximations were justified in the above two displays, then this informal argument would lead to a proof of Theorem 4.1. We do this in the following subsection.

2 Rigorous derivation

Here we prove Theorem 4.1. We first state two helper lemmas, which formalize the Taylor approximations (4.4) and (4.6) in the acceleration regime and saturation regime, respectively.

Let $\nu:=\frac{3\rho}{2\sqrt{2}}\approx 2.561$. For all $h\geqslant 0$,

We omit the proofs of these lemmas, since the inequalities are visually obvious from plotting the functions, and can be formally proven in a routine algorithmic way, as they only involve algebraic functions of a single scalar variable. This is done by computing the critical points and using well-known techniques for root isolation; see e.g. .

An appealing consequence of Lemma 4.3 is the inequality $\tau_{2n}\leqslant\tau_{n}^{2}$. We call this the rate monotonicity property of the Silver Stepsize Schedule, since it amounts to the statement that using the $2n$-step schedule is at least as good as using the $n$-step schedule twice.

By (4.1), then Lemma 4.3, then (4.1) again, we have $\tau_{2n}=(1-h_{i+1})^{2}\leqslant(1-h_{i})^{4}=\tau_{n}$. ∎

Here we prove the upper bounds (a.k.a., the convergence rates). The matching lower bounds are conceptually identical and deferred to Appendix A for brevity.

Acceleration regime. Suppose $n\leqslant n^{*}$. Let $i:=\log_{2}n\leqslant i^{*}$. We bound

Above, the first step is by $i$ applications of the lower bound in Lemma 4.2. The second step is because $h_{t}\leqslant\rho^{t}h_{0}$ by $t$ applications of the upper bound in Lemma 4.2. The third step is by summing the geometric series, crudely dropping a positive term, and simplifying $\nu/(\rho\sqrt{2})=3/4$. The fourth step is because $\rho^{i}h_{0}\leqslant\rho^{i^{*}}h_{0}\leqslant 2/3$ by definition of $i^{*}$ and the initialization upper bound $h_{0}\leqslant 2/\kappa$, see (4.2). The final step is by definition of $i=\log_{2}n$ and the initialization lower bound $h_{0}\geqslant 1/\kappa$, see (4.2). This completes the proof since by (4.1),

Saturation regime. Next, suppose $n>n^{*}$. By $n/n^{*}$ applications of Corollary 4.4 and then using the bound on $\tau_{n^{*}}$ proved in the acceleration regime, we have

The proof is complete by using the definition of $n^{*}$ and $i^{*}$ to bound $(n^{*})^{\log_{2}\rho}=\rho^{i^{*}}\geqslant\frac{\kappa}{3\rho}$. ∎

Certificate of the Silver Convergence Rate

Here we prove that the Silver Stepsize Schedule has convergence rate $\tau_{n}$. This is where we establish multi-step descent. For a conceptual overview, we refer the reader to §2.2 for the case of $n=2$; the proof for general $n$ here mirrors that key case, albeit is more technically involved.

Recall from the discussion there that the proof strategy amounts to finding a certificate $\{\lambda_{ij}\}$ for the rate $\tau_{n}$, by which we mean non-negative multipliers $\{\lambda_{ij}\}_{i,j\in\{0,\dots,n-1,*\}}$ such that

See §2.2 for a definition of the co-coercivities $Q_{ij}$. Briefly, these are valid inequalities that generate all possible long-range consistency conditions between the gradients seen along GD’s trajectory.

Our proof builds the $2n$-step certificate by recursively gluing two copies of the $n$-step certificate and adding slight modifications to account for the fact that the $2n$-step Silver Stepsize Schedule $h^{(2n)}$ differs from $[h^{(n)},h^{(n)}]$ in two out of the $2n$ stepsizes. Concretely, this recursive gluing can be understood as creating the $(2n+1)\times(2n+1)$ matrix $\{\lambda_{ij}\}_{i,j\in\{0,\dots,2n-1,*\}}$ from the $(n+1)\times(n+1)$ matrix $\{\sigma_{ij}\}_{i,j\in\{0,\dots,n-1,*\}}$ in three parts: a tensor product which glues together two copies of the $n$-step certificate, a rank-one correction which affects the rows indexed by $i\in\{n-1,2n-1,*\}$, and a sparse correction which affects the $6$ entries $(i,j)$ where $i\neq j\in\{n-1,2n-1,*\}$. See Figure 7.

This recursive gluing is formally stated in Theorem 5.2 below. To most easily state this result, we first isolate a certain property of the sparsity pattern of the multipliers $\lambda_{ij}$ that holds by construction in our recursion. This property is technical and eases the proof.

A collection of weights $\{\lambda_{i,j}\}_{i,j\in\{0,\dots,n-1,*\}}$ satisfies the $*$-sparsity property if $\lambda_{i,*}$ for all $i<n-1$.

Let $\kappa\in(1,2)\cup(2,\infty)$. Suppose $\{\sigma_{ij}\}_{i,j\in\{0,\dots,n-1,*\}}$ satisfies $*$-sparsity and certifies the $n$-step rate, i.e.,

Then there exists $\{\lambda_{ij}\}_{i,j\in\{0,\dots,2n-1,*\}}$ that satisfies $*$-sparsity and certifies the $2n$-step rate, i.e.,

Moreover, this certificate is explicitly given by

where the “gluing component” $\Theta$ is defined as

the “rank-one correction” $\Xi$ is zero except $\{\Xi_{ij}\}_{i\in\{n-1,2n-1,*\},j\in\{n,\dots,2n-2\}}$, and the “sparse correction” $\Delta$ is zero except $\{\Delta_{ij}\}_{i\neq j\in\{n-1,2n-1,*\}}$. The explicit values of $c$, $\Xi$, $\Delta$ are provided in Appendix B.

While the explicit values of $\Xi$ and $\Delta$ are somewhat involved, the key point is that they can be expressed as rational functions in just $z_{n},y_{2n},z_{2n}$, see Remark B.1. Importantly, since $y_{2n},z_{2n}$ are explicit algebraic functions of $z_{n}$ by construction (see §3.1), this turns verifying the claimed identity (5.3) into a straightforward (albeit tedious) algebraic exercise that is rigorously automatable via standard computer algebra techniques .

A few minor remarks. First, for simplicity, Theorem 5.2 assumes $\kappa\neq 2$. This allows us to multiply and divide by $\kappa-2$, which simplifies expressions. The rate for $\kappa=2$ anyways follows immediately from $\kappa=2+\varepsilon$ for $\varepsilon\downarrow 0$. Second, in (5.4) the notational shorthand $i-n$ is understood to be $*$ when $i=*$. Third, when it is said that $\lambda$ satisfies $*$-sparsity, it is understood that this property corresponds to the horizon of length $2n$, i.e., $\lambda_{*,i}=0$ for all $i<2n-1$.

Theorem 5.2 immediately implies the convergence rate (1.4) in our main result Theorem 1.1.

The base case of $n=1$ is the classical analysis of GD; see, e.g., [5, Chapter 8] for a proof in this language of co-coercivities.One can also use Theorem 2.2 to take $n=2$ as the base case. Then this paper’s proof is fully self-contained. The convergence rate is the textbook unaccelerated rate $\tau_{1}=(\tfrac{\kappa-1}{\kappa+1})^{2}$. By induction, Theorem 2.2 implies that $\tau_{n}$ is a valid convergence rate for the $n$-step Silver Stepsize Schedule, for all $n$ that are powers of $2$. ∎

Below, in §5.1, we express the components of the recursively glued certificate as succinct quadratic forms, and then in §5.2, we use this to prove Theorem 5.2.

Proving Theorem 5.2 requires establishing that $\lambda$ satisfies the identity (5.3). Ignoring presently the linear form in the function values (that term is much simpler and addressed in §5.2), this amounts to showing equality of two quadratic forms. Naïvely, this requires checking equality of all coefficients of these quadratic forms—which is painstaking since these are quadratics in all the GD iterates $x_{0},\dots,x_{2n-1},x^{*}$ and their corresponding gradients $g_{0},\dots,g_{2n-1},g^{*}$, and moreover are defined over the ideal generated by the GD equations $x_{t+1}=x_{t}-\alpha_{t}g_{t}$. A key observation that removes much of this labor is that the quadratic forms in our recursive certificate have rank at most $4$. In fact, these quadratic forms are only in the four variables $x_{n-1},g_{n-1},x_{2n-1},g_{2n-1}$. This reduces the number of coefficients to be checked from $\Theta(n^{2})$ to a constant number: $10$.

This observation is formalized in the following lemma, which expresses the quadratic forms via coefficient matrices as this is convenient for book-keeping. For brevity, just as in Theorem 5.2, the explicit values of these matrices are deferred to the Appendix, but the key point is that each entry can be expressed a rational function of just $z_{n},y_{2n},z_{2n}$, see Remark B.1. To isolate the quadratic form component of the co-coercivities, let $P_{ij}$ denote $Q_{ij}$ without its linear component $f_{i}-f_{j}$, i.e.,

Consider the setup of Theorem 5.2, let $v:=[x_{n-1},g_{n-1},x_{2n-1},g_{2n-1}]^{T}$, and let $E$, $S$, $L$ be the $4\times 4$ matrices defined in Appendix B.4.

Gluing error: $\tau_{2n}\|x_{0}\|^{2}-\|x_{2n}\|^{2}-\sum_{i,j\in\{0,\dots,2n-1,*\}}\Theta_{ij}P_{ij}=\langle E,vv^{T}\rangle$

Sparse correction: $\sum_{ij}\Delta_{ij}P_{ij}=\langle S,vv^{T}\rangle$

Rank-one correction: $\sum_{ij}\Xi_{ij}P_{ij}=\langle L,vv^{T}\rangle$

For brevity, we defer the proof of the sparse and low-rank corrections to Appendix. However, we provide the proof of the gluing error here to provide intuition for why these quadratic forms have constant rank rather than the a priori upper bound of $\Theta(n)$. In particular, the proof shows how the low rank arises from the recursive construction of the Silver Stepsize Schedule that creates $h^{(2n)}$ from $h^{(n)}$, modulo only changing the $n$-th and $2n$-th stepsizes (each increases the rank by $2$).

2 Certificate verification

The non-negativity and $*$-sparsity properties of $\lambda$ are direct from the explicit values of $\lambda$; details in Appendix B.3. It therefore suffices to check the rate certificate (5.3). By definition of the co-coercivity $Q_{ij}$, this certificate has two components: a linear form in $\{f_{i}\}_{i\in\{0,\dots,2n-1,*\}}$ and a quadratic form in $\{x_{i},g_{i}\}_{i\in\{0,\dots,2n-1,*\}}$. We check these two components below.

where $E,S,L$ are the matrices defined in Appendix B.4. This amounts to checking the $10$ entries on or above the diagonal of these $4\times 4$ matrices—elements below the diagonal need not be checked as the matrices are symmetric. By Lemma B.3, these entries can be expressed as rational functions in $z_{n},y_{2n},z_{2n}$, which are polynomially related via (3.1). Therefore, checking that these $10$ entries vanish amounts to checking that certain polynomials vanish modulo an associated ideal. This verification is rigorously automatable using standard techniques from computational algebraic geometry such as Gröbner bases; see e.g. . A simple script for Mathematica (or other computer algebra systems) that verifies these identities is available at the URL given in the references . We emphasize that this is purely in the interest of brevity: verifying these identities can be done by hand, as it just amounts to straightforward (albeit tedious) algebraic cancellations.

Recall that each $Q_{ij}$ contributes $2(M-m)(f_{i}-f_{j})$. Thus, in order to show that all function values vanish in $\sum_{ij}\lambda_{ij}Q_{ij}$, it is equivalent to show that

That is, the $j$-th row and column sums of $\lambda$ must match, for all $j$. We call refer to these identities as netflow constraints. Since $\sigma$ is a valid certificate, it satisfies the netflow constraints $\sum_{j}\sigma_{ij}=\sum_{j}\sigma_{ji}$ for all $j\in\{0,\dots,n-1,*\}$. Thus, by construction of $\Theta$ from $\sigma$, it follows that $\Theta$ satisfies the netflow constraints $\sum_{j}\Theta_{ij}=\sum_{j}\Theta_{ji}$ for all $i\in\{0,\dots,2n-1,*\}$. Therefore, in order to prove (5.7), it is equivalent to prove the netflow constraints for $\Xi+\Delta$; that is,

The cases $i\in\{0,\dots,n-2\}$ are trivial since on these rows and columns, $\Xi$ and $\Delta$ are identically zero. The cases $i\in\{n,\dots,2n-2\}$ are similarly trivial because on these rows and columns, $\Delta$ is identically zero and $\sum_{j}(\Xi_{ji}-\Xi_{ij})=\Xi_{n-1,i}+\Xi_{2n-1,i}+\Xi_{*,i}=0$ by construction of $\Xi$. It remains only to prove (5.8) for $i\in\{n-1,2n-1,*\}$. By the sparsity patterns of $\Xi$ and $\Delta$, this amounts to showing

By Lemma B.3, these quantities can be expressed as rational functions in $z_{n},y_{2n},z_{2n}$, which are polynomially related via (3.1). Therefore, checking that the three quantities vanish in (5.9) amounts to checking that three polynomials vanish modulo an ideal. As mentioned above, this verification is rigorously automatable using standard computational algebra techniques; see the same URL for a simple script implementing this computation.

Future work

This work removes a key stumbling block in previous analyses of optimization algorithms: we show that directly analyzing multi-step descent can lead to improved convergence analyses. This general principle opens up a number of directions in both the design and analysis of optimization algorithms. We list a few here.

Do these techniques extend to stochastic settings where gradients are noisy or only computed approximately? This is motivated by modern machine learning settings such as empirical risk minimization. What about constrained settings where projections are interleaved? Or other settings where one uses coordinate descent, proximal steps, etc.? What about second-order methods such as Newton or Interior Point methods? The modern optimization toolbox is broad, and the algorithmic opportunity of faster multi-step descent that we establish warrants re-investigating many existing algorithms that use greedy analyses.

While our techniques extend to the convex setting (see §1.1.4), it is less clear if extensions to non-convex settings are also possible. In particular, can one prove accelerated rates for converging to an stationary point? Could this justify empirical phenomena observed in neural network training such as super-acceleration from cyclic stepsize schedules ?

Is faster convergence possible if the objective function is more structured? One well-motivated direction here is low-dimensional objective functions. It is known that faster asymptotic convergence is possible if the dimension $d$ is fixed and the number of iterations $n\to\infty$, e.g., via cutting planes. Recent work has shown that certain momentum-based modifications to GD can also surpass standard lower bounds for sufficiently large $n$ . Do such phenomena extend to GD with dynamic stepsizes? Altschuler’s thesis [5, Chapter 6] proved that for univariate convex functions (or more generally, separable convex functions), GD achieves the fully accelerated rate $\Theta(\sqrt{\kappa}\log 1/\varepsilon)$ via a certain (random) dynamic choices of stepsizes. Does this extend to higher dimension? What is the fundamental trade-off between $n$, $d$, and the convergence rate?

The Silver Stepsize Schedule periodically uses extremely large step sizes, which are overly aggressive in isolation, but effective when combined with other short steps. It is natural to wonder if this dependence between iterations makes such strategies more sensitive to model misspecification, noisy gradients, inexact arithmetic, or other considerations in practical implementations. We expect this may occur, since it does for other accelerated algorithms, see e.g., .

JMA is grateful to his friends for their patience over the past seven years as he continually complained about how hard this problem was.

Appendix A Deferred details for §4

Here we prove the matching lower bounds in Theorem 4.1.

Above, the first step is by (4.1). The third step is by the upper bound in Lemma 4.2 and the initialization upper bound $h_{0}\leqslant 2/\kappa$ from (4.2). The fourth step is by definition of $i=\log_{2}n$. It remains to argue the second step. This is due to the elementary inequality $1-h\geqslant\exp(-2h)$ which holds for $h\in(0,2/3)$ and is applicable since

Here, we used same upper bound in Lemma 4.2, the same initialization upper bound $h_{0}\leqslant 2/\kappa$, and, critically, the fact that $i\leqslant i^{*}$ since we are in the acceleration regime.

where the first and third steps are by (4.1), the second step is by the lower bound in Lemma 4.3, and the final step is because $\tau_{n}\leqslant\tau_{n^{*}}\leqslant\exp(-1/3)$ by the rate monotonicity in Corollary 4.4 and the upper bound we proved for $\tau_{n^{*}}$ in the acceleration regime. By unrolling this recursion from $n$ to $n^{*}$, continuing to crudely bound constants for simplicity of exposition, and then plugging in the lower bound $\tau_{n^{*}}\geqslant\exp(-8)$ from the acceleration regime, we conclude

Appendix B Deferred details for §5

Here we provide the deferred details for the proof of Theorem 5.2. See §5 for a proof overview. Three remarks on notation in this Appendix. First, after a possible translation of both $f$ and $x_{0}$, we assume without loss of generality that $x^{*}=0$. Second, it is convenient to define the shorthand

where $\alpha_{0},\dots,\alpha_{2n-1}$ index the $2n$-length Silver Stepsize Schedule $h^{(2n)}$. Third, as is standard convention, products over the empty set such as $\prod_{t=n}^{n-1}q_{t}$ have value $1$.

We begin by explicitly stating the correction components used in the recursive gluing. It is convenient to provide two equivalent versions of these expressions. In the first version (Definition B.2), the low-rank correction $\Xi$ is explicitly defined for every entry, and the sparse correction $\Delta$ is typically defined as something minus the gluing component $\Theta$. Such expressions for $\Delta$ are convenient for computing the final certificate $\lambda$ because $\Theta$ cancels. In the second version (Lemma B.3), $\Xi$ is given only through its row sums (which is the only way $\Xi$ is needed for the proof of Theorem 5.2), and $\Delta$ is given via explicit expressions for the subtracted entries of $\Theta$. The key benefit of this second version is that it provides explicit expressions in terms of $z_{n},y_{2n},z_{2n}$ for all quantities required in the proof of Theorem 5.2. For easy recall, we isolate this important fact in the following remark.

While the expressions in Definition B.2 are somewhat involved, the key point is that all the quantities that are required in the proofs in §5 can be expressed as rational functions in $z_{n},y_{2n},z_{2n}$. This is Lemma B.3. (Note that $\tau_{n},\tau_{2n}$ are by definition rational functions of $z_{n},z_{2n}$, and also note that $\Xi$ is needed only through its row sums.) The upshot is that since $z_{n},y_{2n},z_{2n}$ are polynomially related by construction (see §3.1), these expressions make the rate verification a routine and rigorously automatable algebraic exercise.

The “low-rank correction” $\Xi$ is defined to be zero except that for all $j\in\{n,\dots,2n-2\}$,

$\Xi_{n-1,j}:=\phi/\prod_{t=n}^{j-1}q_{t}$

$\Xi_{2n-1,j}:=r\phi/\prod_{t=n}^{j-1}q_{t}$

$\Xi_{*,j}:=-(1+r)\phi/\prod_{t=n}^{j-1}q_{t}$

The “sparse correction” $\Delta$ is zero everywhere except for the following entries:

$\Delta_{n-1,2n-1}:=\phi\frac{\kappa-2}{\kappa(1-z_{n})}$

$\Delta_{2n-1,n-1}:=\phi(\kappa-2)\frac{y_{2n}}{1-z_{n}}$

$\Delta_{*,n-1}:=\tau_{2n}\frac{1+\kappa y_{2n}}{1-z_{n}}-\frac{\tau_{2n}}{\tau_{n}}\sigma_{*,n-1}$

$\Delta_{*,2n-1}:=\frac{1+(\kappa-1)z_{2n}+\kappa z_{2n}^{2}}{(1+z_{2n})^{2}}-c\sigma_{*,n-1}$

$\Delta_{n-1,*}:=-\frac{\tau_{2n}}{\tau_{n}}\sigma_{n-1,*}$

$\Delta_{2n-1,*}:=\frac{2\kappa z_{2n}}{(1+z_{2n})^{2}}-c\sigma_{n-1,*}$

In the above, we used as shorthand the following special values:

$c:=\frac{\tau_{2n}}{\tau_{n}}\left[r+(1+r)\left(\frac{z_{2n}+z_{n}}{z_{2n}-z_{n}}\right)\right]$

$\phi:=\tau_{2n}\frac{\kappa}{\kappa-2}\left(\frac{z_{2n}+z_{n}}{z_{2n}-z_{n}}\right)$

We now state the alternative expressions discussed in Remark B.1.

$\Delta_{n-1,2n-1}=\frac{\tau_{2n}}{1-z_{n}}\left(\frac{z_{2n}+z_{n}}{z_{2n}-z_{n}}\right)$

$\Delta_{2n-1,n-1}=\frac{\kappa y_{2n}\tau_{2n}}{1-z_{n}}\left(\frac{z_{2n}+z_{n}}{z_{2n}-z_{n}}\right)$

$\Delta_{*,n-1}=\frac{\tau_{2n}}{1-z_{n}}(1+\kappa y_{2n})-\tau_{2n}\frac{1+(\kappa-1)z_{n}+\kappa z_{n}^{2}}{(1-z_{n})^{2}}$

$\Delta_{*,2n-1}=\tau_{2n}\frac{1+(\kappa-1)z_{2n}+\kappa z_{2n}^{2}}{(1-z_{2n})^{2}}-c\tau_{n}\frac{1+(\kappa-1)z_{n}+\kappa z_{n}^{2}}{(1-z_{n})^{2}}$

$\Delta_{n-1,*}=-\frac{2\kappa z_{n}\tau_{2n}}{(1-z_{n})^{2}}$

$\Delta_{2n-1,*}=\frac{2\kappa z_{2n}\tau_{2n}}{(1-z_{2n})^{2}}-c\frac{2\kappa z_{n}\tau_{n}}{(1-z_{n})^{2}}$

$\sum_{j=n}^{2n-2}\Xi_{n-1,j}=\frac{1}{r}\sum_{j=n}^{2n-2}\Xi_{2n-1,j}=-\frac{1}{1+r}\sum_{j=n}^{2n-2}\Xi_{*,j}=\tau_{2n}\left(\frac{\kappa z_{n}-1}{1-z_{n}}\right)\left(\frac{z_{2n}+z_{n}}{z_{2n}-z_{n}}\right)$ and is for $n=1,2$