arXiv CS open access

Improved Gradient Descent Lower Bounds Beyond Nesterov

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Improved Gradient Descent Lower Bounds Beyond Nesterov Yuhan Ye MIT yyh03@mit.edu

Kaizhao Liu MIT mrzt@mit.edu

arXiv:2609.02855v1 [math.OC] 2 Sep 2026

September 3, 2026

Abstract We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical Ω(n−2 ) first-order oracle lower bound [NY83], we prove an Ω(n−1.6342 ) non-anytime bound and an Ω(n−1.2408 ) anytime barrier. These improve the Ω(n−1.932 ) non-anytime result of [MC26] and the Ω(n−4/3 ) anytime bound of [TFZH26], respectively. √ − log (1+ 2) 2 Combined with the O(n ) rate achieved by non-anytime silver schedules [AP25b, GSW25b], our anytime lower bound establishes a strict separation between the achievable convergence exponents in the two settings.

Contents 1

Introduction 1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Technique overview 3

3 3 4 5

Proof of the Non-Anytime Lower Bound 8 3.1 Reduction to a sequence inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Eliminating the variables xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Properties of Γλ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Upper bounding ∑q−1 i=1 Γλ (ωi , ωi+1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Anytime Lower Bound

Concluding Remarks

Appendix

A Hard-Function Construction

B Properties of J(α, λ ) and Numerical Solution

C Proofs for the Anytime Lower Bound 25 C.1 Proof and Intuition of Lemma 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 C.2 Proof of Lemma 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Introduction

Gradient descent (GD) is one of the simplest optimization algorithms, dating back nearly two hundred years to Cauchy [Cau47]. It updates xk+1 = xk − hk ∇ f (xk ), where hk > 0 is the stepsize. In this paper, we study how far this basic method can be accelerated by predetermined stepsizes in smooth convex optimization. To formalize this question, we define the convergence rate of a stepsize schedule H = (h1 , . . . , hn ) by f (xn+1 ) − f (x⋆ ) , L ⋆ 2 d∈N f ∈FL (Rd ) x⋆ ∈arg min f x1 ∈Rd \{x⋆ } 2 ∥x1 − x ∥

Rn (H) := sup

sup

where FL (Rd ) is the class of convex L-smooth functions on Rd with a nonempty set of minimizers. In the non-anytime (finite-horizon) setting, the schedule is designed for a fixed horizon n. In the anytime setting, one infinite schedule h = (hk )k≥1 is used for every horizon, with Hn = (h1 , . . . , hn ). It is a standard textbook result that GD with the constant stepsize 1/L achieves an O(n−1 ) rate [LP66, Nes04]. Classical acceleration approaches modify the GD iteration by introducing momentum or auxiliary sequences, as in Polyak’s heavy-ball method [Pol64] and Nesterov’s accelerated method [Nes83]. Among the broader class of first-order methods, Nesterov’s method attains the optimal O(n−2 ) rate for smooth convex objectives, while the matching Ω(n−2 ) first-order oracle lower bound goes back to Nemirovsky and Yudin [NY83]. For GD with predetermined stepsizes, since it is a restricted class of first-order methods, the classical Ω(n−2 ) lower bound continues to apply. For many years, however, the best known general upper bound remained the classical O(n−1 ) rate. This leads to the fundamental question of whether a faster rate is possible. In recent years, a growing body of work surprisingly shows that GD itself can be accelerated beyond the classical O(n−1 ) rate by using carefully designed stepsize schedules that use occasional long steps and recursive structure [Gri24, AP25b, GSW25a, GSW25b]. The current best known non-anytime upper bound √ is O(n− log2 (1+ 2) ), achieved by the silver schedule [AP25b, GSW25b]. An anytime construction based on silver-schedule blocks achieves an O(n−1.119 ) rate at every stopping time [ZLDC25]. This left open whether the generic Ω(n−2 ) lower bound could be strengthened toward these upper bounds. Recently, Ma and Chen [MC26] proved an Ω(n−1.932 ) lower bound by cleverly constructing a hard function family.√ A subsequent refinement [Tsa26] gave an exposition of the framework and improved this bound to Ω(n− 3 ). For the anytime case, [TFZH26] provides an Ω(n−4/3 ) lower bound.1

1.1

Contribution

Narrowing these gaps is a central problem in optimization as it clarifies the limitation of accelerating GD through stepsize schedules alone. In this paper, we make progress on both questions. Our result improves √ the −1.2408 ). Since log (1+ 2) ≈ non-anytime lower bound to Ω(n−1.6342 ), and the anytime lower bound to Ω(n 2 √ 1.2716 > 1.2408, our anytime lower bound rules out the O(n− log2 (1+ 2) ) rate achieved by non-anytime silver schedules [AP25b, GSW25b], establishing a strict separation between the two cases. Theorem 1.1. There exists a constant c > 0 such that, for every integer n ≥ 1 and every H ∈ (0, ∞)n , Rn (H) ≥ cn−1.6342 . 1 Throughout, we use an Ω(n−p ) anytime lower bound as shorthand for the statement that no single infinite stepsize schedule achieves an o(n−p ) rate.

Theorem 1.2. No positive infinite schedule h = (hk )k≥1 , with Hn = (h1 , . . . , hn ), satisfies Rn (Hn ) = o(n−1.2408 ).

Figure 1: Improved lower bounds for GD. After reviewing additional related work in Section 1.2, we give an overview of our techniques in Section 2. At a high level, both proofs use the hard-function family introduced in [MC26, Theorem 4.1]. After this construction, Ma and Chen summarize the selected long-step excesses by a single quantity [MC26, Section 5.4]. Tsai rewrites this quantity in terms of the harmonic mean of these excesses [Tsa26, Lemma 7]. In contrast, our main technical contribution is to retain every factor coupling consecutive selected long steps and estimate these factors term by term. For the anytime case, we adapt the finite-to-anytime transfer from [TFZH26, Theorem 4.1] and apply the same estimate at horizons where the last stepsize is the largest seen so far. This yields the improved anytime lower bound. The remainder of the paper is organized as follows. Section 3 provides the full details of the non-anytime proof outlined in Section 2. Section 4 extends the analysis to the anytime setting. Appendix A recalls the hard-function construction, Appendix B details how the scalar parameters are chosen, and Appendix C contains the proofs deferred from Section 4.

1.2

Related Work

Accelerating GD. Classical acceleration methods modify GD by incorporating information from previous iterations, as in Polyak’s heavy-ball method [Pol64] and Nesterov’s accelerated method [Nes83]. A complementary line of work uses the performance-estimation problem (PEP), which provides a systematic numerical framework for worst-case analysis [DT14]. Interpolation conditions yield exact PEP formulations for fixed-step first-order methods [THG17]. In the stepsize-only setting, PEP has also been used to search numerically for horizon-dependent GD schedules, providing finite-horizon evidence of acceleration [DGVPR24, KHG25]. Within the classical O(n−1 ) regime, improved constants were obtained using predetermined schedules with stepsizes increasing toward 2/L [TV23] and, separately, periodic schedules with occasional long steps analyzed through multi-step certificates [Gri24]. For strongly convex quadratic objectives, stepsize-only acceleration was known much earlier through Chebyshev stepsizes [You53]. Fractal orderings were later introduced to control their unstable intermediate iterates [AGZ21].

√ Silver and recursive stepsize schedules. Let ρ = 1 + 2. At horizons n = 2k − 1, the recursively defined silver schedule attains the rate O(n− log2 ρ ), where log2 ρ ≈ 1.2716 [AP25b]. A related right-heavy schedule attains the silver exponent for the objective gap, while its reversal attains the same exponent for the squared gradient norm [GSW25a]. A subsequent composition framework and an independent concatenation construction extend this rate to every prescribed finite horizon [GSW25b, ZJ26]. Note that these guarantees hold at selected horizons (non-anytime case). The question of whether an infinite schedule can accelerate GD at every stopping time was posed in [KS24] and answered affirmatively in [ZLDC25], which gives an anytime O(n−1.119 ) rate. The silver-step constructions also extend to projected and proximal gradient methods [BA25], and to smooth strongly convex objectives with accelerated linear rates [AP25a]. Lower bounds for GD. The classical Ω(n−2 ) first-order oracle lower bound for smooth convex optimization goes back to Nemirovsky and Yudin [NY83], while Nesterov’s accelerated method attains the matching O(n−2 ) rate [Nes83]. A standard quadratic-chain proof appears in [Nes04, Section 2.1.2, Theorem 2.1.7], and we recall its geometric mechanism in Fact A.2. Stronger conclusions were previously known under additional structural restrictions. Time-invariant oblivious first-order methods cannot attain O(n−α ) rates for any α > 1 [AS16, Corollary 1]. Within the √ recursively generated class of basic f -composable GD schedules, the best objective-gap rate is Θ(n− log2 (1+ 2) ) [GSW25b, Theorem 5]. For arbitrary predetermined schedules, an Ω(n−1.932 ) lower bound was proved using a hard function adapted to the schedule’s √ long steps [MC26]. The same construction was then used to sharpen the non− anytime bound to Ω(n 3 ) [Tsa26]. For the anytime case, it was proved in [TFZH26] that no positive predetermined infinite schedule satisfies Rn (Hn ) = o(n−4/3 ).

Technique overview

In this section, we provide a high-level overview of techniques behind the proof of Theorem 1.1. Replacing f by f /L and each hk by Lhk leaves the GD iterates and Rn unchanged, so we assume L = 1 throughout. Following [MC26], we call a step hk long if hk > 1 and short if hk ≤ 1. Let r := #{k : hk > 1} be the number of long steps. For an integer 1 ≤ q ≤ r, select q long steps 0 < t1 < · · · < tq ≤ n,

hti > 1,

where t0 = 0 and tq+1 = n + 1. Define Si to be the stepsize accumulation between the selected long steps, that is, Si := hti−1 +1:ti −1 , 1 ≤ i ≤ q + 1, where ha:b := ∑bk=a hk , with an empty sum equal to zero. An illustration of these concepts is provided in Fig. 2. Lemma 2.1. For every such selection, Rn (H) ≥

q−1 q Si+1 + hti+1 1 hti − 1 . ∏ Sq + htq + 2Sq+1 + 1 ∏ S + h + S + h ti i+1 ti+1 i=1 Si + 1 i=1 i

(1)

This is the lower bound in [MC26, Theorem 4.1]; see also [Tsa26, Lemma 6]. The lemma reduces the original problem to establishing a lower bound for the right-hand side of (1), which involves only the

tq−1

h=1 ···

···

ht1 S1

ht2

··· htq−1

···

··· htq

hn Sq+1

Figure 2: The selected long steps are hti > 1, and each brace marks the stepsize accumulation Si between the selected long steps. sequence H. The lemma extends the classical Huber bound: When no long step is selected (q = 0), it recovers exactly 1 Rn (H) ≥ . (2) 1 + 2 ∑nk=1 hk We briefly recall the proof of (2) in Fact A.1. A nonempty selection q > 0 allows (1) to adapt flexibly to the long steps, limiting the acceleration they might otherwise provide in (2). The lemma is proved using a hard function tailored to the schedule H and the selected long steps. Appendix A gives an intuitive explanation of the construction. Based on Lemma 2.1, Ma and Chen bound the resulting product using a single quantity that summarizes the selected long-step excesses [MC26, Section 5.4]. Tsai derives a related bound in terms of the harmonic mean of these excesses [Tsa26, Lemma 7] and then uses a counting function [Tsa26, Lemma 8]. We instead retain each factor coupling two consecutive selected long steps and estimate these factors term by term. For w, z, x, y > 0, define √ xy (w + z + x + y) Kw,z (x, y) := p . wz(w + x)(z + y)

Reduction to a sequence inequality.

(3)

Given any sequence ω1 , . . . , ωq , write ω1↓ ≥ · · · ≥ ωq↓ for its decreasing rearrangement. Then the problem of proving an Ω(n−(1+α) ) lower bound for (1) can be reduced to the following sequence inequality. Lemma 2.2. Fix α > 0. Suppose there is a constant Cα < ∞, depending only on α, with the following property: For every integer q ≥ 2 and any positive sequences x1 , . . . , xq and ω1 , . . . , ωq such that q

∑ xi < q,

∑ ωs↓ ≥ q

i=1

s=p+1

α q −1 p

(∀1 ≤ p < q),

(4)

we have q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Cα ,

(5)

i=1

where √ Eend := x1 xq

" # xq + 2 q − ∑qi=1 xi 1 + x1 /ω1 1+ . 1 + xq /ωq ωq

Then, Rn (H) ≥ cα (n + 1)−(1+α) for every n and H. 6

(6)

The reduction makes two choices that are not apparent from (1). Given a cutoff q, it selects the q largest excesses, while the cutoff itself is chosen from the schedule H according to (15). The right-hand side of (1) is then normalized so that the variables xi have total mass below q, and the decreasing rearrangement of the weights ωi satisfies the tail inequalities in (4). The proof is provided in Section 3.1. Eliminating the variables xi . To make (5) tractable, we first eliminate the variables xi . For a parameter λ > 0 to be chosen later, define Γλ (w, z) := sup {log Kw,z (x, y) − λ (x + y)} .

(7)

x,y>0

By definition, log Kw,z (x, y) ≤ λ (x + y) + Γλ (w, z).

(8)

Applying this inequality to every adjacent factor and using ∑i xi < q gives the next reduction. Lemma 2.3. Fix α, λ > 0. There is a constant Cα,λ < ∞ such that, for every integer q ≥ 2, every pair of positive sequences (xi )qi=1 and (ωi )qi=1 satisfying (4) obeys ( ) q−1

q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Cα,λ exp 2λ q + ∑ Γλ (ωi , ωi+1 ) . i=1

(9)

i=1

We are left with a sum of consecutive Γλ terms. To proceed, we record some basic properties of Γλ . Lemma 2.4 (Properties of Γλ ). For every λ > 0, Γλ has the following properties. 1. Smoothness. For every w, z > 0, the supremum in (7) is attained at a unique point of (0, ∞)2 . Denote this point by (xλ (w, z), yλ (w, z)). The optimizer map and Γλ are C∞ on (0, ∞)2 . 2. Symmetry. Γλ (w, z) = Γλ (z, w). 3. Joint convexity. The map (w, z) 7→ Γλ (w, z) is jointly convex on (0, ∞)2 . 4. Coordinatewise decrease. The function Γλ is strictly decreasing in each coordinate. 5. Strict submodularity. 2 ∂wz Γλ (w, z) < 0.

(10)

Controlling the summation of consecutive pairs. The remaining sum is bounded in four steps. First, the summation of consecutive pairs can be split into two matchings, and maximizing over matchings leads to a symmetric function. Second, the symmetry, joint convexity, and coordinatewise decrease together allow majorization, replacing the unknown weights ωi↓ by the explicit comparison sequence in (23). Third, strict submodularity identifies the maximizing matching of these explicit comparison weights. Finally, the resulting finite sum is compared with a one-dimensional integral. The full argument is given in Section 3.4. Lemma 2.5. Fix α, λ > 0. There is a constant Cα,λ < ∞ such that, for every integer q ≥ 2 and every positive sequence ω1 , . . . , ωq satisfying the tail condition in (4), q−1

∑ Γλ (ωi , ωi+1 ) ≤ 2q

i=1

Z 1/2 0

Γλ Wα (t),Wα (1 − t) dt +Cα,λ ,

where Wα (t) := αt −1−α for 0 < t ≤ 1. 7

(11)

Completing the proof of Theorem 1.1.

Define Z 1/2

J(α, λ ) := 2λ + 2 0

Γλ Wα (t),Wα (1 − t) dt.

(12)

Then Lemmas 2.3 and 2.5 give q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Cα,λ eqJ(α,λ ) .

(13)

i=1

Thus J(α, λ ) ≤ 0 makes (5) uniform in q, and Lemma 2.2 yields Rn (H) ≥ cα,λ (n + 1)−(1+α) .

(14)

For α = 0.6342 and λ = 0.4506, numerical integration gives J(0.6342, 0.4506) < −0.00005 < 0. Therefore Rn (H) = Ω(n−1.6342 ), proving Theorem 1.1. Appendix B studies the dependence of J on (α, λ ) and explains how the pair (0.6342, 0.4506) was obtained numerically.

Proof of the Non-Anytime Lower Bound

This section provides the full proofs of Lemmas 2.2 to 2.5.

3.1

Reduction to a sequence inequality

Proof of Lemma 2.2. Suppose that (4) implies (5), with a constant Cα uniform over all q ≥ 2. Fix n ≥ 1 and a schedule H = (h1 , . . . , hn ). Recall that r is the number of long steps. If r = 0, the Huber bound (2) yields Rn (H) ≥ (2n + 1)−1 ≥ (2(n + 1))−1 . Therefore, from now on we consider r ≥ 1. We decompose each stepsize hk into two components: a base min{hk , 1} and an excess max{hk − 1, 0}. Let a1 ≥ · · · ≥ ar > 0 denote the positive excesses in decreasing order. We define the base accumulation as B := 1 + ∑nk=1 min{hk , 1}. By definition, B ≤ n + 1. Moreover, let Ds denote the total stepsize accumulation excluding the excesses from the s longest steps: r

Ds := B + ∑ aℓ ,

1 ≤ s ≤ r,

ℓ=s+1

with Dr = B. See Fig. 3 for an illustration of these definitions. t2

tq−1

a1 ≥ · · · ≥ ar > 0 q h=1

··· h1

··· ht1

··· ht2

···

B = 1+

··· htq−1

··· htq

··· aq

aq+1 aq+2

Dq = B + ∑ aℓ ℓ>q

k=1

Sq+1

∑ min{hk , 1} |

···

}

total height of the blue portions

Figure 3: The schedule in chronological order (left) and its positive excesses in decreasing order (right). 8

Choose q ∈ arg min Ds sα .

(15)

1≤s≤r

This specific choice ensures that Dq has a universal upper bound Dq ≤ Dq qα ≤ Dr rα ≤ (n + 1)α+1

(16)

as Dr = B ≤ n + 1 and r + 1 ≤ n + 1. We first treat the special case q = 1 to illustrate the power of Lemma 2.1. Then we show that Lemma 2.1 combined with (5) is sufficient to prove the general case q ≥ 2. Case 1: q = 1.

If a1 ≤ D1 , since D1 + a1 = 1 + ∑nk=1 hk , the Huber bound (2) gives Rn (H) ≥

1 1 . ≥ 2(D1 + a1 ) − 1 4D1

If a1 > D1 , select t such that ht − 1 = a1 and apply Lemma 2.1. In this case D1 = (S1 + 1) + (S2 + 1), while (S1 + 1) + a1 + 2(S2 + 1) − 1 < a1 + 2D1 < 3a1 . Consequently, Rn (H) ≥

a1 1 1 1 > ≥ > . (S1 + 1)(S1 + a1 + 2S2 + 2) 3(S1 + 1) 3D1 4D1

Thus Rn (H) ≥ 1/(4D1 ) in both subcases. Applying (16) yields Rn (H) ≥

1 . 4(n + 1)α+1

Case 2: q ≥ 2. Let t1 < · · · < tq be the indices of the q largest positive excesses hk − 1. With this selection, let S1 , . . . , Sq+1 be defined as in Lemma 2.1. Note that q+1

∑ (Si + 1) = q + 1 + ∑

hk = D q .

k∈{t / 1 ,...,tq }

i=1

We use Dq /q as the normalization scale for Si + 1 and hti − 1, and define xi :=

q(Si + 1) , Dq

ωi :=

q(hti − 1) , Dq

1 ≤ i ≤ q.

By Lemma 2.1, Rn (H) ≥ G, where G denotes the right-hand side of (1) for the indices selected above. Substituting the definitions of xi and ωi gives s xq + 2(q − ∑qi=1 xi ) − q/Dq q−1 D 1 + x1 /ω1 √ q −1 G = x1 xq 1+ ∏ Kωi ,ωi+1 (xi , xi+1 ). q 1 + xq /ωq ωq i=1 Replacing −q/Dq by 0 increases the quantity in the bracket and yields G−1 ≤

q−1 Dq Eend ∏ Kωi ,ωi+1 (xi , xi+1 ). q i=1

(17)

The sequences (xi )qi=1 and (ωi )qi=1 satisfy (4). Specifically, as xi are normalized, q

∑ xi = Dq ∑ (Si + 1) = q −

i=1

q(Sq+1 + 1) < q. Dq

Moreover, noting that ωs↓ = qas /Dq for 1 ≤ s ≤ q, the minimizing property (15) implies α q ∑s=p+1 as D p 1 q q ↓ 1+ = ≥ ωs = 1 + ∑ q s=p+1 Dq Dq p for every 1 ≤ p < q. Hence, (5) holds, and by (16), Rn (H) ≥ G ≥

1 q ≥ . Cα Dq Cα (n + 1)α+1

Finally, combining all cases gives Rn (H) ≥ cα (n + 1)−(1+α) ,

3.2

cα := min{Cα−1 , 1/4}.

Eliminating the variables xi

Proof of Lemma 2.3. Set q

∆ := q − ∑ xi > 0. i=1

Applying (8) to Kωi ,ωi+1 (xi , xi+1 ) for 1 ≤ i < q and summing gives q−1

q−1

log ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ λ ∑ (xi + xi+1 ) + ∑ Γλ (ωi , ωi+1 ). i=1

Since

q−1

i=1

∑ (xi + xi+1 ) = 2 ∑ xi − x1 − xq = 2q − (2∆ + x1 + xq ),

i=1

we obtain q−1

(

)

q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ exp 2λ q + ∑ Γλ (ωi , ωi+1 ) Eend e−λ (2∆+x1 +xq ) . i=1

i=1

It remains to bound Eend e−λ (2∆+x1 +xq ) independently of q, (xi )qi=1 , and (ωi )qi=1 . Taking p = q − 1 in (4) yields α q q ↓ min ωi = ωq ≥ q − 1 ≥ αq log ≥ α. 1≤i≤q q−1 q−1

(18)

The last two inequalities use eu − 1 ≥ u and log(1 + t) ≥ t/(1 + t). In particular, ω1 , ωq ≥ α. Using this in (6) and writing T := x1 + xq + ∆, we obtain Eend e−λ (2∆+x1 +xq ) ≤ Cα (1 + T )5/2 e−λ T ≤ Cα sup(1 + t)5/2 e−λt =: Cα,λ < ∞. t≥0

Substitution into the preceding display proves (9). 10

3.3

Properties of Γλ

Proof of Lemma 2.4. For w, z, x, y > 0, set Fw,z (x, y) := log Kw,z (x, y) − λ (x + y). (1) Smoothness. For fixed w, z > 0, the function Fw,z (x, y) tends to −∞ as x ↓ 0, y ↓ 0, or x + y → ∞. It therefore attains its maximum at an interior point. Write A := w + x, B := z + y, and Σ := A + B. For every nonzero direction (a, b), D2x,y Fw,z (x, y)[(a, b), (a, b)] = −

b2 (a + b)2 a2 b2 a2 − − + + < 0. 2x2 2y2 Σ2 2A2 2B2

Thus the maximizer is unique. Fix (w0 , z0 ) and let (x0 , y0 ) be its maximizer. The Jacobian in (x, y) of the first-order condition ∇x,y Fw,z (x, y) = 0 is the invertible Hessian above. The implicit function theorem gives a neighborhood of (w0 , z0 ) on which the critical point is a C∞ function of (w, z). Since (w0 , z0 ) was arbitrary, the optimizer map is C∞ on (0, ∞)2 . Substituting it into Fw,z shows that Γλ is also C∞ . (2) Symmetry.

The definition (7) is invariant under (w, x) ↔ (z, y).

(3) Joint convexity.

For fixed x, y, put A := w + x and B := z + y. The Hessian in (w, z) has quadratic form

D2w,z Fw,z (x, y)[(a, b), (a, b)] =

a2 a2 b2 b2 (a + b)2 + + + − ≥ 0. 2w2 2A2 2z2 2B2 (A + B)2

Indeed, the first four terms dominate a2 /A2 +b2 /B2 , which is at least (a+b)2 /(A+B)2 by Cauchy–Schwarz. Taking the supremum in (7) preserves convexity. (4) Coordinatewise decrease. Write x∗ := xλ (w, z) and y∗ := yλ (w, z), and set A := w + x∗ , B := z + y∗ , and Σ := A + B. The chain rule and the first-order conditions give ∂w Γλ = ∂w Fw,z + ∂x Fw,z ∂w x∗ + ∂y Fw,z ∂w y∗ 1 1 1 = ∂w Fw,z = − − . Σ 2w 2A Equivalently, −∂w Γλ =

x∗ B + > 0, 2wA AΣ

and the same argument applies to the z coordinate. (5) Strict submodularity.

With the notation above, the first-order conditions imply λ−

1 w z = = . Σ 2x∗ A 2y∗ B

Consequently, define the parameter τ∗ :=

x∗ A y∗ B = > 0. w z

(19)

For u, τ > 0, set

√ u + u2 + 4uτ fu (τ) := . 2 Then x∗ = −w + fw (τ∗ ), y∗ = −z + fz (τ∗ ), A = fw (τ∗ ), B = fz (τ∗ ), and g(τ∗ ; w, z) = 0,

g(τ; w, z) :=

(20)

1 1 + −λ. 2τ fw (τ) + fz (τ)

(21)

The explicit formula for fu shows that it increases in both arguments. Hence ∂τ g < 0 and ∂z g < 0, and implicit differentiation gives ∂z τ∗ = −(∂z g)/(∂τ g) < 0. Moreover, 1 −1 Σ= λ− , A = fw (τ∗ ). 2τ∗ Since dΣ/dτ = −Σ2 /(2τ 2 ) < 0, we have ∂z Σ > 0 and ∂z A = fw′ (τ∗ )∂z τ∗ < 0. Differentiating (19) yields 2 ∂wz Γλ = −

∂z Σ ∂z A + 2 < 0, Σ2 2A

which proves (10).

3.4

q−1

Upper bounding ∑i=1 Γλ (ωi , ωi+1 )

In this section, we prove Lemma 2.5. Step 1. Symmetrization. For a positive vector v = (v1 , . . . , vN ) ∈ RN and 0 ≤ k ≤ ⌊N/2⌋, let Mk (N) be the set of all collections of k disjoint unordered pairs from {1, . . . , N}. Define the largest sum over all k-edge matchings on the coordinates of v to be Φk,λ (v1 , . . . , vN ) :=

max

∑ Γλ (va , vb ),

M∈Mk (N) {a,b}∈M

Φ0,λ := 0.

Let N = q − 1 and

q−1 kq := . 2 We are going to show that q−1

∑ Γλ (ωi , ωi+1 ) ≤ 2Φk ,λ (ωq↓ , . . . , ω2↓ ) +Cα,λ . q

(22)

i=1

We first split the consecutive pairs into an odd matching and an even matching, according to whether i is odd or even. An illustration is given in Fig. 4.

Figure 4: The consecutive pairs split into two matchings with q = 8. 12

Choose i∗ such that ωi∗ = ω1↓ . If q is odd, both matchings have kq pairs and leave one index unused. If i∗ is matched, replace it by the unused index. The unused coordinate has no larger value, so the coordinatewise decrease in Lemma 2.4 shows that the matching sum cannot decrease. If q is even, the same replacement applies to the even matching with kq pairs. The odd matching has kq + 1 pairs. Delete the pair containing i∗ . The remaining matching has kq pairs drawn from (ωq↓ , . . . , ω2↓ ), and is therefore bounded by Φkq ,λ (ωq↓ , . . . , ω2↓ ). By (18), every ωi ≥ α, and coordinatewise decrease gives Γλ (ωi , ω j ) ≤ Γλ (α, α). In particular, the contribution of the deleted pair is bounded by max{0, Γλ (α, α)}. This proves (22). Step 2. Majorization. For a fixed matching, the sum of its Γλ terms is convex and coordinatewise decreasing. Taking the maximum over all matchings preserves both properties, and permuting the coordinates only permutes the matchings. Thus Φk,λ is symmetric, convex, and coordinatewise decreasing. For a symmetric, convex, and coordinatewise decreasing function, we have the following majorization principle: Lemma 3.1. Let F : (0, ∞)N → R be symmetric, convex, and coordinatewise decreasing. Suppose a1 ≤ · · · ≤ aN and b1 ≤ · · · ≤ bN satisfy ℓ

ℓ

∑ ai ≥ ∑ bi ,

i=1

1 ≤ ℓ ≤ N.

i=1

Then F(a) ≤ F(b). Here, the partial-sum assumption is precisely a ≺ w b, in the notation of weak supermajorization. Since every symmetric convex function is Schur-convex and F is coordinatewise decreasing, the conclusion F(a) ≤ F(b) follows from the standard characterization of functions preserving weak supermajorization; see [MOA11, Theorem 3.A.8 and Proposition 3.C.2]. For 2 ≤ s ≤ q, define the comparison weights (q) w̄s := q1+α (s − 1)−α − s−α , which may also be written as (q)

w̄s = q1+α

Z s

(23)

αu−1−α du.

s−1 (q) (q) Since the integrand is decreasing, w̄q ≤ · · · ≤ w̄2 . Moreover, for 1 ≤ p < q, q

∑

(q) w̄s = q1+α

Z q

−1−α

αu p

s=p+1

α q −1 . du = q p

Setting p = q − ℓ in (4) gives, for 1 ≤ ℓ ≤ q − 1, ℓ

ℓ

i=1

↓ ≥ ∑ w̄q+1−i . ∑ ωq+1−i (q)

Applying Lemma 3.1 to F = Φkq ,λ , a = (ωq↓ , . . . , ω2↓ ), and b = (w̄q , . . . , w̄2 ) proves (q)

(q)

Φkq ,λ (ωq↓ , . . . , ω2↓ ) ≤ Φkq ,λ (w̄q , . . . , w̄2 ). (q)

(q)

(24)

Step 3. Identify the maximizing matching. Majorization has replaced the unknown weights by the (q) (q) explicit sequence (w̄q , . . . , w̄2 ). It remains to identify the matching that maximizes the resulting sum. For 0 < a ≤ b ≤ c ≤ d, symmetry and strict submodularity give Γλ (a, d) + Γλ (b, c) ≥ Γλ (a, c) + Γλ (b, d), Γλ (a, d) + Γλ (b, c) ≥ Γλ (a, b) + Γλ (c, d). Let 0 < v1 ≤ · · · ≤ vN . Since Γλ decreases in each coordinate, a maximizing matching may be chosen to use the 2k smallest coordinates. If v1 is not paired with v2k , exchange the partners of their two pairs. The two inequalities above show that the total cannot decrease. Fixing the pair (v1 , v2k ) and repeating on the remaining coordinates gives k

Φk,λ (v1 , . . . , vN ) = ∑ Γλ (v j , v2k+1− j ).

(25)

j=1

Applied to the comparison weights, this identity gives (q) (q) Φkq ,λ (w̄q , . . . , w̄2 ) =

(q)

∑ Γλ (w̄q+1− j , w̄q−2k + j ).

(26)

j=1

(q)

q Step 4. Comparison with the integral. Finally, we estimate ∑ j=1 Γλ (w̄q+1− j , w̄q−2kq + j ) by comparing it with its corresponding Riemann integral. By the mean value theorem, for every 2 ≤ s ≤ q there is θs ∈ (s − 1, s) such that (q) w̄s = Wα (θs /q), (27) Wα (t) := αt −1−α , 0 < t ≤ 1.

To control the error introduced by replacing these mean-value points with the uniform mesh, define G(t, v) := Γλ (Wα (t),Wα (v)),

0 < t ≤ 1,

0 < v ≤ 1.

The following regularity estimate shows that one argument of G can be extended to 0. Lemma 3.2 (Uniform Lipschitz bound). For fixed α, λ > 0, the function G has a Lipschitz extension to [0, 1] × [1/2, 1]. Proof of Lemma 3.2. Let D := (0, 1] × [1/2, 1]. For (t, v) ∈ D, write w := Wα (t), z := Wα (v), and let (x∗ , y∗ ) be the unique optimizer in the definition of Γλ (w, z). Set A := w + x∗ , B := z + y∗ , Σ := A + B as in the proof of Lemma 2.4. The first-order conditions give τ∗ :=

x∗ A y∗ B = , w z

λ=

1 1 + . 2τ∗ Σ

We first obtain bounds on the optimizer that are uniform over D. Since v ∈ [1/2, 1], α ≤ z ≤ α21+α . Moreover, as z + y∗ ≥

√ zτ∗ , λ≤

1 1 +√ . 2τ∗ ατ∗

The right-hand side tends to 0 as τ∗ → ∞, so τ∗ ≤ Cα,λ . In particular, x∗ , y∗ ≤ τ∗ ≤ Cα,λ . The bounds on z and y∗ give B := z + y∗ ≤ α21+α +Cα,λ , whereas A := w + x∗ ≥ w and Σ := A + B ≥ w.

We next bound the derivatives of Γλ . The derivative identity (19) yields −∂w Γλ (w, z) =

x∗ B + . 2wA AΣ

Since A ≥ w, Σ ≥ A ≥ w, and x∗ , B ≤ Cα,λ , |∂w Γλ (w, z)| ≤ Cα,λ w−2 . Similarly, −∂z Γλ (w, z) =

A y∗ + . 2zB BΣ C

Using z, B ≥ α, y∗ ≤ Cα,λ , and A ≤ Σ, we obtain |∂z Γλ (w, z)| ≤ 2αα,λ2 + α1 ≤ Cα,λ . By the chain rule, ∂t G(t, v) = ∂w Γλ (w, z)Wα′ (t). Since |Wα′ (t)| = α(1 + α)t −2−α and Wα (t)−2 = α −2t 2+2α , we have |∂t G(t, v)| ≤ Cα,λ |Wα′ (t)|Wα (t)−2 ≤ Cα,λ t α ≤ Cα,λ . Likewise, ∂v G(t, v) = ∂z Γλ (w, z)Wα′ (v). Because v ∈ [1/2, 1], the derivative Wα′ (v) is uniformly bounded, and hence |∂v G(t, v)| ≤ Cα,λ . It follows that G is uniformly Lipschitz on D. In particular, for every v ∈ [1/2, 1], the limit G(0, v) := lim G(t, v) t↓0

exists. Defining G = G on D and using these limits on {0}×[1/2, 1], the preceding Lipschitz estimate passes to the limit. Hence G is a Lipschitz extension of G to [0, 1] × [1/2, 1]. Using this extension, define I(t) := G(t, 1 − t),

1 0≤t ≤ . 2

After increasing the Lipschitz constant if needed, there are finite Lα,λ and Mα,λ such that |G(t, v) − G(t ′ , v′ )| ≤ Lα,λ (|t − t ′ | + |v − v′ |), |I(t) − I(t ′ )| ≤ Lα,λ |t − t ′ |,

|I(t)| ≤ Mα,λ .

Assume first that q ≥ 3, and write rq := q − 2kq ∈ {1, 2},

u j :=

rq + j − 1 , q

1 ≤ j ≤ kq .

By symmetry and (26), (q) (q) Φkq ,λ (w̄q , . . . , w̄2 ) =

θr + j θq+1− j ∑ G qq , q j=1

Moreover, θrq + j 1 ∈ u j, u j + , q q

θq+1− j rq − 1 rq ∈ 1−uj + ,1−uj + . q q q 15

The total displacement from (u j , 1 − u j ) is less than (1 + rq )/q ≤ 3/q. Since kq ≤ q/2, k

q 3 (q) (q) Φkq ,λ (w̄q , . . . , w̄2 ) − ∑ I(u j ) ≤ Lα,λ . 2 j=1

The intervals [u j − 1/q, u j ] are consecutive, and at most 1/q of [0, 1/2] is omitted: For odd q, they fill [0, 1/2 − 1/(2q)]; for even q, they fill [1/q, 1/2]. On each covered interval, replacing I(t) by its value at the right endpoint costs at most Lα,λ /(2q). Hence kq

Z 1/2

∑ I(u j ) − q 0

j=1

1 I(t) dt ≤ Lα,λ + Mα,λ . 4

Combining the two comparisons gives (q)

(q)

Φkq ,λ (w̄q , . . . , w̄2 ) = ∑ I(u j ) + Oα,λ (1) j=1

Z 1/2

=q 0

Γλ (Wα (t),Wα (1 − t)) dt + Oα,λ (1).

When q = 2, kq = 0, and the same estimate holds after enlarging the constant. Combining this estimate with (22) and (24) proves (11).

Anytime Lower Bound

In this section, we further extend the improved lower bound to the anytime case, for which an infinite schedule h = (hk )k≥1 is fixed in advance, and its prefix Hn = (h1 , . . . , hn ) is used at horizon n. Compared with the non-anytime case, the schedules used at different horizons must be consistent. This leads to a sharper Ω(n−1.2408 ) lower bound. As a high-level conclusion of the proof, we combine the term-by-term estimate from the preceding sections with the anytime transfer argument of [TFZH26]. We first reduce the anytime problem to a truncated sequence inequality, similar to Lemma 2.2. Lemma 4.1. Fix α > 0. Suppose that there are constants ηα ∈ (0, 1) and Cα < ∞, depending only on α, with the following property: For every integer q ≥ 2, every integer 1 ≤ ℓ ≤ ηα q, and all positive sequences (xi )qi=1 and (ωi )qi=1 such that q

∑ xi < q,

∑ ωs↓ ≥ q

i=1

h q α

s=k+1

−1

(∀ℓ ≤ k < q),

(28)

we have q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Cα ,

(29)

i=1

where Eend and Kωi ,ωi+1 (xi , xi+1 ) are defined as in Lemma 2.2. 2(1+α)

Then every positive infinite schedule satisfies lim supn→∞ n 2+α Rn (Hn ) > 0. When ℓ = 1, (28) coincides with (4). For ℓ > 1, the constraints indexed by 1 ≤ k < ℓ are removed, so the ℓ largest ωi are unconstrained. Thus (28) admits a larger class of sequences (xi )qi=1 and (ωi )qi=1 than (4). To proceed, we adapt the estimation technique in the proof of Lemma 2.5 to the truncated tail condition (28). The resulting product bound has exponent qJ(α, λ ) + Oα,λ (ℓ + 1), rather than qJ(α, λ ) as in (13). 16

Lemma 4.2. Fix α, λ > 0. There are constants Aα,λ > 0 and Bα,λ ≥ 0, depending only on α and λ , such that, for every q ≥ 2, every 1 ≤ ℓ < q, and all positive sequences (xi )qi=1 and (ωi )qi=1 satisfying (28), q−1 Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Aα,λ exp qJ(α, λ ) + Bα,λ (ℓ + 1) .

(30)

i=1

Appendix C contains the proof of the lemmas above. Completing the proof of Theorem 1.2. Suppose that J(α, λ ) < 0, and choose ηα ∈ (0, 1) so that Bα,λ ηα ≤ −J(α, λ )/2. For every q ≥ 2, every integer 1 ≤ ℓ ≤ ηα q, and all positive sequences (xi )qi=1 and (ωi )qi=1 satisfying (28), Lemma 4.2 gives q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Aα,λ eqJ(α,λ )+Bα,λ (ℓ+1) ≤ Aα,λ eBα,λ eqJ(α,λ )/2 ≤ Cα,λ .

(31)

i=1

Thus (29) is uniform in q and ℓ, and Lemma 4.1 yields, for every positive infinite schedule, 2(1+α)

lim sup n 2+α Rn (Hn ) > 0.

(32)

n→∞

It remains only to find a pair (α, λ ) for which J(α, λ ) < 0. For α = 0.6342 and λ = 0.4506, numerical integration gives J(0.6342, 0.4506) < −0.00005 < 0. Since 2(1 + 0.6342)/(2 + 0.6342) = 1.240756 . . . < 1.2408, no positive infinite schedule satisfies Rn (Hn ) = o(n−1.2408 ). Appendix B explains the optimization over (α, λ ) and the numerical verification.

Concluding Remarks

In this paper, we improve lower bounds for GD with predetermined stepsizes in both the non-anytime and anytime settings. Starting from the hard-function construction and the corresponding product-form lower bound in Lemma 2.1, we perform a finer term-by-term analysis of the consecutive-pair factors in (5). In the non-anytime setting, this improves the lower bound in [Tsa26] from Ω(n−1.7321 ) to Ω(n−1.6342 ). Combined with the finite-to-anytime transfer of [TFZH26, Theorem 4.1], the same analysis improves the anytime lower bound from Ω(n−4/3 ) to Ω(n−1.2408 ). Closing the gaps between these lower bounds and their corresponding upper bounds remains a significant open problem. Since our term-by-term estimates used to prove the sequence inequality in (5) appear fairly tight, this suggests√that our current use of Lemma 2.1 through Lemma 2.2 may not suffice to close the gap to the O(n− log2 (1+ 2) ) silver-schedule upper bound [AP25b, GSW25b]. To elaborate, while Lemma 2.1 gives a lower bound for every selection of long steps, the proof of Lemma 2.2 uses only the q largest excesses at the q chosen in (15). This choice guarantees the scale estimate (16) and the tail inequalities in (4), and is therefore sufficient for our proof. However, it is not known to maximize the lower bound in (1). It remains open whether optimizing over several values of q, or combining the corresponding selections, can yield a stronger analogue of √Lemma 2.2. A more structural question is whether Lemma 2.1 is already sufficient to prove an Ω(n− log2 (1+ 2) ) lower bound matching the silver-stepsize rate [AP25b]. We suspect that it is necessary to resort to alternative hard functions with a hierarchy of scales, mirroring the recursive structure of silver stepsizes. For the anytime case, the exponent 2(1 + α)/(2 + α) arises from the finite-to-anytime transfer in Lemma 4.1. The argument combines the terminal-step estimate (42) with the tail bounds in (43) at horizons where the final stepsize is the largest seen so far. It remains open whether coupling several horizons, or replacing the terminal-step estimate by a multi-step bound, can yield a stronger anytime lower bound. 17

AI Disclosure For the non-anytime result in Sections 2 and 3, we used ChatGPT-5.6 Sol over multiple rounds to help develop the improvement. ChatGPT’s initial proof was disorganized and difficult to follow. The authors subsequently digested it in detail, worked through the calculation, and reorganized and rewrote the presentation. After further review, the authors identified that the anytime bound could also be improved by combining the refined non-anytime analysis developed in this paper with the framework of Tsai et al. [TFZH26]. We then used ChatGPT-5.6 Sol to help develop the proof of this extension, presented in Section 4 and Appendix C. The authors take full responsibility for the correctness and originality of all content.

References [AGZ21] Naman Agarwal, Surbhi Goel, and Cyril Zhang. Acceleration via fractal learning rate schedules. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 87–99. PMLR, 2021. [AP25a] Jason M. Altschuler and Pablo A. Parrilo. Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule. Journal of the ACM, 72(2):1–38, 2025. [AP25b] Jason M. Altschuler and Pablo A. Parrilo. Acceleration by stepsize hedging: Silver Stepsize Schedule for smooth convex optimization. Mathematical Programming, 213(1–2):1105–1118, 2025. [AS16] Yossi Arjevani and Ohad Shamir. On the iteration complexity of oblivious first-order optimization algorithms. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 908–916. PMLR, 2016. [BA25] Jinho Bok and Jason M. Altschuler. Accelerating proximal gradient descent via silver stepsizes. In Proceedings of the Thirty-Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 421–453. PMLR, 2025. [Cau47] Augustin-Louis Cauchy. Méthode générale pour la résolution des systèmes d’équations simultanées. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 25:536– 538, 1847. [DGVPR24] Shuvomoy Das Gupta, Bart P. G. Van Parys, and Ernest K. Ryu. Branch-and-Bound Performance Estimation Programming: A unified methodology for constructing optimal optimization methods. Mathematical Programming, 204(1–2):567–639, 2024. [DT14] Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex minimization: A novel approach. Mathematical Programming, 145(1–2):451–482, 2014. [Gri24] Benjamin Grimmer. Provably faster gradient descent via long steps. SIAM Journal on Optimization, 34(3):2588–2608, 2024. [GSW25a] Benjamin Grimmer, Kevin Shu, and Alex L. Wang. Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS Journal on Optimization, 7(2):156–169, 2025.

[GSW25b] Benjamin Grimmer, Kevin Shu, and Alex L. Wang. Composing optimized stepsize schedules for gradient descent. Mathematics of Operations Research, 2025. [Hub64] Peter J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964. [KHG25] Yassine Kamri, Julien M. Hendrickx, and François Glineur. Numerical design of optimized first-order algorithms. arXiv preprint arXiv:2507.20773, 2025. [KS24] Guy Kornowski and Ohad Shamir. Open problem: Anytime convergence rate of gradient descent. In Proceedings of the Thirty-Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 5335–5339. PMLR, 2024. [LP66] E. S. Levitin and B. T. Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6(5):1–50, 1966. [MC26] Jianhao Ma and Yuxin Chen. A lower bound for stepsize-based acceleration of gradient descent. arXiv preprint arXiv:2608.10418, 2026. [MOA11] Albert W. Marshall, Ingram Olkin, and Barry C. Arnold. Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics. Springer, New York, 2 edition, 2011. [Mor65] Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273–299, 1965. [Nes83] Yurii E. Nesterov. A method of solving a convex programming problem with convergence rate O(1/k2 ). Soviet Mathematics Doklady, 27(2):372–376, 1983. [Nes04] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Kluwer Academic Publishers, 2004. [NY83] Arkadii S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Chichester, 1983. Translated from the 1979 Russian edition by E. R. Dawson. [Pol64] Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964. [TFZH26] Chung-En Tsai, Ilyas Fatkhullin, Liang Zhang, and Niao He. Lower bounds for anytime acceleration of gradient descent. arXiv preprint arXiv:2607.02053, 2026. [THG17] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1–2):307–345, 2017. [Tsa26] Chung-En Tsai. An improved lower bound for non-anytime gradient descent. Blog post, https://chungentsai.github.io/gd-lower-bounds.html, 2026. [TV23] Marc Teboulle and Yakov Vaisbourd. An elementary approach to tight worst case complexity analysis of gradient based methods. Mathematical Programming, 201(1–2):63–96, 2023. [You53] David Young. On Richardson’s method for solving linear systems with positive definite matrices. Journal of Mathematics and Physics, 32(1–4):243–255, 1953. 19

[ZJ26] Zehao Zhang and Rujun Jiang. Accelerated gradient descent by concatenation of stepsize schedules. SIAM Journal on Optimization, 36(2):1182–1210, 2026. [ZLDC25] Zihan Zhang, Jason Lee, Simon Du, and Yuxin Chen. Anytime acceleration of gradient descent. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 5991–6013. PMLR, 2025.

Hard-Function Construction

This appendix recalls the geometric idea behind the construction used in Lemma 2.1. The formal realization and all projection inequalities are proved in [MC26, Theorem 4.1]; see also [Tsa26] for a complementary geometric exposition. We first explain why this construction is a natural response to long steps. Two motivating facts. Fact A.1 (Ω(n−1 ) Huber lower bound). For every stepsize schedule H, the Huber construction gives Rn (H) ≥

1 . 1 + 2 ∑nk=1 hk

In particular, if hk ≤ 1 for every 1 ≤ k ≤ n, then Rn (H) ≥ 1/(2n + 1). Fact A.1 is proved by setting δ = (1 + 2 ∑k hk )−1 and considering the one-dimensional Huber function ( u2 /2, |u| ≤ δ , φδ (u) = 2 δ |u| − δ /2, |u| > δ . This quadratic–linear function was introduced by Huber [Hub64]. Its use as a tight worst-case instance for constant-step gradient descent appears in [DT14, Theorem 3.2]. See also [AP25b, Footnote 1]. Starting from u1 = 1, all GD iterates stay in the affine region u > δ , where φδ′ (u) = δ . Thus un+1 = 1 − δ ∑k hk , and direct substitution gives 2φδ (un+1 ) = δ . Hence a schedule that improves on the n−1 scale must use steps strictly larger than 1. Fact A.2. In the standard quadratic-chain proof of the classical first-order oracle lower bound [Nes04, Section 2.1.2, Lemma 2.1.5], let Rk = span{e1 , . . . , ek }. The tridiagonal hard quadratic satisfies x ∈ Rk

=⇒

∇ f (x) ∈ Rk+1 .

Consequently, starting from x0 = 0, induction shows that a first-order method satisfying the usual linearspan condition can reveal at most one new coordinate per oracle call. A chain whose length grows with the horizon yields the classical Ω(n−2 ) lower bound [Nes04, Theorem 2.1.7]. The relevant idea is the supply of fresh orthogonal directions: after k calls, part of the hard instance still lies outside the subspace reached by the algorithm. Forcing long steps to switch gradient directions. It is useful to view the construction in [MC26, Theorem 4.1] as a combination of the above two ideas. The Huber function supplies a constant-gradient affine region on which the intervening updates make only one-dimensional progress. Introducing fresh coordinates prevents the selected long steps from repeatedly exploiting the same one-dimensional overshoot. This restricts the convergence rate, thereby establishing a tighter lower bound. More precisely, fix selected indices 0 < t1 < · · · < tq ≤ n,

hti > 1,

set t0 = 0 and divide the schedule into q transition blocks and one terminal block. For 1 ≤ i ≤ q, transition block i contains (hti−1 +1 , . . . , hti ), while the terminal block contains (htq +1 , . . . , hn ). The construction first specifies a desirable trajectory. Place anchors Xi = λi ei ,

1 ≤ i ≤ q + 1, 21

e3 X3 = λ3 e3

ht2 +1 , . . . , hn

ht2 > 1

xn+1 X1 = λ1 e1 e1

, ht

2 −1

1 +1

,...

h 1, .

ht 1 >

. . , ht 1

−1

X2 = λ2 e2 e2

Figure 5: Only the selected long steps (purple arrows) switch the gradient directions. where e1 , . . . , eq+1 are orthonormal. Then, for each 1 ≤ i ≤ q, arrange for the iterates to start at the anchor Xi , make only one-dimensional progress, and reach the next anchor Xi+1 at the final selected long step. As a consequence, the gradient gi for this block is fixed to be gi =

Xi − Xi+1 , Si + hti

1 ≤ i ≤ q.

Note that after the final selected long step lands on the next coordinate-axis anchor Xi+1 , the active gradient changes from gi to gi+1 . After the last selected step, the remaining iterates use gq+1 =

λq+1 eq+1 . 1 + 2Sq+1

Figure 5 illustrates this geometry. Construction of the hard function via a Moreau envelope. The remaining question is how to realize this prescribed piecewise-constant gradient pattern with one globally defined smooth convex function. Intuitively, this is possible by gluing Huber functions together. The selected long steps provide enough room for the landscape of the hard function to change while maintaining its smoothness. More precisely, let C := conv{0, g1 , . . . , gq+1 }, and consider its support function σC (z) := max⟨g, z⟩. g∈C

The support function stores the candidate block gradients as slopes. Now take the Moreau envelope of the support function σC , 1 2 fC (x) := min σC (z) + ∥x − z∥ . z 2 22

Since σC is proper, closed, and convex, its Moreau envelope fC is convex and has a 1-Lipschitz gradient [Mor65, Propositions 5.b, 7.b, and 7.d]. The hard function fC satisfies the distance and projection identities [MC26, Lemma 4.2] 1 1 fC (x) = ∥x∥2 − d(x,C)2 , 2 2

∇ fC (x) = ΠC (x).

Completing the square also gives 1 fC (x) = max ⟨g, x⟩ − ∥g∥2 . g∈C 2 This hard function can be regarded as a multidimensional analogue of the Huber function. On C it equals 1 1 2 2 2 ∥x∥ . On a normal-cone region where ΠC (x) = gi , it equals ⟨gi , x⟩ − 2 ∥gi ∥ and is therefore affine. The trajectory stays in these constant-projection regions between selected long steps. In this sense, the construction retains the quadratic region C and affine outer pieces of the one-dimensional Huber function while using new coordinate axes to keep the effects of several selected long steps separate. Hence prescribing gi as the gradient throughout a block reduces to the geometric condition gi = ΠC (x)

⇐⇒

⟨x − gi , v − gi ⟩ ≤ 0

for every v ∈ C.

Since C is the convex hull of finitely many generators, it is enough to check this inequality at 0, g1 , . . . , gq+1 . The proof in [MC26, Theorem 4.1] parameterizes the positive scales by the amplitude ratios γi := λi+1 /λi . That theorem gives an explicit admissible upper bound for each γi2 . Choosing the ratios within these ranges ensures the projection inequalities along every intended block. Saturating the explicit upper bounds on γi maximizes the final gap fC (xn+1 ) − fC (0) and yields the lower bound in Lemma 2.1.

Properties of J(α, λ ) and Numerical Solution

The proofs of Theorems 1.1 and 1.2 reduce to finding the smallest possible α > 0 for which J(α, λ ) ≤ 0 for some λ > 0; see (13)–(14).2 Accordingly, for each exponent parameter α, we optimize over the scalar parameter λ in (12) and define ˆ J(α) := inf J(α, λ ). (33) λ >0

ˆ It remains to find the smallest α > 0 for which J(α) ≤ 0. The following proposition gives the properties needed to determine α and λ . Proposition B.1. For every α > 0, the function λ 7→ J(α, λ ) is strictly convex and has a unique minimizer λ⋆ (α) ∈ (1/4, 1/2). The function Jˆ is continuous and strictly decreasing. Hence it has a unique zero α⋆ on every interval where it changes sign. Proof. Let uλ = (xλ , yλ ) be the optimizer defining Γλ (w, z), and let H be the Hessian of log Kw,z at uλ . By Lemma 2.4, this optimizer is unique and H is negative definite. Applying the implicit function theorem to the first-order condition ∇x,y log Kw,z (uλ ) = λ 1 shows that uλ is differentiable in λ and that u′λ = H −1 1. Differentiating the optimized value then gives ∂λ Γλ (w, z) = −1⊤ uλ = −(xλ + yλ ), ∂λ λ Γλ (w, z) = −1⊤ H −1 1 > 0. 2 For the anytime case, the inequality must be strict; see (31)–(32).

Consequently, J(α, ·) is strictly convex. To determine the signs of ∂λ J at the endpoints λ = 1/4 and λ = 1/2, we need bounds on the optimizer (x, y). Set a := x/(w + x) and b := y/(z + y). The first-order conditions give λ (x + y) = 1 −

(a − b)2 . 2(a + b − 2ab)

Since a + b − 2ab − (a − b)2 = a(1 − a) + b(1 − b) > 0, this identity yields 1/2 < λ (x + y) ≤ 1. Equality in the upper bound forces a = b. Writing τ = x(w + x)/w = y(z + y)/z, we have w = τ(1 − a)2 /a and z = τ(1 − b)2 /b. Thus equality forces w = z. Therefore 1 < λ (x + y) ≤ 1. (34) 2 Moreover, the upper bound is strict whenever w ̸= z. By (34), x + y ≤ 1/λ , so |∂λ Γλ | has a uniform bound on every compact λ -interval. We may therefore differentiate under the integral in (12) to obtain Z 1/2 ∂λ J(α, λ ) = 2 − 2 xα,λ (t) + yα,λ (t) dt, (35) 0

where (xα,λ (t), yα,λ (t)) is the optimizer corresponding to (w, z) = (Wα (t),Wα (1 − t)). It follows from (35) that ∂λ J(α, 1/4) < 0 and ∂λ J(α, 1/2) > 0. The latter inequality is strict because equality in λ (x + y) ≤ 1 can occur only when w = z, which here happens only at t = 1/2. Thus the unique minimizer lies in (1/4, 1/2). For fixed λ , Wα (t) increases strictly with α, while Γλ decreases strictly in each coordinate. Therefore ˆ 2 ) < J(α ˆ 1 ). J(α, λ ) decreases strictly with α. If 0 < α1 < α2 , evaluating J(α2 , ·) at λ⋆ (α1 ) gives J(α It remains to prove continuity. The estimates in the proof of Lemma 3.2 are locally uniform in (α, λ ). Consequently, the integrand in (12) extends continuously to t = 0, locally uniformly on compact parameter sets, and is locally bounded there. Together with the implicit-function argument above, dominated convergence shows that J is jointly continuous. Since the minimizer always lies in the fixed compact interval [1/4, 1/2], minimizing over that interval gives continuity of J.ˆ Numerical solution.

For u, τ > 0, write Xu (τ) :=

2τ p = fu (τ) − u. 1 + 1 + 4τ/u

For fixed α, λ > 0 and 0 < t ≤ 1/2, put w = Wα (t) and z = Wα (1 − t). The optimizer defining Γλ (w, z) is x = Xw (τ) and y = Xz (τ), where τ is the unique root of (21). At t = 0, we use the continuous extension established above. At this root, 1 1 Γλ (w, z) = log τ + − λ Xw (τ) + Xz (τ) . (36) fw (τ) fz (τ) To evaluate J(α, λ ) and ∂λ J(α, λ ), we solve (21) at each quadrature node and use (36) and (35). For fixed α, ∂λ J(α, ·) is continuous and strictly increasing and has opposite signs at 1/4 and 1/2. Bisection therefore gives λ⋆ (α). A second bisection applied to the continuous, strictly decreasing function Jˆ gives its zero α⋆ . Floating-point computation gives α⋆ ≈ 0.63416058454,

λ⋆ (α⋆ ) ≈ 0.45060731.

(37)

These digits describe the optimized pair but are not used as a rigorous certificate. The proof uses the nearby pair (α, λ ) = (0.6342, 0.4506). A computer-assisted calculation using Arb with directed outward rounding certifies J(0.6342, 0.4506) < −0.0000512188 < −0.00005 < 0, (38) which is the inequality used in the proofs of Theorems 1.1 and 1.2. 24

Proofs for the Anytime Lower Bound

This appendix proves Lemmas 4.1 and 4.2.

C.1

Proof and Intuition of Lemma 4.1

We first explain how the proof of Lemma 4.1 modifies the finite-to-anytime transfer of [TFZH26, Theorem 4.1]. We begin with two lower bounds from one-dimensional hard instances that drive this transfer. For a prefix Hn = (h1 , . . . , hn ), the first one relates Rn (Hn ) to the total stepsize h1:n . Using convex quadratics, [TFZH26, Lemma 2.1] gives 1 . (39) Rn (Hn ) ≥ 4(1 + 2h1:n ) 1 We instead use the standard Huber loss from Fact A.1, which gives the stronger bound Rn (Hn ) ≥ 1+2h , 1:n −p as stated in (2). In particular, if Rn (Hn ) = o(n ) for some p > 1, then h1:n /n → ∞, and the stepsizes are unbounded. The second bound comes from [TFZH26, Lemma 3.1]. Its hard instance is the asymmetric Huber loss  2  u ≥ δ, δ u − δ /2, ψε,δ (u) := u2 /2, (40) −ε ≤ u ≤ δ ,   −εu − ε 2 /2, u ≤ −ε.

It is quadratic near the origin and affine on either side. By choosing ε and δ so that the update with hm > 1 crosses the quadratic region, their lemma proves Rn (Hn ) ≥

(hm − 1)2 . (1 + h1:m−1 )2 (1 + 2hm+1:n )

(41)

We only use the case m = n, which gives p hn − 1 ≤ (1 + h1:n−1 ) Rn (Hn )

when hn > 1.

(42)

The proof of the Ω(n−4/3 ) anytime lower bound in [TFZH26, Theorem 4.1] combines (39), (41), and their Lemmas 2.2 and 2.3. The latter use convex quadratics to control the total stepsize through the largest stepsize. Figure 6 summarizes their argument. Convex quadratics

Total-sum bound (39) cf. [TFZH26, Lemma 2.1]

Asymmetric Huber loss (40)

Largest-step control: Bounding h1:n in terms of maxk≤n hk

Terminal-step bound (42) cf. [TFZH26, Lemma 3.1]

cf. [TFZH26, Lemmas 2.2–2.3]

Ω(n−4/3 ) anytime lower bound for Rn cf. [TFZH26, Theorem 4.1]

Figure 6: Roadmap of the proof of [TFZH26, Theorem 4.1]; see also [TFZH26, Figure 2].

Our proof uses the stronger total-sum bound (2) in place of [TFZH26, Lemma 2.1], retains the terminalstep bound (42) from [TFZH26, Lemma 3.1], and replaces the use of [TFZH26, Lemmas 2.2 and 2.3] with the two more refined tail bounds in (43), valid for every m such that Rn (H)Dm ≤ c0 . The proof of these tail bounds uses the same hard function and variable substitution as the proof of Lemma 2.2. Proof of Lemma 4.1. Fix α > 0, and assume that (28) implies (29), with the same constants ηα ,Cα for every integer q ≥ 2 and every integer 1 ≤ ℓ ≤ ηα q. Fix a finite schedule H = (h1 , . . . , hn ). Recall the notation from Section 3.1. Let a1 ≥ · · · ≥ ar > 0 be the decreasing rearrangement of the positive excesses (hk − 1)+ , and define n

B := 1 + ∑ min{hk , 1},

Ds := B + ∑ a j ,

1 ≤ s ≤ r.

j=s+1

k=1

Part I: Constructing tail bounds. We first prove that there are constants c0 ,C > 0, depending only on α, such that any 1 ≤ m ≤ r satisfying Rn (H)Dm ≤ c0 also satisfies mam ≤ CDm ,

Dm ≤ C(n + 1)1+α m−α .

(43)

Together, these two bounds play the role of [TFZH26, Lemmas 2.2 and 2.3] in our proof. The condition Rn (H)Dm ≤ c0 implies Dm ≤ c0 /Rn (H). The first inequality compares Dm−1 and Dm , since Dm−1 = Dm + am ≤ (1 + C/m)Dm , while the second controls Dm itself. Applying both bounds with m = j gives a j ≤ C(n + 1)1+α j−1−α , whose sum controls the remaining smaller excesses. We now prove the two inequalities in (43). Note that only the proof of the second inequality uses the hypothesis that (28) implies (29). If r = 0, there is nothing to prove. We may therefore assume r ≥ 1. For the moment, let c0 > 0, and let m be arbitrary such that Rn (H)Dm ≤ c0 . We collect the required restrictions on c0 at the end of Part I. The q = 1 case in the proof of Lemma 2.2 gives Rn (H)D1 ≥ 1/4. Under the restriction c0 < 1/4, the case m = 1 cannot satisfy Rn (H)Dm ≤ c0 . We henceforth consider only 2 ≤ m ≤ r. Fix 2 ≤ q ≤ r. Following the notation in the proof of Lemma 2.2, let t1 < · · · < tq be the locations of the q largest positive excesses, with t0 = 0 and tq+1 = n + 1. For 1 ≤ i ≤ q + 1, set Si := hti−1 +1:ti −1 ; for 1 ≤ i ≤ q, define q(Si + 1) q(hti − 1) xi := , ωi := , 1 ≤ i ≤ q, Dq Dq with ∑qi=1 xi < q. Let G be the right-hand side of (1) for these selected indices. Then Lemma 2.1 gives Rn (H) ≥ G, and (17) yields q Rn (H) ≥ , (44) q−1 Dq Eend ∏i=1 Kωi ,ωi+1 (xi , xi+1 ) Step 1. Prove the first inequality in (43). Set βα := 1 + max{e, α}. We claim that sas ≤ βα Ds ,

m ≤ s ≤ r.

(45)

For every m ≤ s ≤ r, we have Ds ≤ Dm , and hence Rn (H)Ds ≤ c0 . Apply (44) with q = s and use the s largest excesses to form x1 , . . . , xs and ω1 , . . . , ωs . Every selected excess is at least as , so ωi ≥ sas /Ds for every 1 ≤ i ≤ s. If sas > βα Ds , then ωi > βα for every i. Define Γ1 3 by Γ1 (w, z) := sup {log Kw,z (x, y) − (x + y)}. x,y>0 3 Here Γ = Γ | 1 λ λ =1 .

For the xi , ωi just obtained with q = s, put ∆s := s − ∑si=1 xi > 0. Since mini ωi > βα , the endpoint estimate in the proof of Lemma 2.3 gives Eend e−(2∆s +x1 +xs ) ≤ Aβα , (46) for some Aβα < ∞ depending only on βα . Combining (46) with the definition of Γ1 gives ( ) s−1

s−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Aβα exp 2s + ∑ Γ1 (ωi , ωi+1 ) . i=1

i=1

Because Γ1 decreases in each coordinate and Γ1 (βα , βα ) = − log βα − 1, s−1

2s + ∑ Γ1 (ωi , ωi+1 ) ≤ 2s + (s − 1)(− log βα − 1). i=1

Put δ := log βα − 1 > 0. Then 2s + (s − 1)(− log βα − 1) = −δ s + log βα + 1. The preceding product is eβ e−δ s , where A eβ := eβα Aβ . Applying (44) with q = s gives therefore at most A α α α Rn (H) ≥

seδ s seδ s s ≥ ≥ R (H), eβ Ds A eβ c0 n Ds Eend ∏s−1 A i=1 Kωi ,ωi+1 (xi , xi+1 ) α α

eβ c0 < 1, then s ≥ m ≥ 2 gives seδ s /(A eβ c0 ) > 1, a contradiction. Hence (45), and thus the first inequality If A α α in (43), holds under this condition. Step 2. Prove the second inequality in (43). eβ c0 < 1, so that Step 1 applies. Put Fs := Ds sα , and choose Assume A α qb ∈ arg min Fs . m≤s≤r

Using (45), Ds−1 = Ds + as , and log(1 + u) ≤ u, we obtain, for every m < q ≤ r, q q Dm 1 q as log = ∑ log 1 + ≤ βα ∑ ≤ βα log . Dq s=m+1 Ds m s=m+1 s Therefore Dq ≥ Dm

βα m . q −(βα −α)

We now prove that Fm ≤ AFr for a constant A depending only on α. Take A ≥ ηα qb > m and βα −α Fqb Dqb qb α Fqb 1 m < , = ≥ . Fm A Fm Dm m qb

. If Fm > AFr , then

Hence m/b q < A−1/(βα −α) ≤ ηα , so m < ηα qb. Because the selected excesses are a1 , . . . , aqb, the decreasing rearrangement of the normalized weights satisfies ω ↓j = qba j /Dqb for 1 ≤ j ≤ qb. For every m ≤ k < qb, the minimizing property of qb gives qb

∑ s=k+1

ωs↓ =

α Dk qb qb qb ∑ as = qb Dqb − 1 ≥ qb k − 1 . Dqb s=k+1

(47)

This inequality, m ≤ ηα qb, and the bound ∑qi=1 xi < qb together verify (28) with q = qb and ℓ = m. Applying (29) gives b

qb−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Cα . i=1

Combining this estimate with (44) and Dqb ≤ Dm ≤ c0 /Rn (H) gives Rn (H) ≥

qb qb ≥ Rn (H), Cα Dqb Cα c0

If, in addition, Cα c0 < 1, then qb/(Cα c0 ) > 1, a contradiction. Hence Fm ≤ AFr under these conditions. Since Dr = B ≤ n + 1 and r ≤ n, Dm mα = Fm ≤ AFr = ADr rα ≤ A(n + 1)nα . Collecting the conditions used above, choose, once and for all, 1 e−1 −1 0 < c0 < min , A ,C . 4 βα α For this choice, the preceding argument proves both inequalities in (43) for every m satisfying Rn (H)Dm ≤ c0 . eβ ,Cα , and A depend only on α, so does c0 . Taking C := max{βα , A} completes Part I. Since βα , A α Part II: The anytime transfer. We now combine Part I with (2) and (42). The remaining proof adapts the finite-to-anytime transfer in [TFZH26, Proof of Theorem 4.1]. Fix a positive infinite schedule. For each prefix Hn , define a1 , . . . , ar , B, Ds as in Part I. Suppose for contradiction that Rn (Hn ) = o n−2(1+α)/(2+α) . Since α > 0, the exponent 2(1 + α)/(2 + α) is greater than 1. The contradiction hypothesis and (2) therefore imply h1:n /n → ∞. Hence the stepsizes are unbounded, and there are arbitrarily large indices n satisfying hn = max hk > 1. 1≤k≤n

(48)

Moreover, since Dr = B ≤ n + 1, Rn (Hn )Dr ≤ (n + 1)Rn (Hn ) = o n−α/(2+α) −→ 0. We may therefore fix one such n, sufficiently large that both (48) and Rn (Hn )Dr ≤ c0 hold. Since hn is the largest stepsize in Hn , its excess is the largest, and hence a1 = hn − 1. Define the cutoff4 $ % 1 m⋆ := p . (49) 4 Rn (Hn ) Since Rn (Hn ) → 0 and ⌊x⌋ ≥ x/2 for x ≥ 2, our sufficiently large choice of n satisfies 1 m⋆ ≥ p . 8 Rn (Hn ) 4We explain the choice of m in Remark C.1. ⋆

(50)

If the number of long steps r ≤ m⋆ , the terminal-step bound (42) gives r

∑ a j ≤ m⋆ a1 ≤ 4 (1 + h1:n ).

j=1

Since h1:n = (B − 1) + ∑rj=1 a j and B − 1 ≤ n, this would imply h1:n = O(n), a contradiction. Thus r > m⋆ . To apply Part I with m = m⋆ , we first prove that Rn (Hn )Dm⋆ ≤ c0 . Suppose instead that Rn (Hn )Dm⋆ > c0 . Since r > m⋆ , Rn (Hn )Dr ≤ c0 , and Ds decreases with s, there is a smallest index q⋆ > m⋆ such that Rn (Hn )Dq⋆ ≤ c0 . Applying both inequalities in (43) with m = q⋆ gives C Dq⋆ −1 = Dq⋆ + aq⋆ ≤ 1 + Dq⋆ ≤ C(n + 1)1+α q−α ⋆ . q⋆ Using q⋆ > m⋆ and (50), we obtain Rn (Hn )Dq⋆ −1 ≤ Cn1+α Rn (Hn )1+α/2 (2+α)/2 2(1+α) = o(1), = C n 2+α Rn (Hn ) contradicting the minimality of q⋆ , which gives Rn (Hn )Dq⋆ −1 > c0 . Hence Rn (Hn )Dm⋆ ≤ c0 .

(51)

For every m⋆ < j ≤ r, D j ≤ Dm⋆ , so Rn (Hn )D j ≤ c0 . Applying (43) with m = j gives aj ≤

CD j ≤ C(n + 1)1+α j−1−α . j

For 1 ≤ j ≤ m⋆ , we have a j ≤ a1 = hn − 1, so the terminal-step bound (42) controls the first sum below. For m⋆ < j ≤ r, sum the preceding estimate and use (50) for the second sum: m⋆

∑ a j ≤ m⋆ a1 ≤ 4 (1 + h1:n ),

j=1 r

∞

∑ a j ≤ C(n + 1)1+α ∑

j=m⋆ +1

j−1−α

j=m⋆ +1

1+α

≤ C(n + 1)

1+α m−α Rn (Hn )α/2 . ⋆ ≤ C(n + 1)

Using h1:n = (B − 1) + ∑ j a j and B − 1 ≤ n, we absorb 41 h1:n into the left-hand side to obtain h1:n ≤ C n + n1+α Rn (Hn )α/2 . Multiplying by Rn (Hn ) gives Rn (Hn )h1:n ≤ C nRn (Hn ) + n1+α Rn (Hn )1+α/2 2(1+α) (2+α)/2 2+α Rn (Hn ) = o(1). = C nRn (Hn ) + n But (2) gives Rn (Hn )(1 + 2h1:n ) ≥ 1, a contradiction. Therefore 2(1+α)

lim sup n 2+α Rn (Hn ) > 0. n→∞

(52)

Remark C.1. We explain the choice of m⋆ in (49).p For the chosen n, hn = max1≤k≤n hk > 1, so a1 = hn − 1. The terminal-step bound (42) gives a1 ≤ (1 + h1:n ) Rn (Hn ). Since a j ≤ a1 , every cutoff m satisfies m

∑ a j ≤ m(1 + h1:n ) Rn (Hn ).

j=1

The head estimate only requires m⋆ ≤ εRn (Hn )−1/2 , where ε ∈ (0, 1) is fixed. Indeed, the preceding inequal⋆ ity then gives ∑mj=1 a j ≤ ε(1 + h1:n ), which can be absorbed in (52) since ε < 1. In (49), we take ε = 1/4. Part I then gives 1+α Rn (Hn )α/2 . ∑ a j ≤ C(n + 1)1+α m−α ⋆ ≤ C(n + 1) j>m⋆

Combining the head and tail estimates with h1:n = (B − 1) + ∑ j≤m⋆ a j + ∑ j>m⋆ a j recovers (52).

C.2

Proof of Lemma 4.2

We adapt the proof of Lemma 2.5 to establish (30). Proof. Step 1. Eliminate the xi ’s. Taking k = q − 1 in (28) gives mini ωi ≥ α, the only consequence of the tail conditions used in the proof of Lemma 2.3. Hence the same proof gives ( ) q−1

q−1

Eend ∏ Kωi ,ωi+1 (xi , xi+1 ) ≤ Cα,λ exp 2λ q + ∑ Γλ (ωi , ωi+1 ) . i=1

i=1

It remains to bound the sum in the exponent. Step 2. Set aside the ℓ unconstrained largest weights. We first split the consecutive-pair sum from Step 1 into an odd matching and an even matching, according to whether i is odd or even. (ω1 , ω2 ), (ω3 , ω4 ), . . .

(ω2 , ω3 ), (ω4 , ω5 ), . . . .

and

The tail inequalities in (28) do not constrain the ℓ largest weights ω1↓ , . . . , ωℓ↓ . Mark their positions in the chronological sequence and delete, from each matching, every pair containing one of these positions. Each marked position belongs to at most one pair in each matching, so at most 2ℓ terms are deleted in total. Let M0 and M1 denote the remaining odd and even matchings, respectively, and put kν := |Mν |,

dν := q − 2kν .

Thus dν is the number of positions not used by Mν . Since Mν contains none of the ℓ marked positions, dν ≥ ℓ. Before any pair is deleted, each of the odd and even matchings leaves at most two positions unused. Deleting a pair creates two additional unused positions, and at most ℓ pairs are deleted from either matching. Hence ℓ ≤ dν ≤ 2ℓ + 2. (53) (q)

(q)

Recall the comparison weights w̄s from (23). They satisfy w̄q ≤ · · · ≤ w̄2 and, for every ℓ ≤ m < q, q

(q)

∑ w̄s = q

h q α

s=m+1

i −1 .

Hence (28) gives, for every 1 ≤ j ≤ q − ℓ, q

∑

ωs↓ ≥

s=q− j+1

∑

(q)

w̄s .

(54)

s=q− j+1

Step 3. Identify the maximizing matching and compare it with the integral. ↓ After ordering the remaining weights increasingly, each Mν is a kν -edge matching on (ωq↓ , . . . , ωℓ+1 ). The proof of Lemma 2.5 shows that Φkν ,λ is symmetric, convex, and coordinatewise decreasing. Hence Lemma 3.1, (54), and (25) give, for ν ∈ {0, 1},

∑

↓ Γλ (ωi , ω j ) ≤ Φkν ,λ (ωq↓ , . . . , ωℓ+1 )

{i, j}∈Mν (q)

(q)

≤ Φkν ,λ (w̄q , . . . , w̄ℓ+1 ) kν (q) (q) = ∑ Γλ w̄q+1− j , w̄dν + j .

(55)

j=1

We next compare the explicit matching sum in (55) with its corresponding Riemann integral. Recall that Wα (t) = αt −1−α for 0 < t ≤ 1. By Lemma 3.2, gα,λ (t) := Γλ (Wα (t),Wα (1 − t)),

1 0<t ≤ , 2

extends continuously to t = 0. Define Z 1/2

Iα,λ :=

gα,λ (t) dt.

We use the following shifted Riemann-sum estimate. For every integer 0 ≤ k ≤ ⌊(q − 1)/2⌋, set d := q − 2k, so d ≥ 1. Then k (q) (q) w̄ , w̄ (56) Γ ∑ λ q+1− j d+ j ≤ qIα,λ +Cα,λ (d + 1). j=1

(q)

Set Mα,λ := max{0, Γλ (α, α)}. To prove (56), first suppose d ≥ q/4. Since every w̄s ≥ α, each summand is at most Mα,λ . Therefore k

∑

(q) (q) Γλ (w̄q+1− j , w̄d+ j ) − qIα,λ ≤ q

j=1

Mα,λ + |Iα,λ | ≤ Cα,λ d. 2

Now suppose d < q/4. By the mean-value theorem, for each 2 ≤ s ≤ q, there is ξs ∈ (s − 1, s) such that (q)

w̄s = Wα (ξs /q). The Lipschitz estimate in Lemma 3.2 applies to (u, v) 7→ Γλ (Wα (u),Wα (v)) on [0, 1/2] × [1/2, 1]. For each j such that u j := (d + j)/q ≤ 1/2, ξd+ j 1 −uj ≤ , q q

ξq+1− j d +1 − (1 − u j ) ≤ . q q

Symmetry and the Lipschitz estimate give d +1 (q) (q) Γλ w̄q+1− j , w̄d+ j ≤ gα,λ (u j ) +Cα,λ . q 31

Since 1 ≤ j ≤ k = (q − d)/2, there are at most d + 1 indices with u j > 1/2. For these indices, both ξd+ j /q and ξq+1− j /q lie in [1/4, 1], because d < q/4. Thus both arguments of Γλ lie in [α, α 41+α ], and the total contribution of these terms is at most Cα,λ (d + 1). For the other indices, the grid u j has mesh 1/q and begins at (d + 1)/q. The portion of [0, 1/2] not covered by the corresponding Riemann cells has total length at most (d + 1)/q. The boundedness and Lipschitz continuity of gα,λ therefore give

∑

gα,λ (u j ) ≤ qIα,λ +Cα,λ (d + 1).

j: u j ≤1/2

Summing the error Cα,λ (d +1)/q over these indices and adding the at most d +1 terms with u j > 1/2 proves (56). Apply (56) to the odd and even matchings M0 and M1 , with (k, d) = (kν , dν ). Add back the at most 2ℓ terms deleted in Step 2. Since ωi ≥ α for every i by Step 1, each deleted term is at most Mα,λ . Since dν ≤ 2ℓ + 2, we obtain q−1

∑ Γλ (ωi , ωi+1 ) ≤ 2qIα,λ +Cα,λ (ℓ + 1).

i=1

Combining the estimate from Step 1 with (57) and using J(α, λ ) = 2λ + 2Iα,λ from (12) proves (30).

(57)

Improved Gradient Descent Lower Bounds Beyond Nesterov

Analyze & explore related research in Conceptio

Related documents