Source-linked AI summary
Lower Bounds for Anytime Acceleration of Gradient Descent
Chung-En Tsai, Ilyas Fatkhullin, Liang Zhang, Niao He
TL;DR
The optimal anytime convergence rates of gradient descent with arbitrary positive stepsizes remain incompletely known, despite faster non-anytime rates and the classical Ω(n^-2) first-order lower bound. The paper analyzes gradient descent on quadratic and asymmetric Huber functions to upper-bound the number and magnitude of large stepsizes. No positive stepsize schedule achieves o(n^-4/3) anytime convergence for R_n or o(n^-1) for G_n; the latter matches the O(n^-1) upper bound.
Problem
The optimal anytime convergence rates of gradient descent with arbitrary positive stepsizes remain incompletely known, despite faster non-anytime rates and the classical Ω(n^-2) first-order lower bound.
Source: §1 · p. 2, §1.2 · p. 4, §1.3 · p. 5Method
The paper analyzes gradient descent on quadratic and asymmetric Huber functions to upper-bound the number and magnitude of large stepsizes.
Source: §6 · pp. 21–22Results
No positive stepsize schedule achieves o(n^-4/3) anytime convergence for R_n or o(n^-1) for G_n; the latter matches the O(n^-1) upper bound.
Source: §1.3 · p. 6, §6 · p. 21Takeaways & Limitations
The results show that the non-anytime O(n−1.271) rate is unachievable in the anytime setting, quantifying the price of not knowing the stopping time in advance.
Source: §1.3 · p. 6The R_n lower bound does not determine the optimal anytime rate, which remains between n^-1.334 and n^-1.119.
Source: §6 · p. 22
Abstract
from arXiv · showhide
Recent work suggests that the convergence rate of gradient descent (GD) in smooth convex optimization can be significantly improved by employing large stepsizes that may violate the descent property. In particular, if the total number of iterations $n$ is given, an $O(n^{-1.271})$ convergence rate can be achieved for both function value and squared gradient norm minimization. On the other hand, in the setting of anytime convergence, where $n$ is not known in advance, the best known rates of GD are much slower: $O(n^{-1.119})$ for function value minimization and $O(n^{-1})$ for squared gradient norm minimization. It remains open whether any of these upper bounds can be improved, as they are far from the classical $Ω(n^{-2})$ lower bound for any first-order method. In this work, we establish two lower bounds on the anytime convergence of GD. We show that no positive stepsize schedule can achieve an $o(n^{-1.334})$ anytime rate for function value minimization, nor an $o(n^{-1})$ anytime rate for squared gradient norm minimization. The key ingredients of our analysis are novel upper bounds on the number and the magnitude of large stepsizes, derived by analyzing GD on quadratic functions and variants of Huber functions. Our work provides the first lower bounds for the COLT 2024 open problem posed by Kornowski and Shamir regarding the optimal anytime convergence rates of GD.
1 Introduction
This work studies anytime convergence of gradient descent with arbitrary positive, non-adaptive stepsizes and establishes lower bounds that constrain acceleration for function-value and squared-gradient objectives.
1 Introduction
- Anytime convergence requires one schedule to work for every n, whereas non-anytime schedules may depend on the prescribed stopping time.This distinction creates different optimal rates, including an O(n^-1.271) non-anytime rate for both R_n and G_n.Source: §1 · p. 3, §1.1 · p. 3
1.1 Upper Bounds for GD
- Acceleration relies on large stepsizes exceeding 2/L, which may violate descent; in the silver schedule, one fourth exceed 2/L and the largest scales as Θ(n^1.271/L).The paper studies the number and magnitude of such stepsizes because they constrain possible progress.Source: §1.1 · p. 3
1.2 Lower Bounds for GD
- The lower bounds apply to arbitrary positive stepsize schedules, unlike prior bounds restricted to classes such as basic and composable schedules or the silver schedule.The results therefore cover every positive, non-adaptive schedule considered in the paper.Source: §1.2 · pp. 4–5
1.3 Contributions and Main Results
- The analysis derives upper bounds on the number and magnitude of large stepsizes using quadratic and asymmetric Huber functions, yielding the stated anytime lower bounds.These bounds provide necessary conditions for fast-converging schedules.Source: §1.3 · p. 5, §1.4 · p. 6
- No positive stepsize schedule achieves an o(n^-4/3) anytime rate for R_n, while the best known upper bound is approximately O(n^-1.119).The lower and upper bounds leave the optimal anytime rate for function-value minimization between n^-1.334 and n^-1.119.Source: §1.3 · p. 5
- No positive stepsize schedule achieves an o(n^-1) anytime rate for G_n, matching the O(n^-1) rate attained by small constant stepsizes.Thus, the anytime rate for squared-gradient-norm minimization is characterized up to matching upper and lower bounds.Source: §1.3 · pp. 5–6
2 GD on Convex Quadratic Functions
The quadratic-function analysis reduces GD’s worst-case behavior to polynomial bounds and uses them to control how many large stepsizes can occur. These controls yield improved bounds on the total stepsize magnitude, which is central to the later lower bounds.
Quadratic reduction
- GD on convex quadratics reduces convergence analysis to bounding the norm of a polynomial generated by the stepsizes.The resulting quantity Q_n lower-bounds both function-value and squared-gradient-norm rates.Source: §2 · p. 8
- Q_n(η) ≥ 1/[4(1 + 2η_1:n)] links the convergence rate directly to the reciprocal of the cumulative stepsizes.This bound also shows that achieving o(n^-1) requires unbounded stepsizes.Source: §2.1 · pp. 8–9
Number of large stepsizes
- N_n(t), the number of first-n stepsizes exceeding threshold t, is bounded more tightly than the trivial count n.When Q_n(η) = O(poly(n)), the bound simplifies to N_n(t) = O(log n + n/√t).Source: §2.2 · pp. 9–10
Proof strategy
- The proof controls the polynomial separately below and above a threshold, using the exponential growth caused by many factors associated with stepsizes larger than that threshold.This explains why a small Q_n limits the number of large stepsizes.Source: §2.2 · p. 10
Sum of stepsizes
- The large-stepsize count bound implies η_1:n = O(√(nM_n) + M_n log n), improving the trivial η_1:n ≤ nM_n.For the silver schedule, this changes the resulting upper bound from O(n^2.271) to O(n^1.636).Source: §2.3 · pp. 12–13
3 GD on Asymmetric Huber Functions
The asymmetric Huber construction bounds the damage caused by an unusually large stepsize at any iteration. It places GD in a high-curvature quadratic region for that step and in zero-curvature linear regions otherwise.
Asymmetric Huber construction
- Asymmetric Huber functions are smooth and convex, with a quadratic region between linear regions; equal parameters recover the standard Huber function.The construction uses parameters ε and δ to control the two sides asymmetrically.Source: §3 · p. 14
Construction intuition
- A large η_m causes GD to overshoot in the quadratic region, while the linear regions allow only limited progress during the other updates.The construction therefore tests whether later stepsizes can compensate for the overshoot.Source: §3 · p. 14, §3.1 · p. 15
Lower bounds from Huber functions
- For any η_m > 1, Lemma 3.1 gives lower bounds on both R_n and G_n that grow with (η_m − 1)^2 and decay with the remaining stepsizes.The bounds differ between the two metrics and depend on the ordering of the stepsizes.Source: §3.1 · p. 15
Trajectory analysis
- The construction places the iterate at the quadratic-region boundary before the large step and sends it to the opposite linear region afterward.Choosing δ from the preceding stepsizes ensures x_m = δ, while the large update gives x_{m+1} = −(η_m − 1)δ.Source: §3.1 · pp. 15–16
4 Proofs of Main Results
The main proofs combine cumulative-stepsize lower bounds with the quadratic and asymmetric-Huber controls. They rule out faster-than-n^-4/3 anytime convergence for function values and faster-than-n^-1 anytime convergence for squared gradient norms.
Comparison of metrics
- The G_n lower bound is stronger than the R_n lower bound for the same schedule because η_1:n−1 > 0 makes the former bound larger.The proof obtains this comparison by setting the large-step index to m = n in Lemma 3.1.Source: §4 · p. 17
Function-value lower bound
- No positive stepsize schedule satisfies R_n(η) = o(n^-4/3) for anytime function-value convergence.Assuming such a rate forces incompatible lower and upper bounds on cumulative stepsizes, yielding a contradiction.Source: §4.1 · pp. 17–18
Squared-gradient lower bound
- For squared gradient norms, assuming G_n(η) = o(n^-1) similarly contradicts the cumulative-stepsize and asymmetric-Huber bounds.The contradiction appears as O(√n) ≥ ω(√n).Source: §4.2 · p. 18
5 Discussion
The discussion derives necessary stepsize-growth conditions, shows the large-stepsize-count bound is nearly tight, and finds numerical evidence against extending the technique to non-anytime lower bounds beyond n^-2.
5.1 Necessary Conditions for Fast Stepsize Schedules
- η_n = Θ(n^2/3) and η_1:n = Θ(n^4/3) are necessary for a hypothetical O(n^-4/3) anytime rate for R_n.The argument combines lower and upper bounds on cumulative and maximal stepsizes.Source: §5.1 · p. 19
5.2 Tightness of Lemma 2.2
- Stepsize schedules can match the upper bound on the number of large stepsizes up to logarithmic terms, making Lemma 2.2 nearly tight.The construction achieves the bound up to an O(log n) additive term and constant factors.Source: §5.2 · pp. 19–20
5.3 Non-Anytime Lower Bounds
- For the constructed permutation η(n), all evaluated quadratic and asymmetric-Huber lower bounds decay roughly as O(n^-2), despite the schedule being non-anytime.The schedule permutes Chebyshev-based stepsizes around the largest step and satisfies Q_n(η(n)) = O(n^-2).Source: §5.3 · pp. 20–21
- The numerical construction suggests that proving an ω(n^-2) non-anytime lower bound requires explaining why every permutation of the Chebyshev stepsizes fails.The quadratic lower bound alone is insufficient, and combining it with Lemma 3.1 remains insufficient for this goal.Source: §5.3 · pp. 20–21
5.4 Beyond Last Iterate and Positive Stepsizes
- The results are restricted to last-iterate GD with positive, non-adaptive stepsizes; averaged iterates, negative stepsizes, and adaptive rules remain outside scope.The paper leaves these extensions for future work.Source: §5.4 · p. 21
6 Conclusions
The paper proves anytime lower bounds for GD and identifies both their technical basis and remaining gaps. It also reports numerical evidence that its approach does not establish a stronger non-anytime lower bound.
6 Conclusions
- No positive stepsize schedule can achieve o(n^-4/3) anytime convergence for R_n or o(n^-1) anytime convergence for G_n.These are the paper’s two principal lower bounds.Source: §6 · p. 21
- The proofs use upper bounds on the number and magnitude of large stepsizes derived from quadratic and asymmetric Huber functions.These bounds also provide necessary conditions for designing fast-converging schedules.Source: §6 · pp. 21–22
- Figure 4 evaluates the quadratic and asymmetric Huber lower bounds on schedule (14) using maxima over specified points and valid m values.The figure’s calculations support the discussion of the non-anytime construction.Source: Figure 4 · p. 22
- The optimal anytime rate for R_n remains open, with current bounds lying between n^-1.334 and n^-1.119.The paper also leaves an ω(n^-2) non-anytime lower bound as an open problem.Source: §6 · p. 22
A Best Known Convergence Rates of GD and First-Order Methods
The tables summarize best known convergence rates for GD and first-order methods in smooth convex optimization. The only setting with matching upper and lower bounds is anytime convergence for G_n.
A Best Known Convergence Rates of GD and First-Order Methods
- Anytime convergence for G_n is the only listed setting where upper and lower bounds coincide for GD with arbitrary positive stepsizes.Table 1 summarizes the corresponding GD rates.Source: Table 1 · p. 26
- Upper and lower bounds coincide in every listed first-order-method setting except anytime convergence for G_n.Table 2 provides the broader comparison across first-order methods.Source: Table 2 · p. 26
B Helper Lemmas
The helper lemmas connect GD on quadratics to polynomial approximation, Chebyshev polynomials, derivative bounds, and measure-theoretic layer-cake representations used in the analysis.
B Helper Lemmas
- Q_n(η) is represented as the infinity norm of a degree-n polynomial, connecting quadratic optimization to polynomial approximation theory.The polynomial is formed from the factors (1 − η_kλ)^2.Source: B Helper Lemmas · p. 27
- Chebyshev polynomials provide the minimum-norm polynomial characterization used to analyze Q_n.The n-th Chebyshev polynomial is defined piecewise and has a minimum-infinity-norm property.Source: B Helper Lemmas · pp. 27–28
- A shifted Markov brothers’ inequality bounds the derivative norm of a polynomial by its norm on the relevant interval.The proof rescales the polynomial to apply the standard inequality.Source: B Helper Lemmas · p. 27
- The appendix combines polynomial norm and derivative estimates into a lemma for polynomials satisfying p′(0) = 1.The resulting statement is proved by combining the preceding lemmas.Source: B Helper Lemmas · p. 28
- The layer-cake representation expresses the integral of a nonnegative measurable function through the measures of its superlevel sets.This measure-theoretic lemma is introduced as an auxiliary tool.Source: B Helper Lemmas · p. 28