PaperlayerView exact revision on arXiv

Source-linked AI summary

Silver Rate Is (Almost) Optimal for Gradient Descent

Yuhan Ye, Kaizhao Liu

arXiv:2609.09152v2math.OCcs.LG

TL;DR

The paper asks how far predetermined stepsizes can accelerate gradient descent, given that known upper bounds outpace available lower bounds. It bends gradient directions during local updates to construct stronger lower bounds, which nearly match the upper bounds in both non-anytime and anytime settings.

  • Problem

    Whether lower bounds for GD with predetermined stepsizes can be strengthened toward the known accelerated upper bounds remained open.

    Source: §1 · p. 3

  • Method

    The lower-bound construction bends the gradient direction during local updates.

    Source: §2 · p. 7, §5 · p. 13

  • Results

    The lower bounds for predetermined nonnegative stepsizes match the upper bounds in both non-anytime and anytime settings up to subpolynomial terms.

    Source: §5 · p. 13

  • Takeaways & Limitations

    The results establish almost-tight lower bounds for GD with predetermined nonnegative stepsizes in both settings.

    Source: §5 · p. 13

    Extending these lower bounds to schedules that may include negative stepsizes remains open.

    Source: §5 · p. 13

Abstract

from arXiv · show

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})$, we prove an $\Omega\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)$ non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error $\Omega\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right)$. Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.

1 Introduction

Predetermined stepsizes accelerate gradient descent beyond its standard O(n^-1) rate, but it remained open whether lower bounds could approach the known silver-schedule upper bounds. For nonnegative schedules, the paper identifies the optimal polynomial convergence exponents in both finite-horizon and anytime settings.

1 Introduction

  • The silver schedule achieves O(n^-p_sil), while a single anytime schedule achieves O(n^-p_any) at every stopping time; whether lower bounds could approach these rates remained open.Here p_sil = log2(1 + sqrt(2)) and p_any = 2p_sil/(1 + p_sil).Source: §1 · p. 3

1.1 Main Results

  • For nonnegative schedules, the results identify the optimal polynomial convergence exponents in both non-anytime and anytime settings, matching the corresponding upper bounds up to subpolynomial terms.This confirms the conjecture that the silver exponent is optimal.Source: §1.1 · pp. 3–4

1.2 Additional Related Work

  • Related work studies acceleration through time-varying stepsizes while leaving the GD update unchanged, alongside bounds and extensions for particular schedules, objectives, and settings.The silver-rate guarantee was extended to proximal and projected GD, and an anytime schedule achieved O(n^-1.119) at every stopping time.Source: §1.2 · pp. 4–5

2 Motivation and Technical Overview

The technical overview improves a checkpoint-based hard-function construction by turning gradient directions between selected steps, reducing the transfer-bound coefficient toward 1. Recursive checkpoint analysis then yields non-anytime and anytime lower bounds approaching the silver-rate exponents.

Prior construction

  • Jung et al.’s construction uses selected steps to activate successive components and obtains an Ω(n^-log2(1+√3)) non-anytime lower bound [2026, Section 3].The selected step raises the next coordinate above its activation threshold while later components remain inactive.Source: §2 · p. 6

The bottleneck and innovation

  • The earlier transfer ratio has denominator c(2 + s_i), with c = 2, because intervening updates decrease the coordinate difference that keeps a component active.The proposed two-coordinate hard function changes gradient direction during those updates so c can approach 1.Source: §2 · p. 6

Switching the gradient direction

  • The local gradient is chosen on a circular arc and the two-coordinate GD trajectory is constructed backward from the selected update.The backward recursion reads the GD update in reverse; as the gradient reaches (c,0), earlier gradients remain horizontal.Source: §2 · p. 7

Assembling the hard function

  • Adjacent-coordinate components are assembled into a finite maximum of affine functions whose Moreau envelope is convex, 1-smooth, and has the constructed trajectory’s gradients.The next component’s activation level keeps the previous component inactive after its selected step.Source: §2 · pp. 7–8

The bottleneck and innovation

  • Reducing the coefficient of the intervening-stepsize term from 2 toward 1 improves the checkpoint transfer bound toward the silver exponent.The construction adds an εb_i correction and constants depending on ε and γ.Source: §2 · pp. 6, 8

From the construction to the lower bounds

  • Checkpoint minimization and recursive bounds handle the εb_i correction, yielding non-anytime lower bounds for every p > p_sil and the refined Theorem 1.1.For anytime schedules, comparison at horizons where the last step is the largest so far gives exponent 2p/(1 + p) infinitely often.Source: §2 · p. 8

3 (Almost) Tight Non-Anytime Lower Bound

The section derives a nearly silver-rate lower bound for every nonnegative finite schedule. It builds a chained smooth hard instance and controls the checkpoint recursion to make the bound uniform over schedules.

3.1 Proof of Lemma 2.2

  • A backward-built trajectory on an arc yields a two-coordinate convex 1-smooth function, whose final step transfers height to the next component.The local construction uses a gradient direction that can change during the intervening updates.Source: §3.1 · p. 9
  • The hard objective chains scaled two-coordinate components with a final one-dimensional Huber function; zero regions keep components inactive outside their turns.Each coordinate appears in at most two 1-smooth terms, making the full objective 1-smooth after scaling.Source: §3.1 · pp. 9–10

3.2 Proof of Theorem 1.1

  • For every nonnegative finite schedule, Theorem 1.1 gives a uniform lower bound approaching the silver rate, with exponent losses of order sqrt(log n loglog n).The proof chooses parameters so the coefficient of the accumulated step sizes approaches 1.Source: §3.2 · pp. 10, 13
  • The proof minimizes a checkpoint functional for each schedule, then bounds its supremum recursively by splitting checkpoint sets at positive steps.The additional εb_i term shifts shorter subproblems and is retained in the splitting inequality rather than absorbed into a schedule-independent constant.Source: §3.2 · pp. 10–12

4 (Almost) Tight Anytime Lower Bound

The anytime proof uses record times, comparing the total stepsize with the largest step seen so far. Its main step is a record-time estimate under stated size conditions.

4 (Almost) Tight Anytime Lower Bound

  • The proof follows a record-time approach, comparing the total stepsize with the largest step seen so far.A horizon n is a record time when h_n equals M_n.Source: §4 · p. 13
  • Lemma 4.1 provides the main estimate for record times when M_n ≥ B0 and r_n ≤ r0,p, for p in (p_sil, p_sil + 1/10].The lemma asserts the estimate for every p in that interval, with constants depending on p.Source: §4 · p. 13

5 Concluding Remarks

The paper's lower bounds match the corresponding upper bounds in both anytime and non-anytime settings up to subpolynomial terms. The authors identify bending the gradient direction during local updates as the key innovation and describe remaining open questions.

5 Concluding Remarks

  • The lower bounds match the upper bounds in both settings up to subpolynomial terms.The authors identify bending the gradient direction during local updates as the key innovation.Source: §5 · p. 13
  • Whether the lower and upper bounds can be matched for schedules allowing negative stepsizes remains open.The authors report that extending their lower bounds to negative stepsizes remains open, although they believe their approach may be adapted.Source: §5 · p. 13
  • The authors also leave open whether the loglog n/log n losses in the exponents can be reduced or removed.Source: §5 · p. 14

AI Disclosure

The authors report that interaction with ChatGPT-6 Astra Ultra helped shape a smooth convex hard function with a rotating local gradient, combined with a refinement of Jung et al.’s recursive analysis. The accompanying proof constructs a trajectory backward and verifies its projection and coordinate bounds.

AI Disclosure

  • The authors say ChatGPT-6 Astra Ultra helped design a smooth convex hard function whose local gradient rotates along a circular arc, with a refinement of Jung et al.’s recursive analysis.They trace the difference from Jung et al.’s exponent to a factor 2 in that work’s local transfer estimate.Source: AI Disclosure · p. 14

A Proofs for the Hard-Function Construction

  • The Moreau envelope of a proper, closed, convex function is finite, convex, continuously differentiable, and has a 1-Lipschitz gradient.Its gradient equals x − prox_g(x); when g is nonnegative, the envelope is nonnegative and has the same zero set.Source: A Proofs for the Hard-Function… · p. 17

A.1 Proof of Lemma 3.1

  • The construction uses v(0) = (c,0) and v(1) = (ε,−1), with ε ≤ p(q) ≤ c and q p(q) ≤ 1.When the threshold condition holds at an index, it also holds at every earlier index, where the construction selects v_i = (c,0).Source: §A.1 · pp. 17, 19
  • The backward construction chooses each preceding gradient by a thresholded rule, then proves by induction that it is the projection of the preceding iterate onto K.The induction also maintains the coordinate bounds; Figure 4 illustrates the similar shaded triangles with scale factor α_j.Source: §A.1 · pp. 17–19, Figure 4 · p. 18

A.2 Proof of Lemma 3.2

The proof uses a scaled convex hull and its Moreau envelope to build a nonnegative, convex, 1-smooth objective. It tracks how prescribed updates move the iterate and identifies a region where the objective vanishes.

A.2 Proof of Lemma 3.2

  • The constructed objective f is nonnegative, convex, and 1-smooth, using the finite convex hull of the constructed gradients and a scaled Moreau envelope.The hull contains every v_j and is contained in K; each v_j remains the projection of r_j onto the smaller set.Source: §A.2 · p. 21
  • The prescribed updates take the iterate to (U,Y + G) at the final step, while its first coordinate stays at least U and its second lies in [0,Y] beforehand.Just before the final step, the gradient is ρ(ε,−1).Source: §A.2 · p. 21
  • The objective vanishes on the region {z1 ≤ 0, z2 ≥ 0}, where every affine piece is nonpositive.The proof also uses q ≤ p/ε and b ≥ 1 + ε^-2 to establish this zero region.Source: §A.2 · p. 22

A.3 Proof of Lemma 2.2

The proof assembles two-coordinate components and a terminal Huber term into a convex, nonnegative, 1-smooth objective. It verifies the prescribed gradient-descent trajectory and derives a final-loss bound.

A.3 Proof of Lemma 2.2

  • The assembled objective F is convex and nonnegative, has minimum zero, and is 1-smooth because each coordinate appears at most twice in the component smoothness sum.The construction combines the two-coordinate components with a terminal Huber term.Source: §A.3 · p. 22
  • During block i, earlier components remain zero, later components remain zero, and only the active component Φ_i/2 contributes a nonzero gradient.The coordinate scaling makes each actual step h_t induce the local step h_t/2, so the candidate path is the gradient-descent trajectory.Source: §A.3 · pp. 22–23
  • From time t_k onward, the terminal Huber term stays in its affine region and above its activation level, yielding the stated final value and loss bound.The argument uses δ = D_{k+1}/(1+s_{k+1}) and concludes R_n(h) ≥ 2F(x_n), then drops the factor 2.Source: §A.3 · p. 23

B Proofs for the Non-anytime Lower Bound

  • The non-anytime lower-bound proof assumes 0 < ε < 1/2, c > ε, and a sufficiently large a, with λ ≥ a; increasing a preserves the transfer bound.The passage also specifies conventions for empty subsequences and checkpoint sets selecting a zero step.Source: B Proofs for the Non-anytime Lower Bound · p. 23

B.1 Proof of (14)

The proof reduces the checkpoint minimization to positive steps and invokes the local lower-bound construction. It then expresses the checkpoint objective by decomposing around each selected step.

B.1 Proof of (14)

  • Every selected step in a minimizing checkpoint set has size b_i > a/2 ≥ B_0, so Lemma 2.2 applies, including the empty-set case.Inserting a positive step not already selected increases the objective factor, so deleting such a checkpoint strictly decreases Ψ_λ.Source: §B.1 · p. 24
  • For every s ≥ 0, (λ + s)^2 ≥ 4(λ − 1)(1 + s), by the square identity shown in the proof.The difference is (s − λ + 2)^2.Source: §B.1 · p. 24

B.2 Proof of Lemma 3.3

  • The identity for Ψ_λ decomposes a checkpoint set around each positive selected step, minimizing independently over the checkpoints before and after it.Including the empty set completes the identity.Source: §B.2 · p. 24

B.3 Proof of Lemma 3.4

The proof establishes the inductive bound by splitting a maximizing schedule at a tight checkpoint and applying bounds to the resulting blocks. Log-submodularity and tightness provide the structure needed for this split.

B.3 Proof of Lemma 3.4

  • Tight checkpoint sets are closed under unions and intersections, and two nonempty tight sets cannot be disjoint.These properties follow from log-submodularity and its strictness for disjoint nonempty sets.Source: §B.3 · p. 25
  • For every n and λ ≥ a, U_n(λ) has a positive finite maximizing schedule with the empty set and a nonempty checkpoint set both tight.The proof establishes attainment and tightness as prerequisites for the split.Source: §B.3 · pp. 25–26
  • The splitting argument substitutes auxiliary variables that preserve checkpoint contributions and adds a correction term for shifted parameters.The correction term cancels the extra shifted-parameter contributions in the proof of Lemma 3.4.Source: §B.3 · pp. 27–28
  • Splitting a maximizing schedule at a nonempty tight checkpoint partitions it into shorter blocks, whose bounds combine to prove (18).The block parameters follow from the tight-set identities, and the checkpoint terms cancel.Source: §B.3 · p. 30

B.4 Proof of Lemma 3.5

The proof reduces the required scalar inequality to normalized variables and connects its limiting case to the silver exponent. A slack estimate extends the argument to the perturbed parameters.

B.4 Proof of Lemma 3.5

  • In the ideal case c = 1 and ε = 0, the boundary expression is bounded by one at p = p_sil, with equality at z = 0, 1/2, and 1.This is the silver inequality used to establish the scalar condition.Source: §B.4 · pp. 30–31
  • A slack estimate and integration from p_sil to p control the perturbation for p > p_sil.The proof uses the resulting estimate to rule out failure of the normalized inequality under the finite-parameter conditions.Source: §B.4 · pp. 31–32
  • Normalizing x, y, and w reduces the target scalar inequality to (51), with B/w = (c − ε)uv.The scalar relations supply the other condition used in that reduction.Source: §B.4 · pp. 30, 32

B.5 Proof of (24)

The proof chooses parameters close to the silver exponent to obtain the non-anytime lower bound, then tracks their dependence to establish (24). It also develops bounds at strict record times for the anytime argument.

B.5 Proof of (24)

  • For η = 1/10, the proof gives R_n(h) = Ω(n^−(p_sil+1/10)); its parameter choices also establish the bound with exponent p_sil + η.The stated dependence on η is obtained by tracking the constants in (24).Source: §B.5 · p. 32
  • The parameter choice yields (24) with an absolute implied constant, with log B_0 = O(log(1/η)).The proof derives this from bounds on C_0 and the quantities c and R.Source: §B.5 · pp. 32–33

C.1 Proof of Lemma 4.1

  • At a strict record time, the proof lower-bounds V by appending the final step to a minimizing checkpoint set and factoring the schedule into intervening blocks.The block factorization uses the selected steps and their associated block values.Source: §C.1 · p. 33
  • As p approaches p_sil, the tracked constants satisfy log C_p = O(δ^−1 log(1/δ)), where δ = p − p_sil.The stated bound follows from the parameter dependence in (24) and the constants used in the proof of Lemma 4.1.Source: §C.1 · p. 34

C.2 Proof of Theorem 1.2

The anytime argument compares the total stepsize with the largest step at horizons where the final step is a new record. It yields the stated exponent at infinitely many horizons as p approaches p_sil.

C.2 Proof of Theorem 1.2

  • The proof handles bounded schedules directly; for unbounded schedules it uses infinitely many strict record times and separates cases according to M_n and r_n.When M_n < B_0 or r_n > r_0,p, the cited bounds are stronger than the claimed bound.Source: §C.2 · pp. 34–35
  • At strict record times, the proof derives r_n ≥ c_p n^−β(p), where β(p) = 2p/(1 + p).This bound is stated for record times satisfying the proof's assumptions.Source: §C.2 · p. 35
  • There are infinitely many strict record times, which proves Theorem 1.2.Source: §C.2 · p. 35

Related papers

Loading 2609.09152v2…