Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration Yuhan Ye* MIT [email protected]
Kaizhao Liu* MIT [email protected]
arXiv:2609.09152v1 [math.OC] 8 Sep 2026
September 9, 2026
Abstract We study how far gradient descent (GD) can be accelerated by predetermined stepsizes nonnegative √ √ in smooth convex optimization. Writing psil = log2 (1 + 2), we prove an Ω n−psil −O( log log n/ log n) non-anytime lower bound. Inthe anytime setting, every infinite nonnegative schedule has infinitely √ 2p − 1+psil −O( log log n/ log n) sil . Together with the silver-schedule upper many horizons with error Ω n 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.
* Authors are listed in random order.
1
Contents 1
Introduction 1.1 Stepsize Schedules for Accelerating GD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3
2
Motivation and Technical Overview
4
3 (Almost) Tight Non-Anytime Lower Bound 3.1 Proof of Lemma 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Proof of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 9
4 (Almost) Tight Anytime Lower Bound
13
5
13
Concluding Remarks
A Proofs for the Hard-Function Construction A.1 Proof of Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Proof of Lemma 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Proof of Lemma 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16 16 18 18
B Proofs for the Global Cost Analysis B.1 Proof of Lemma 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Proofs of Lemmas 3.4 and 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Proof of Lemma 3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.4 Proof of Lemma 3.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.5 Proof of Lemma 3.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.6 Proofs of Lemmas 3.9 and 3.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.7 Proof of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20 20 20 21 22 24 24 26
C Proofs for the Anytime Lower Bound 27 C.1 Proof of Lemma 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 C.2 Proof of Theorem 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2
1
Introduction
We consider the unconstrained minimization of a convex L−smooth function f : Rd → R. One of the most fundamental methods for this problem is gradient descent (GD), which dates back to Cauchy [1847]. Given a stepsize schedule H = (h1 , . . . , hn ) ∈ [0, ∞)n fixed before the optimization begins, GD iterates xk = xk−1 − hk ∇ f (xk−1 ),
1 ≤ k ≤ n.
In this paper, we study how far this basic method can be accelerated using only predetermined stepsizes. Let FL (Rd ) be the class of convex L-smooth functions on Rd with a nonempty set of minimizers. We measure the worst-case convergence rate of a schedule H by f (xn ) − f (x∗ ) , L 2 d∈N f ∈FL (Rd ) x∗ ∈arg min f x0 ∈Rd \{x∗ } 2 ∥x0 − x∗ ∥
Rn (H) := sup
sup
sup
sup
rn∗ :=
inf
H∈[0,∞)n
Rn (H).
(1)
In the non-anytime (finite-horizon) setting, the schedule may be chosen separately for each fixed horizon n, and rn∗ is the best worst-case error achievable at that horizon. 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 has an O(n−1 ) convergence rate [Levitin and Polyak, 1966; Nesterov, 2004]. Classical acceleration methods alter the GD iteration by adding momentum or auxiliary sequences, as in the heavy-ball method of Polyak [1964] and the accelerated method of Nesterov [1983]. Within the broader class of first-order methods, Nesterov’s method attains the optimal O(n−2 ) rate for smooth convex objectives, matching the Ω(n−2 ) oracle lower bound of Nemirovsky and Yudin [1983].
1.1
Stepsize Schedules for Accelerating GD
Since GD with predetermined stepsizes is a special class of first-order method, the classical Ω(n−2 ) oracle lower bound continues to apply. For many years, however, the standard O(n−1 ) rate remained the best general upper bound known. This left open whether stepsize design alone could yield a faster rate. This question was answered affirmatively by schedules that combine occasional long steps with recursive constructions [Altschuler and Parrilo, 2025; Grimmer, 2024; Grimmer et al., 2025a,b]. At horizons n = 2k − √ −p sil 1, the silver schedule attains O(n ), where psil := log2 (1 + 2) ≈ 1.2716 [Altschuler and Parrilo, 2025]. Compositions of stepsize schedules attain the same exponent at every prescribed horizon [Grimmer et al., 2025a]. At original silver horizons, Wang et al. [2026] established tight lower bounds for the silver schedule. In the anytime setting, Zhang et al. [2025] attain O(n−pany ), where pany := 2psil /(1 + psil ) ≈ 1.1195. Recently, a sequence of lower bound results has narrowed the gaps to these rates. Ma and Chen [2026] proved an Ω(n−1.932 ) non-anytime lower bound, and a subsequent blog post by Tsai [2026] sharpened it √ to Ω(n− 3 ). For the anytime setting, Tsai et al. [2026] proved an Ω(n−4/3 ) lower bound. In our previous work [Ye and Liu, 2026], we proved an Ω(n−1.6342 ) non-anytime lower bound and an Ω(n−1.2408 ) anytime lower bound for arbitrary real-valued stepsizes. To our knowledge, these remain the strongest known lower bounds when negative stepsizes are allowed. For nonnegative schedules, Jung et al. [2026] further improved the non-anytime and anytime lower bounds to Ω(n−1.4500 ) and Ω(n−1.1837 ), respectively.
1.2
Main Results
For nonnegative schedules, we close both remaining gaps in the polynomial exponents. Theorem 1.1. There is an absolute constant C > 0 such that, for every sufficiently large n, q − psil +C logloglogn n ∗ rn ≥ n .
3
(2)
Theorem 1.2. There is an absolute constant C > 0 such that every infinite nonnegative schedule has infinitely many horizons n for which q log log n log n
− pany +C
Rn (Hn ) ≥ n
(3)
.
Together with the corresponding upper bounds [Altschuler and Parrilo, 2025; Grimmer et al., 2025a; Zhang et al., 2025], our results identify psil and pany as the optimal polynomial convergence exponents in the non-anytime and anytime settings, respectively. n−1.932 n−2
Ma & Chen (2026) Nemirovsky & Yudin (1983)
n −psil
n−1.6342 n−1.7321 Tsai (2026)
Ye & Liu (2026)
n−1
n−1.4500 This work
Jung et al. (2026)
Constant stepsize
Altschuler & Parrilo (2025)
Non-anytime Lower bound
Upper bound
This work Jung et al. (2026)
Anytime Nemirovsky & Yudin (1983)
Tsai et al. (2026)
Zhang et al. (2025) Constant stepsize
Ye & Liu (2026)
n−2
n−1.3334 √ psil = log2 (1 + 2) ≈ 1.271553,
n−1.1837 n−1.2408 n −pany
n−1
pany = 2psil /(1 + psil ) ≈ 1.119545
Figure 1: Lower and upper bounds for GD with predetermined stepsizes. Organization. Section 2 gives an overview of the proofs. Section 3 proves the non-anytime result, and Section 4 proves the anytime result. Deferred arguments appear in the appendices.
2
Motivation and Technical Overview
Replacing f by f /L and each hk by Lhk leaves the GD iterates and Rn unchanged, so we assume L = 1 throughout. We first recall how previous constructions of Jung et al. [2026]; Ma and Chen [2026] use selected steps to change the gradient direction. Selecting the checkpoints. Fix a nonnegative schedule h = (h1 , . . . , hn ) and select indices T = {t1 < · · · < tk } ⊆ {1, . . . , n}, which we call checkpoints. Set t0 = 0, tk+1 = n + 1, and define bi := hti
(1 ≤ i ≤ k),
si :=
ti −1
∑ ht
t=ti−1 +1
(1 ≤ i ≤ k + 1).
(4)
Here bi is the selected stepsize at time ti , and si is the total stepsize of the intervening updates, indexed by ti−1 < t < ti . The last sum sk+1 covers the steps after the final checkpoint. Figure 2 illustrates this notation. For selected long steps, Ma and Chen [2026, Theorem 4.1] construct a hard function whose gradient stays constant during the intervening updates and changes after each selected step. See also Ye and Liu [2026, Appendix A] for a geometric illustration of the trajectory. Their hard function is globally defined depending on all the coordinates. Jung et al. [2026, Section 2] instead construct a summation of local 4
t2
t1
tk tk−1
···
h1
···
b1 = ht1
s1
b2 = ht2
s2
··· ···
···
bk−1 = htk−1
bk = htk
sk
···
hn
sk+1
Figure 2: The selected stepsizes are bi = hti . Each brace marks the total stepsize si of the intervening updates. bivariate function that maintains a smilar trajectory where gradient stays constant during the intervening updates, obtaining the following improved lower bound. Fact 2.1 (Jung et al., 2026, Lemma 2.3). For every positive schedule h and every checkpoint set T , 2 k bi 1 . Rn (h) ≥ 4(1 + sk+1 ) ∏ i=1 2(2 + si )
(5)
n For k = 0, the product is empty and s1 = ∑t=1 ht .
Specifically, their construction uses the one-sided Huber function z ≤ 0, 0, 2 Hδ (z) := z /2, δ > 0, 0 ≤ z ≤ δ, δ z − δ 2 /2, z ≥ δ ,
(6)
and joins adjacent coordinates through F(x) :=
1 1 k Hδi x(i) − x(i+1) − τi + Hδk+1 x(k+1) − τk+1 . ∑ 4 i=1 2
The parameters δi > 0 and activation thresholds τi ≥ 0 are chosen based on the stepsizes and the selected checkpoints [Jung et al., 2026, Section 2]. Starting from the first coordinate, the selected step of size bi activates component i + 1, while all later components remain inactive.1 This step raises coordinate i + 1 above its activation threshold, allowing the next component to contribute to the gradient. The final onedimensional component gives the objective-gap lower bound in (5). They √ then optimize over checkpoint sets and analyze the resulting bound recursively, obtaining the Ω(n− log2 (1+ 3) ) non-anytime lower bound [Jung et al., 2026, Section 3]. The bottleneck. The coefficient 2 of si in (5) suggests where to improve the construction. During the intervening updates, component i stays in its affine region and contributes a gradient proportional to ei − ei+1 . Its contribution decreases coordinate i and increases coordinate i + 1 by the same amount. Both motions decrease the difference x(i) − x(i+1) that keeps the component active. To keep component i + 1 inactive during the intervening updates, its activation threshold is set to the value of coordinate i + 1 just before the update with stepsize bi . Only the additional increase produced by this update is then passed to the next component. The resulting transfer ratio is bi /[c(2 + si )], with c = 2. Following the exponent calculation 1A component is active at an iterate if its gradient there is nonzero, and inactive otherwise.
5
√
in [Jung et al., 2026, Section 3], a coefficient c of si suggests a lower bound of order n− log2 (1+ 1+c) . This motivates our two-coordinate hard function, which changes the gradient direction during the intervening updates to make c arbitrarily close to 1, improving the lower-bound exponent toward the silver exponent. Our innovation: switching the gradient direction during the intervening updates. To reduce the coefficient c of si , we modify the local hard function on coordinates i and i + 1. We initially keep the gradient horizontal and then turn it toward the negative x(i+1) direction.2 This decreases coordinate i without increasing coordinate i + 1 too much at first. Near time ti , we turn the gradient toward (ε, −1), so the selected step of size bi is mostly used to increase coordinate i + 1 rather than to decrease in coordinate i. Fix ε, γ > 0 and set q p 2 c = 1 + 2γ + ε , R = ε 2 + (1 + γ)2 . We choose gradient vectors on the circular arc of radius R centered at (0, γ), joining (c, 0) to (ε, −1) in the quadrant {v(1) ≥ 0, v(2) ≤ 0}. Here v = (v(1) , v(2) ) is a two-coordinate gradient vector, not an iterate position. Its two coordinates will correspond to coordinates i and i + 1 of the full construction. Let K be the convex hull of this arc and the origin. Its support function and Moreau envelope are 1 2 σK (z) = max⟨v, z⟩, env1 σK (r) = min σK (z) + ∥r − z∥ . v∈K 2 z∈R2 The envelope is convex and 1-smooth, and its gradient is ∇ env1 σK (r) = ΠK (r), where ΠK denotes Euclidean projection onto K. To obtain a GD trajectory for the prescribed stepsizes, we construct it backward. Write α1 , . . . , αm for the steps in this two-coordinate problem, r j for its iterate after j steps, and v j = ΠK (r j ) for the corresponding gradient. We fix the point and gradient just before the selected update to be rm = vm = (ε, −1). For j = m, m − 1, . . . , 1, choose the preceding point and gradient to satisfy r j−1 = r j + α j v j−1 ,
v j−1 = ΠK (r j−1 ).
The first identity is the GD update read backward. The second ensures that the chosen vector is the gradient of the same smooth convex function. The circular geometry gives an explicit solution. Once the backward gradient reaches (c, 0), all earlier gradients remain horizontal. If the intervening updates have small total stepsize, the first gradient may lie partway along the arc. The total stepsize spent turning is bounded by a constant depending only on ε, γ. The shift γ > 0 allows the gradient direction to change as we construct the trajectory backward. With γ = 0, the gradient would remain at (ε, −1). Keeping ε > 0 lets a sufficiently large bi move the first coordinate far enough to put the old component into a region where it remains zero as the next component runs. Figure 3 shows the local gradients on the left and the resulting iterate path on the right. We write Φi for the scaled and translated component acting on coordinates i, i + 1 of the full objective. The gray region (i+1) marks where this component vanishes. The next component has activation level ℓi+1 = xti −1 , the value of coordinate i + 1 just before taking the step of size bi . From xti onward, that coordinate may decrease as the next component runs, but it never falls below ℓi+1 . The old component therefore remains inactive. 2 Here horizontal means that the gradient has zero component in coordinate i + 1, while vertical means that it has zero component
in coordinate i. The selected update uses a gradient proportional to (ε, −1), which is nearly vertical for small ε.
6
v(2)
(a)
Local gradients
(b)
GD iterates
x(i+1)
(0, γ)
xti R Inactive ∇Φi = 0
(c, 0) v(1)
0
hti = bi
xti −1
ℓi+1
Di Gi = Di+1 Active x(i)
0
ℓi
(ε, −1)
Di
xti−1
Figure 3: Local gradients (left) and iterates (right). The step of size bi (orange) activates the next component. (i)
The improved hard-function bound. Let ℓi be the activation level of component i. At xti−1 , Di = xti−1 − ℓi is the amount by which coordinate i exceeds this level. We start with D1 = 1. After scaling and joining the components, the step of size bi leaves coordinate i + 1 a distance Di+1 = Di Gi above ℓi+1 , where Gi =
bi . c(a + si ) + εbi
The constant a depends only on ε, γ. The coefficient of si is now c, which can be made arbitrarily close to 1, instead of 2. The final bound introduce a constant a, a lower bound on bi , and the additional term εbi , made precise in the following lemma. p Lemma 2.2 (Checkpoint transfer bound). Fix ε, γ > 0 and let c := 1 + 2γ + ε 2 . There are finite constants a = a(ε, γ) and B0 = B0 (ε) such that, for every nonnegative schedule and every checkpoint set whose selected steps satisfy bi ≥ B0 , 2 k bi 1 . (7) Rn (h) ≥ 4(1 + sk+1 ) ∏ i=1 c(a + si ) + εbi n For k = 0, the product is empty and s1 = ∑t=1 ht .
We explain the construction in Section 3.1 and give the detailed verifications in Appendix A. The constants a and B0 may grow as ε, γ decrease, so we must keep track of them when choosing the parameters. From the construction to the main lower bounds. To use this bound, we must choose checkpoints that keep the product ∏ki=1 Gi large relative to the total stepsize sk+1 . We express this choice as a cost minimization and bound the cost recursively, following Jung et al. [2026, Section 3]. The new term εbi prevents a direct substitution into their recursion. Although ε is small, bi has no upper bound, so εbi need not be small relative to c(a + si ) and cannot be absorbed into a uniformly over schedules. We include the term εbi in the recursion and bound the cost using Lemmas 3.7 and 3.8. This gives an Ω(n−p ) non-anytime lower bound for every p > psil . Keeping track of the constants as p ↓ psil gives Theorem 1.1, as shown in Section 3.2. For the anytime result, we follow the approaches of Tsai et al. [2026, Section 4.1] and Jung et al. [2026, Section 4]. At horizons where the last step is the largest so far, we compare the total stepsize with that largest step and the final error. Using our stronger construction gives the exponent 2p/(1 + p) at infinitely many horizons. Tracking the constants as p ↓ psil then yields Theorem 1.2, as shown in Section 4. 7
3
(Almost) Tight Non-Anytime Lower Bound
We first explain how to construct and join the local hard functions in Lemma 2.2. We then give the lemmas that complete the proof of Theorem 1.1. The detailed verifications are in Appendix A for the construction and Appendix B for the cost analysis.
3.1
Proof of Lemma 2.2
p Fix ε, γ > 0 and let c = 1 + 2γ + ε 2 . The construction has two parts. First, we build a two-coordinate function for the intervening updates and the selected step that follows them. We then join copies of this function, keeping earlier and later components inactive while the current one runs. Choosing the gradient directions. Use the arc and convex set K from Section 2. Because ∇ env1 σK (r) = ΠK (r), the backward construction must satisfy both the GD update and the projection condition. The following lemma guarantees this for any given stepsizes α j and bounds the total stepsize spent turning. Lemma 3.1 (Backward trajectory). There is a finite constant H = H(ε, γ) such that, for every m ≥ 0 and every α1 , . . . , αm ≥ 0, there are points r0 , . . . , rm and vectors v0 , . . . , vm on the arc satisfying rm = vm = (ε, −1),
r j = r j−1 − α j v j−1
Moreover,
∑
v j = ΠK (r j ) (0 ≤ j ≤ m).
(1 ≤ j ≤ m),
1≤ j≤m v j−1 ̸=(c,0)
α j ≤ H.
The proof and an explicit formula for H are given in Section A.1. The following lemma records both properties. Lemma 3.2 (Two-coordinate transfer). There is a finite constant C0 = C0 (ε, γ) with the following property. Let m ≥ 0, α1 , . . . , αm ≥ 0, S = ∑mj=1 α j , b ≥ 1 + ε −2 , and A ≥ C0 . Moreover, the function satisfies f (x, y) = 0
if x ≤ 0, y ≥ 0,
f (U, y) = 0
if y ≥ Y.
Only the additional height G is passed to the next component. The first zero region keeps a component inactive before its turn. The second keeps it inactive afterward, provided that its first coordinate stays at U and its second coordinate stays at least Y . The coordinate bounds ensure that these conditions hold when we join the components. The bound from Lemma 3.1 controls the vertical displacement by a constant, while the horizontal displacement is at most cS. Scaling by (cS + εb + A)−1 gives the stated transfer ratio. The construction of f and the verification of both zero regions are in Section A.2. Combining the local hard functions. For each i, we apply Lemma 3.2 with the local stepsizes specified below to obtain a function fi . We scale and translate fi to form Φi , then define F as half the sum of these components and a final one-dimensional Huber function, as in (55). Each coordinate appears in at most two 1-smooth terms, so this makes the full objective F 1-smooth. Because of the factor 1/2, a GD step of size ht corresponds to a local step of size ht /2. Choose B0 = 2(1 + ε −2 ) and a ≥ max{2, 2C0 /c, 2B0 }. put m = ti − ti−1 − 1 and apply Lemma 3.2 with αj =
hti−1 + j 2
(1 ≤ j ≤ m),
S= 8
si , 2
b=
bi , 2
A=
ca . 2
Its transfer ratio is
bi . c(a + si ) + εbi Write fi ,Ui ,Yi for the function and coordinates supplied by Lemma 3.2. Gi =
D1 := 1,
ℓ1 := 0,
Di+1 := Di Gi ,
ℓi+1 := DiYi
For x ∈ Rk+1 , define the component acting on coordinates i, i + 1 by ! (i) − ℓ x(i+1) x i , . Φi (x) := D2i fi Di Di
(1 ≤ i ≤ k).
(8)
(9)
This scaling preserves 1-smoothness, while the first input measures height above ℓi . x(i) = ℓi + DiUi ,
x(i+1) ≥ ℓi+1 = DiYi .
Thus the two inputs to fi remain Ui and at least Yi , respectively, so its second zero region keeps Φi inactive. The first zero region keeps later components inactive until their turn. The induction verifying these coordinate relations is in Section A.3. With δ = D/(1 + sk+1 ), the final Huber calculation gives 2 k D2 1 bi F(xn ) − min F = = . 4(1 + sk+1 ) 4(1 + sk+1 ) ∏ i=1 c(a + si ) + εbi The construction starts at e1 and has a minimizer at the origin, so the initial distance is 1. Under the normalization in (1), Rn (h) is at least twice this value. Dropping the factor 2 gives Lemma 2.2. When there are no checkpoints, the same Huber calculation applies with D = 1. The smoothness and final-value calculations are also given in Section A.3.
3.2
Proof of Theorem 1.1
The transfer bound in Lemma 2.2 holds for every admissible checkpoint set. We choose the checkpoints to obtain a lower bound that holds for every stepsize schedule. The cost formulation and the analysis of tight checkpoint sets follow the framework of Jung et al. [2026, Section 3 and Appendix C]. We account for the additional εbi in the splitting bound of Lemma 3.7, then apply that bound recursively in Lemma 3.8. Throughout this subsection, fix 0 < ε < 1/2 and γ > 0, and set p ε c := 1 + 2γ + ε 2 , d := , χ := c − ε = c(1 − d). (10) c Choose the constants of Lemma 2.2 so that a ≥ 2B0 + 2 and a ≥ 2. Enlarging a preserves its transfer bound. In particular, 0 < d < 1 and χ > 0. We may choose the parameter λ ≥ a freely. For a schedule h ∈ [0, ∞)n , use the checkpoint notation T, bi , si from (4). Define k c(a + si ) Ψλ (T ; h) := (λ + sk+1 ) ∏ ε + , (11) bi i=1 Vλ (h) :=
min
T ⊆{1,...,n}
Ψλ (T ; h),
Un (λ ) := sup Vλ (h). h∈[0,∞)n
(12)
n A checkpoint set selecting a zero step has cost +∞. The empty set has cost λ + ∑t=1 ht , and U0 (λ ) = λ . Each factor in the product is G−1 , and λ + s accounts for . Thus V (h) is the best cost for a given k+1 λ i schedule, while Un (λ ) is the worst such cost over all schedules. Although Vλ minimizes over all checkpoint sets, deleting a selected step of size 0 < b ≤ a/2 from a finite-cost set strictly lowers its cost. Thus every minimizing set satisfies bi > a/2 ≥ B0 , so Lemma 2.2 applies. The following lemma converts this cost bound into a lower bound on the optimization error. Its proof, including the deletion argument, is in Section B.1.
9
Lemma 3.3 (Cost lower bound). For every n ≥ 0, h ∈ [0, ∞)n , and λ ≥ a, Rn (h) ≥
λ −1 . Vλ (h)2
(13)
Call T tight if Ψλ (T ; h) = Vλ (h). The next two lemmas describe the tight sets at a schedule maximizing Vλ . Their proofs are in Section B.2. Lemma 3.4 (Log-submodularity). For every positive schedule h ∈ (0, ∞)n and every two checkpoint sets A, B, Ψλ (A; h)Ψλ (B; h) ≥ Ψλ (A ∩ B; h)Ψλ (A ∪ B; h). (14)
The inequality is strict when A and B are disjoint and nonempty. Consequently, tight sets are closed under unions and intersections, and two nonempty tight sets cannot be disjoint.
Lemma 3.5 (Extremal schedules). For every n ≥ 1 and λ ≥ a, Un (λ ) is finite, Un (λ ) > Un−1 (λ ), and the supremum defining Un (λ ) is attained by a positive finite schedule. At every maximizing schedule, the empty set and at least one nonempty checkpoint set are tight. For the cost Ψλ , these lemmas do not yet give a tight set consisting of one checkpoint. We obtain one below by changing variables and maximizing a different quantity. Rewriting the checkpoint cost. Now take a maximizing schedule from Lemma 3.5 and choose any nonempty tight set T . For its bi and si , put Bi := (1 − d)bi ,
Λ := λ + sk+1 .
gi := si + dbi ,
These variables satisfy
(15)
χ(a + gi ) c(a + si ) = + ε. Bi bi
gi + Bi = si + bi ,
When it is selected, the second identity shows that its cost factor is unchanged. These substitutions change only the cost formula, not the GD schedule. For the splitting argument, allow arbitrary g1 , . . . , gk ≥ 0, B1 , . . . , Bk ≥ 0, and Λ ≥ a. S = {i1 < · · · < im } ⊆ {1, . . . , k}, with i0 = 0, set ij
L j (S) :=
∑
gr +
r=i j−1 +1
i j −1
∑
Br ,
r=i j−1 +1
Y (S) := Λ + ∑ (gr + Br ). r>im
Define the auxiliary cost m
e Λ (S; g, B) := Y (S) ∏ χ(a + L j (S)) , Ψ Bi j j=1 k
e Λ (∅; g, B) := Λ + ∑ (gi + Bi ). Ψ
(16) (17)
i=1
A subset containing an index with Bi = 0 has cost +∞. For the variables in (15), every subset cost is preserved.
10
Lemma 3.6 (Preservation of every subset cost). For every S ⊆ {1, . . . , k}, e Λ (S; g, B) = Ψλ ({ti : i ∈ S}; h). Ψ
(18)
The proof is in Section B.3. Since both T and the empty set have cost Un (λ ), the empty set minimizes e ΨΛ . We also need to select additional checkpoints among the intervening updates. Let h(i) be the sequence of stepsizes for the updates indexed by ti−1 < t < ti . An insertion that lowered its local cost would lower the global cost of T , contradicting tightness. As proved in Section B.3, this gives Va+dbi (h(i) ) = a + si + dbi
Vλ (h(k+1) ) = λ + sk+1 .
(1 ≤ i ≤ k),
(19)
These identities will let us bound the cost of each h(i) in terms of its number of updates. The next lemma bounds the full cost in terms of the costs of the individual sequences h(i) . We keep the sum over checkpoints on its left side to cancel terms introduced by the substitution. The exponent ν will give a lower-bound exponent p = 1/ν. Lemma 3.7 (Weighted splitting). Fix ν ∈ [1/2, 1) and κ ≥ 0. Suppose that, for every x, y ≥ a and B > 0, the relations w = x + y + B − a and wB = χxy imply wν + κBν ≤ xν + yν .
(20)
e Λ (∅; g, B). Then For any auxiliary problem (16)–(17) in which the empty set is a minimizer, write W = Ψ k
k
i=1
i=1
W ν + κ ∑ Bνi ≤ Λν + ∑ (a + gi )ν .
(21)
To prove this lemma, fix g, Λ and maximize k
k
J(B) := W ν + κ ∑ Bνi ,
W = Λ + ∑ (gi + Bi ),
i=1
(22)
i=1
e Λ. over Bi ≥ 0 for which the empty set minimizes Ψ The right side of (21) is fixed, so it suffices to prove the bound at a maximizer. We handle Bi = 0 by induction. At a positive maximizer, varying the Bi as in Section B.4 gives a tight set {r} consisting of one checkpoint. If x, y ≥ a are the empty-set costs to its left and right, then W = x + y + Br − a,
e Λ ({r}; g, B) = χxy = W. Ψ Br
Thus W Br = χxy, which explains the scalar relations in the hypothesis. The scalar inequality and induction on the two sides prove the lemma. Returning to the variables in (15), choose ν ν d ε = . (23) κ := 1−d χ This choice gives κBνi = (dbi )ν and yields the following growth bound. Lemma 3.8 (Uniform cost growth). Let ν ∈ [1/2, 1). If the scalar hypothesis (20) holds with (23), then, for every n ≥ 0 and λ ≥ a, Un (λ )ν ≤ aν n + λ ν . (24) 11
We prove the bound by induction on n, simultaneously for all λ ≥ a. At a maximizing schedule with a nonempty tight set, let mi count the updates in h(i) . Then k ≥ 1 gives mi < n and ∑k+1 i=1 mi = n − k. Using (19), the induction hypothesis gives (a + si + dbi )ν ≤ aν mi + (a + dbi )ν ν
ν
ν
(λ + sk+1 ) ≤ a mk+1 + λ .
(1 ≤ i ≤ k),
(25)
Now (a + dbi )ν ≤ aν + d ν bνi . The terms d ν bνi cancel those on the left side of (21) because κ(1 − d)ν = d ν . The remaining step counts sum to n, giving (24). The full proof is in Section B.5. Under the scalar hypothesis, for n ≥ 1 set p = 1/ν and choose the free terminal parameter λ = an p . Then Lemma 3.8 gives Vλ (h) ≤ Un (λ ) ≤ 2 p an p . Since a ≥ 2, we have λ − 1 ≥ an p /2, so Lemma 3.3 yields Rn (h) ≥
1 22p+1 a
for every h ∈ [0, ∞)n .
n−p
(26)
The numerator λ − 1 supplies a factor of order n p , giving the exponent p. It remains to verify the scalar hypothesis for p close to psil and control the constant a. Verifying the scalar condition. In the limiting case χ = 1, ε = 0, the following silver inequality implies (20) at p = psil . The √ change of variables that gives this implication is in Section B.6. Let ρ = 1 + 2, so that psil = log2 ρ. The identity ρ 2 = 2ρ + 1 makes the following inequality tight at the balanced split z = 1/2. Lemma 3.9 (Silver inequality). For every z ∈ [0, 1], z psil + (1 − z) psil + [z(1 − z)] psil ≤ 1.
(27)
Equality holds at z = 0, 1/2, 1. The transfer construction requires ε > 0. We handle this term by taking a slightly larger exponent. Write t+ = max{t, 0}. Lemma 3.10 (Sufficient scalar condition). Let p ∈ [psil , 3/2], ν = 1/p, 0 < χ ≤ 2, and 0 < ε < 1/2. Suppose that τ := ε 1/p ≤ 1/10 and p − psil ≥ (χ − 1)+ + 6ε 1/p . (28)
Then the scalar hypothesis (20) holds for κ = (ε/χ)1/p .
The proofs of these two lemmas are in Section B.6. To finish, fix 0 < η ≤ 1/10 and choose η p η p := psil + η, γ := , ε := , 4 16 p c := 1 + 2γ + ε 2 , χ := c − ε.
(29)
These parameters satisfy the sufficient scalar condition. The bounds on the construction constants in Section B.7 give log a = O η −1 log(1/η) , 0 < η ≤ 1/10, (30)
with an absolute implied constant. Combining this estimate with (26) yields Rn (h) ≥ n−psil exp −η log n − O η −1 log(1/η) .
12
(31)
The implied constant is absolute and the estimate is uniform over h. For sufficiently large n, take s log log n 1 η := ≤ . log n 10
(32)
√ Both terms in the exponent are then O( log n log log n). Taking the infimum over schedules proves, for an absolute constant C > 0, rn∗ ≥ n−psil exp
q n p o − psil +C logloglogn n −C log n log log n = n .
(33)
This is Theorem 1.1. The hard function may depend on n, as allowed by the separate supremum defining Rn (h) at each horizon.
4
(Almost) Tight Anytime Lower Bound
We now use the same hard functions to prove Theorem 1.2. The schedule is a single infinite sequence H = (ht )t≥1 of nonnegative stepsizes, so its prefixes cannot be chosen independently. Following the recordtime argument of Jung et al. [2026, Section 4], we compare the total stepsize with the largest step seen so far. The additional ε term in our checkpoint cost requires a different estimate for the number of large steps. Fix p ∈ (psil , psil + 1/10], set ν := 1/p, and take the parameters a, c, ε, B0 used to obtain (26). As before, let d := ε/c. For each prefix Hn = (h1 , . . . , hn ), write n
Sn := ∑ ht , t=1
Mn := max ht , 1≤t≤n
rn := Rn (Hn ).
We call n a record time if hn = Mn . The following estimate is the main step. Lemma 4.1. For every p ∈ (psil , psil + 1/10], there are constants C p < ∞ and r0,p > 0 such that every record time n with Mn ≥ B0 and rn ≤ r0,p satisfies Sn ≤ C p nMn1−ν .
(34)
The proof is given in Section C.1. Its starting point is to append the final step Mn to an optimal checkpoint set for the preceding steps. The resulting lower bound forces the checkpoint cost of that prefix to be large. On the other hand, if too many steps exceed a threshold u, selecting all of them makes the cost small. Comparing these two estimates bounds the number of steps above u by C p nu−ν . Integrating over u ∈ (0, Mn ) gives (34). Combining Lemma 4.1 with Lemma 2.2, applied to an empty checkpoint set and to a set consisting of the final step, gives the exponent 2p/(1+ p) at infinitely many horizons. Tracking the parameter dependence as p ↓ psil proves Theorem 1.2. The complete argument is in Section C.2.
5
Concluding Remarks
In this paper, we proved an almost tight lower bound for GD with predetermined nonnegative stepsizes. Our result closes the gap between the lower and upper bounds for both non-anytime and anytime cases, up to subpolynomial terms. Two questions remain open.
13
(1) Can the gaps be closed for schedules that may include negative stepsizes? To the best of our knowledge, the best known lower bounds in this setting are Ω(n−1.6342 ) in the non-anytime case and Ω(n−1.2408 ) in the anytime case, as established in our earlier paper [Ye and Liu, 2026]. Extending the lower bounds proved in this paper to this general setting remains open. p (2) Can the log log n/ log n losses in the exponents of (2) and (3) be reduced?
AI Disclosure We √ carefully read the paper by Jung et√al. [2026] and traced the difference between their exponent log2 (1 + 3) and the silver exponent log2 (1 + 2) to the factor 2 in their local transfer estimate. Their local Huber component has a fixed gradient direction. It changes both adjacent coordinates, so both changes reduce the margin that keeps the component active. We wondered whether we could reduce this loss by bending the local trajectory, gradually turning the descent direction toward coordinate i + 1 so that the selected step raises it farther above its activation level. We shared this intuition with ChatGPT-6 Astra. Through several rounds of substantive interaction and detailed calculations by ChatGPT-6 Astra Ultra, we designed a smooth convex hard function whose local gradient rotates along a circular arc and whose coefficient of si approaches 1. Combining this construction with a refinement of the recursive analysis in Jung et al. [2026, Section 3] gave the present result.
References 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. 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. Benjamin Grimmer. Provably faster gradient descent via long steps. SIAM Journal on Optimization, 34(3): 2588–2608, 2024. Benjamin Grimmer, Kevin Shu, and Alex L. Wang. Composing optimized stepsize schedules for gradient descent. Mathematics of Operations Research, 2025a. URL https://pubsonline.informs. org/doi/10.1287/moor.2024.0764. Articles in Advance. 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, 2025b. Minchan Jung, Hanseul Cho, and Chulhee Yun. Stronger lower bounds for (non-)anytime acceleration of gradient descent. arXiv preprint arXiv:2609.04032, 2026. E. S. Levitin and B. T. Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6(5):1–50, 1966. Jianhao Ma and Yuxin Chen. A lower bound for stepsize-based acceleration of gradient descent. arXiv preprint arXiv:2608.10418, 2026. 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. ISBN 0471103454. Translated by E. R. Dawson. 14
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Kluwer Academic Publishers, 2004. 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. Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964. Chung-En Tsai. An improved lower bound for non-anytime gradient descent. Blog post, 2026. URL https://chungentsai.github.io/gd-lower-bounds.html. Chung-En Tsai, Ilyas Fatkhullin, Liang Zhang, and Niao He. Lower bounds for anytime acceleration of gradient descent. arXiv preprint arXiv:2607.02053, 2026. Bofan Wang, Shiqian Ma, Junfeng Yang, and Danqing Zhou. Relaxed proximal point algorithm: Tight complexity bounds and acceleration without momentum. INFORMS Journal on Optimization, 8(2):141– 162, 2026. Yuhan Ye and Kaizhao Liu. Improved gradient descent lower bounds beyond Nesterov. arXiv preprint arXiv:2609.02855, 2026. Zihan Zhang, Jason D. Lee, Simon S. 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.
15
A
Proofs for the Hard-Function Construction
p Fix ε, γ > 0 and let c = 1 + 2γ + ε 2 . For the local construction, set q q R := ε 2 + (1 + γ)2 , p(q) := R2 − (q + γ)2 , v(q) := (p(q), −q),
0 ≤ q ≤ 1.
(35)
The vectors v(q) lie on the circle centered at (0, γ) and will be realized as gradients of a Moreau envelope.
A.1
Proof of Lemma 3.1
Proof. Let K := conv {0} ∪ {v(q) : 0 ≤ q ≤ 1} .
The arc lies on the circle of radius R centered at (0, γ), and v(0) = (c, 0),
1 q ≤ . p(q) ε
ε ≤ p(q) ≤ c,
v(1) = (ε, −1),
(36)
For a convex function g, write env1 g(r) = infz {g(z) + ∥r − z∥2 /2}. If σK (z) = maxw∈K ⟨w, z⟩, then ∇ env1 σK (r) = ΠK (r).
(37)
Indeed, the projection condition ⟨r − v, w − v⟩ ≤ 0 for every w ∈ K is equivalent to v ∈ ∂ σK (r − v), which is the optimality condition for the envelope minimizer r − v. Projection is nonexpansive, so this envelope is convex and 1-smooth. Start with rm = vm = (ε, −1). For j = m, m−1, . . . , 1, write r j = (u, −y), set h = α j , and let ∆ = y+γ −hγ. If ∆ ≤ uγ/c, choose v j−1 = (c, 0). Otherwise, choose D :=
p u2 + ∆ 2 ,
p :=
Ru , D
q :=
R∆ − γ, D
v j−1 := (p, −q).
(38)
y/u ≤ 1/ε
whenever r j = (u, −y).
(39)
In both cases define r j−1 = r j + α j v j−1 . We claim that v j = ΠK (r j ) (0 ≤ j ≤ m),
u ≥ ε,
y ≥ 1,
The claim holds at j = m. Assume the coordinate inequalities hold at r j . In the nonhorizontal case, γ ∆ y+γ 1+γ < ≤ ≤ . c u u ε
√ Since Rs/ 1 + s2 − γ is increasing in s, these inequalities give 0 < q ≤ 1. Thus (38) is a direction on the prescribed arc. In either case p ≥ ε and q ≥ 0, so the new coordinates preserve u ≥ ε and y ≥ 1. Moreover, y + hq u y hp q 1 = + ≤ , u + hp u + hp u u + hp p ε
which proves the coordinate inequalities for the induction step. For a nonhorizontal step, direct substitution gives D r j−1 − v j−1 = + h − 1 v j−1 − (0, γ) . R
(40)
The coefficient is nonnegative for h ≥ 1. If 0 ≤ h ≤ 1, the reverse triangle inequality and u ≥ ε, y ≥ 1 give q D γ D ≥ u2 + (y + γ)2 − hγ ≥ R − hγ, +h−1 ≥ h 1− ≥ 0. R R 16
The vector v j−1 − (0, γ) is an outward normal to the circle. The closed disk bounded by this circle contains the origin and hence all of K, so (40) proves the projection condition against every point of K. For a horizontal step, set µ = u/c+h−1. The condition for choosing a horizontal direction is 0 ≤ y ≤ γ µ, and r j−1 − (c, 0) = (cµ, −y) = µ(c, −γ) + (0, γ µ − y). (41) Both (c, −γ) and (0, 1) support K at (c, 0), so this vector also satisfies the projection condition. Once a horizontal direction is chosen, adding further nonnegative multiples of (c, 0) preserves this normal-cone condition. All earlier directions can therefore remain horizontal. This completes the proof of (39). In forward order, the points r0 , . . . , rm consequently form a gradient descent trajectory with the given local steps α j .
Bounding the total stepsize of the nonhorizontal steps. During a nonhorizontal backward step, set σ = (y + γ)/u. Write σold and σnew for its values before and after the step, and similarly write uold = u. The recursion gives hγ unew R σold − σnew σnew = σold − , . (42) = 1+ p 2 u uold γ 1 + σnew √ For A(σ ) = σ + 1 + σ 2 , convexity gives A(σold ) σold − σnew . ≥ 1+ p 2 A(σnew ) 1 + σnew Since R/γ > 1, Bernoulli’s inequality and (42) imply unew A(σold ) R/γ ≤ . uold A(σnew )
(43)
These ratios telescope over the nonhorizontal part of the backward trajectory. Initially u = ε and σ = (1 + γ)/ε. After every nonhorizontal step, σ > γ/c. If Hturn denotes their total stepsize, then uend ≥ ε(1 + Hturn ) by (36). It follows that c(1 + γ + R) R/γ Hturn ≤ H := − 1. (44) ε(γ + R) This conclusion also holds if the nonhorizontal part is empty. Write v j = (p j , −q j ) and define m
P := ∑ α j p j−1 , j=1
m
Q := ∑ α j q j−1 , j=1
C0 := ε + ε −1 + H/ε.
(45)
Horizontal steps contribute nothing to Q, whereas a nonhorizontal step contributes at most its stepsize. Hence 1+Q P ≤ cS, 0 ≤ Q ≤ H, r0 = (ε + P, −1 − Q), ε +P+ ≤ cS +C0 . (46) ε
17
A.2
Proof of Lemma 3.2
Proof. Retain its points r j , vectors v j , and displacements P, Q from (45). Use the constant C0 from (45). For the given b ≥ 1 + ε −2 and constant A ≥ C0 , set ρ :=
1 , cS + εb + A
z◦ := (1, 0) − ρr0 .
(47)
Let V = {v0 , . . . , vm , (c, 0)} and define φ (z) := max 0, ρ⟨v, z − z◦ ⟩ : v ∈ V ,
f := env1 φ .
(48)
The finite convex hull KV = conv({0} ∪ V ) contains every v j and is contained in K. Thus each v j remains the projection of r j onto the smaller set. Applying (37) to the translated support function of ρKV gives ∇ f (z◦ + ρr j ) = ρv j
(0 ≤ j ≤ m).
(49)
For every v = (p, −q) ∈ V , (46) gives ⟨v, −z◦ ⟩ = −p + ρ p(ε + P) + q(1 + Q) ≤ −p + ρ p(cS +C0 ) ≤ 0. Since p ≥ 0 and q ≥ 0, every affine piece in (48) is nonpositive on {z1 ≤ 0, z2 ≥ 0}. On this region, φ = 0, and its nonnegative envelope is also zero. Therefore f (z1 , z2 ) = 0
(z1 ≤ 0, z2 ≥ 0).
(50)
the position is (1 − ρP, ρQ) and the gradient is ρ(ε, −1). (U,Y + ρb),
U := 1 − ρ(P + εb) ≥ 0,
Y := ρQ.
(51)
The inequality for U follows from P ≤ cS. Moreover, ⟨v, (U,Y ) − z◦ ⟩ = ρ (1 − b)ε p + q ≤ 0, because q/p ≤ 1/ε and b ≥ 1 + ε −2 . Increasing the second coordinate decreases this inner product. As above, the envelope vanishes wherever all its affine pieces are nonpositive, so f (U, z2 ) = 0
(z2 ≥ Y ),
G(S, b) := ρb =
b . cS + εb + A
(52)
Together with (51), this shows that the first coordinate remains at least U , while the second lies in [0,Y ] .
A.3
Proof of Lemma 2.2
Proof. Choose the constants in Lemma 2.2 as B0 := 2(1 + ε −2 ),
a ≥ max{2, 2C0 /c, 2B0 }.
(53)
Suppose first that k ≥ 1. All local hypotheses hold by (53). Write fi ,Ui ,Yi for the resulting function and coordinates in Lemma 3.2. Its transfer ratio is Gi =
bi . c(a + si ) + εbi 18
(54)
Use in (8) and the two-coordinate components Φi in (9). Each Φi is 1-smooth on its pair of coordinates. For δ := Dk+1 /(1 + sk+1 ), define the one-sided Huber function and the full objective by F(x) :=
1 k 1 Φi (x) + Hδ (x(k+1) − ℓk+1 ). ∑ 2 i=1 2
(55)
The objective is convex and nonnegative. All ℓi are nonnegative, so (50) gives Φi (0) = 0, and the terminal term also vanishes at zero. Thus F(0) = min F = 0. To check smoothness, let d = y − x. Summing the component smoothness inequalities gives " # 1 k F(y) ≤ F(x) + ⟨∇F(x), d⟩ + ∑ (d (i) )2 + (d (i+1) )2 + (d (k+1) )2 4 i=1 1 ≤ F(x) + ⟨∇F(x), d⟩ + ∥d∥2 . 2 Each coordinate appears at most twice in the bracketed sum, proving that F is 1-smooth. We now verify the trajectory starting from x0 = e1 . At the start of block i, the claimed state is ℓ j + D jU j , j < i, ( j) xti−1 = ℓi + Di , j = i, 0, j > i.
(56)
This holds initially. Consider the path obtained from the trajectory of fi by the coordinate change in (9), leaving the other coordinates fixed. At every iterate , ti−1 ≤ t < ti , it satisfies x(i) ≥ ℓi + DiUi ≥ ℓi ,
0 ≤ x(i+1) ≤ DiYi = ℓi+1 ,
x( j) = 0
( j ≥ i + 2).
For every earlier two-coordinate component j < i, the first input to f j equals U j and the second is at least ℓ j+1 /D j = Y j . Hence the component remains zero by (52). For every later two-coordinate component, the first input is nonpositive and the second is zero, so the component remains zero by (50). The terminal Huber term is also zero before its activation. A differentiable nonnegative function has zero gradient wherever it vanishes. Thus the only nonzero gradient along this candidate path is that of Φi /2. By (49), each actual step ht therefore induces exactly the local step ht /2, so the candidate path is the GD trajectory. (i)
xti = ℓi + DiUi ,
(i+1)
xti
= Di (Yi + Gi ) = ℓi+1 + Di+1 ,
and all coordinates j ≥ i + 2 remain zero. This proves (56) for the next block. During that block, x(i+1) never drops below ℓi+1 , so the zero region of component i continues to apply. The induction verifies that the next component becomes active and every earlier component remains inactive. only the terminal Huber term is active. Write D = Dk+1 and s = sk+1 . The shifted last coordinate starts at D. δr δs D D− ≥ D− ≥ δ, δ= . 2 2 1+s Thus this trajectory stays in the affine region and above its activation level. Earlier components remain zero, and the final value is 1 δs δ2 D2 F(xn ) = δ D− − = . (57) 2 2 2 4(1 + s) Since Dk+1 = ∏ki=1 Gi and ∥x0 − 0∥ = 1, the normalization in (1) gives Rn (h) ≥ 2F(xn ). Dropping the factor 2 proves (7) for k ≥ 1. For k = 0, take F(x) = Hδ (x)/2 in one dimension with x0 = 1, δ = 1/(1 + ∑t ht ), and minimizer zero. The same calculation in (57) applies with D = 1 and proves the empty-product case as well. 19
B
Proofs for the Global Cost Analysis
We use the constants and conventions from Section 3.2, with 0 < ε < 1/2, d = ε/c ∈ (0, 1), χ = c − ε > 0, a ≥ max{2, 2B0 + 2}, and λ ≥ a.
B.1
Proof of Lemma 3.3
Proof of Lemma 3.3. The empty set has finite cost, so a minimizing set cannot select a zero step. Put y = a + r + db′ when the next has size b′ , and put y = λ + r otherwise. In both cases y ≥ a, and insertion multiplies the cost by c(a + ℓ + db)y I(ℓ, y; b) = . (58) b(ℓ + b + y) The logarithmic derivatives are (1 − d)b + y − a > 0, (a + ℓ + db)(ℓ + b + y) ℓ+b ∂y log I = > 0. y(ℓ + b + y) ∂ℓ log I =
If 0 < b ≤ a/2, then
I(ℓ, y; b) ≥ I(0, a; b) =
c(a + db)a 4 ≥ . b(a + b) 3
Deleting such a checkpoint strictly lowers the cost. Thus every selected step of a minimizing set satisfies bi > a/2 ≥ B0 , and Lemma 2.2 applies, including its empty-set case. For a minimizing set T , it gives Rn (h) ≥
(λ + sk+1 )2 . 4(1 + sk+1 )Vλ (h)2
Finally, (λ + s)2 − 4(λ − 1)(1 + s) = (s − λ + 2)2 ≥ 0 for every s ≥ 0, which proves the claim.
B.2
Proofs of Lemmas 3.4 and 3.5
Proof of Lemma 3.4. Consider inserting the same checkpoint into two sets, where the second contains the first. Additional selected checkpoints in (58). They also decrease the right-hand parameter y. Indeed, , and 1 − d > 0. If , replacing λ by a can only decrease this parameter. Thus both arguments of I are no larger for the second set. Add the elements of B \ A, one at a time, to each of A ∩ B and A. At every insertion the multiplier for the second set is no larger. Multiplying these inequalities gives (14). If A and B are disjoint and nonempty, the first insertion already compares the empty set with A. At least one boundary is strictly closer in the latter set, and the positivity of the schedule makes at least one argument of I strictly smaller. This proves strictness. If both A and B have the minimum cost V , then V 2 ≥ Ψλ (A ∩ B; h)Ψλ (A ∪ B; h) ≥ V 2 . Both sets on the right must therefore also be tight. Strictness rules out disjoint nonempty tight sets. Proof of Lemma 3.5. Appending zero steps does not change Vλ , since those steps cannot be selected and contribute nothing to . Hence Um (λ ) ≤ U j (λ ) whenever m ≤ j. We induct on n, starting with U0 (λ ) = λ .
20
First, Un (λ ) is finite. For an arbitrary schedule, write M = maxt ht . If M ≤ a, the empty-set cost is at most λ + na. If M > a, choose an index j with h j = M, select it, and optimize the suffix. This gives c(a + ∑t< j ht ) Un− j (λ ) ≤ (ε + cn)Un−1 (λ ) < ∞. Vλ (h) ≤ ε + M Here ∑t< j ht ≤ (n − 1)M and a/M < 1. Next, take a maximizing (n − 1)-step schedule supplied by induction and append a positive step t. The cost of every checkpoint set that omits the new step strictly increases, because increases by t. The cost of every checkpoint set that selects the new step tends to infinity as t ↓ 0. There are finitely many checkpoint sets, so for small enough t > 0 every cost exceeds Un−1 (λ ). Consequently Un (λ ) > Un−1 (λ ). To prove attainment, choose a maximizing sequence. If it has an unbounded subsequence, pass to a further subsequence converging coordinatewise in the compact extended interval [0, ∞] and having at least one infinite coordinate limit. Let j be the first such coordinate. All coordinates before j are bounded. Selecting j and optimizing the suffix as above yields lim supVλ (h) ≤ εUn− j (λ ) ≤ εUn−1 (λ ) < Un (λ ),
a contradiction. Thus the maximizing sequence is bounded, and a subsequence converges to h̄ ∈ [0, ∞)n . Suppose h̄ has a zero coordinate. Delete all of its zero coordinates to obtain a schedule h̄+ of length m < n, and fix a minimizing checkpoint set for h̄+ . Use the corresponding indices in the converging sequence, omitting every coordinate with zero limit. The selected steps have positive limits, and the tend to zero. The resulting costs converge to Vλ (h̄+ ). Therefore Un (λ ) ≤ Vλ (h̄+ ) ≤ Um (λ ) ≤ Un−1 (λ ), again a contradiction. The limit is positive. On the positive orthant, Vλ is the minimum of finitely many continuous functions, so it is continuous and h̄ attains Un (λ ). The same argument after deleting zero steps shows that every maximizing schedule is positive. It remains to establish tightness. If the empty set were not tight, all tight sets would be nonempty. Their intersection is nonempty and tight by Lemma 3.4. strictly increases every tight cost. Its factor is ε + c(a + s)/b, and it in those sets. By continuity, every other cost retains its positive slack under a sufficiently small perturbation. The minimum cost would then increase, contradicting maximality. Hence the empty set is tight. If it were the only tight set, increasing any step slightly would increase its cost while preserving the slack of all other sets, giving the same contradiction. A nonempty tight set therefore exists.
B.3
Proof of Lemma 3.6
Proof of Lemma 3.6. Skipping checkpoint i leaves its contribution unchanged, since gi + Bi = si + bi . If checkpoint i j is selected, and sej is , then L j (S) = sej + dbi j . The corresponding auxiliary factor is therefore χ(a + L j (S)) c(a + sej + dbi j ) c(a + sej ) = = + ε. Bi j bi j bi j The also agree. For S = ∅, the equality follows directly from gi + Bi = si + bi . e Λ . Tightness also identifies Both T and the empty set have cost Un (λ ). Hence the empty set minimizes Ψ (i) the smaller problems . Let h be the . For any checkpoint set S , with its indices understood in the original schedule, direct factorization gives Ψλ (T ∪ S; h) Ψa+dbi (S; h(i) ) = Ψλ (T ; h) a + si + dbi 21
(1 ≤ i ≤ k).
The left side is at least one and the empty set attains equality. The same argument replaces the right side by Ψλ (S; h(k+1) )/(λ + sk+1 ). This proves (19).
B.4
Proof of Lemma 3.7
Proof of Lemma 3.7. We induct on k. For k = 0, W = Λ and the assertion is equality. For k ≥ 1, hold g and e Λ . It suffices to prove Λ fixed and maximize J(B) from (22) over Bi ≥ 0 for which the empty set minimizes Ψ the desired bound at a maximizer, since its right side is fixed. Compactness and zero coordinates. singleton constraint at i, define
The feasible set is nonempty because B = 0 is feasible. For the
xi = a + ∑ gr + ∑ Br , r≤i
yi = Λ + ∑(gr + Br ).
r<i
r>i
Its constraint is W Bi ≤ χxi yi . Since W ≥ yi > 0, we have Bi ≤ χxi . The latter bound depends only on earlier variables and , so applying it successively bounds every Bi . Multiplying each subset constraint by gives a continuous polynomial inequality. If a selected size is zero, the left side becomes zero and the right side is positive, agreeing with the infinite-cost convention. The feasible set is therefore closed and bounded, and the continuous function J attains a maximum. If a maximizing vector has Bi = 0 with i < k, delete that checkpoint and replace by gi + gi+1 . This preserves all costs of sets that omit i, and hence preserves empty-set optimality. The induction hypothesis, followed by (a + gi + gi+1 )ν ≤ (a + gi )ν + (a + gi+1 )ν ,
gives the desired bound. If Bk = 0, delete it and replace Λ by Λ + gk . Then use (Λ + gk )ν ≤ Λν + (a + gk )ν . We may therefore assume that a maximizing vector has every Bi > 0. Finding a tight set with one checkpoint. At least one nonempty subset is tight. Otherwise, a sufficiently small increase of any Bi would preserve all constraints and strictly increase J. The auxiliary cost has the same log-submodularity and strictness property as in Lemma 3.4. Its insertion ratio is χ(a + ℓ)y , B(ℓ + B + y) which is strictly increasing in ℓ and y for y ≥ a and B > 0. The proof by successive insertions applies unchanged. Choose an inclusion-minimal nonempty tight set T0 . Every nonempty tight set intersects T0 , and that intersection is tight. Minimality therefore implies that T0 lies in every nonempty tight set. Suppose first that T0 contains two unequal sizes u < v, and put r = v/u > 1. Because both checkpoints are selected in every nonempty tight set, each such cost depends on them only through the reciprocal product 1/(uv). Define W ν−1 + κuν−1 v(W + u) , D∗ := ν−1 . A∗ := u(W + v) W + κvν−1 The gives W > u + v. Since ν ≥ 1/2 and κ ≥ 0, A∗ >
r(r + 2) √ ≥ r ≥ r1−ν ≥ D∗ ≥ 1. 2r + 1
(59)
For completeness, the first inequality follows because r(z + 1)/(z + r) increases in z = W /u > 1 + r. The √ second follows, on writing q = r, from q3 − 2q2 + 2q − 1 = (q − 1)(q2 − q + 1) ≥ 0. The bound on D∗ 22
follows by adding the same positive number W ν−1 to the numerator and denominator of a ratio at most uν−1 /vν−1 = r1−ν . Choose θ ∈ (D∗ , A∗ ) and perturb u 7→ u − t, v 7→ v + θt. Every nonempty tight cost starts at W , and the derivative of its slack over the empty-set cost is 1 θ − − (θ − 1) > 0, W u v where the inequality is equivalent to θ < A∗ . Meanwhile the objective has derivative ν (θ − 1)W ν−1 + κ(θ vν−1 − uν−1 ) > 0, since θ > D∗ . Positivity of and the strictness of all other constraints persist for sufficiently small t > 0. This contradicts maximality. If T0 has at least two elements and all of its sizes are equal to b, perturb two of them to b − t and b + t + t 2 /(2b). Their product becomes b2 − t 2 /2 − t 3 /(2b), while W increases by t 2 /(2b). Thus every nonempty tight constraint gains slack W −b 2 t + O(t 3 ) > 0. 2b2 The change in J is νt 2 ν−1 W + κ(2ν − 1)bν−1 + O(t 3 ) > 0. 2b The leading coefficient is positive even for ν = 1/2 or κ = 0, because W ν−1 > 0. Again the remaining constraints retain their strict slack for small t. This is a contradiction. It follows that T0 = {r} for some index r. Splitting at that checkpoint.
Write
x := a + ∑ gi + ∑ Bi , i≤r
y := Λ + ∑(gi + Bi ).
i<r
i>r
Tightness of {r} gives W = x + y + Br − a and W Br = χxy, with x, y ≥ a. Define the left and right auxiliary costs by e L (SL ) := Ψ e a+g (SL ; g1:r−1 , B1:r−1 ), e R (SR ) := Ψ e Λ (SR ; gr+1:k , Br+1:k ), Ψ Ψ r reindexing the right problem from one. For every choice of subsets SL and SR on the corresponding sides, e Λ (SL ∪ {r} ∪ SR ; g, B) = χ Ψ e L (SL )Ψ e R (SR ). Ψ Br
(60)
e L (∅) = x and Ψ e R (∅) = y. Taking SR = ∅ in (60) and using optimality of Their empty-set values are Ψ e L (SL ) ≥ W = (χy/Br )x. Thus the empty set the empty set in the full auxiliary problem gives (χy/Br )Ψ minimizes the left problem. Taking SL = ∅ gives the same conclusion for the right problem. The induction hypothesis applies to both sides, including a side with no checkpoints, and yields xν + κ ∑ Bνi ≤ ∑(a + gi )ν , i<r
i≤r
yν + κ ∑ Bνi ≤ Λν + ∑(a + gi )ν . i>r
i>r
The scalar hypothesis gives W ν + κBνr ≤ xν + yν . Combining these three inequalities proves (21). 23
B.5
Proof of Lemma 3.8
Proof of Lemma 3.8. We induct on n, simultaneously for all λ ≥ a. The case n = 0 follows from U0 (λ ) = λ . For n ≥ 1, choose a maximizing schedule, put W = Un (λ ), and choose a nonempty tight set with k checkpoints. Apply the substitution (15) and Lemma 3.7 to obtain k
k
i=1
i=1
W ν + κ ∑ [(1 − d)bi ]ν ≤ (λ + sk+1 )ν + ∑ (a + si + dbi )ν .
(61)
Let mi be the number of updates in h(i) for 1 ≤ i ≤ k + 1. Since k ≥ 1, each mi < n, and ∑k+1 i=1 mi = n − k. The identities (19) and the induction hypothesis at parameters a + dbi ≥ a and λ ≥ a give (25). Using (a + dbi )ν ≤ aν + d ν bνi in (61) yields k
k
i=1
i=1
W ν + κ(1 − d)ν ∑ bνi ≤ aν n + λ ν + d ν ∑ bνi . The choice (23) gives κ(1 − d)ν = d ν . Cancelling the checkpoint terms proves (24). For n ≥ 1, let p = 1/ν and take λ = an p . Lemma 3.8 gives Vλ (h) ≤ Un (λ ) ≤ 2 p an p . Since a ≥ 2, we have an p − 1 ≥ an p /2, and Lemma 3.3 implies (26). It remains to verify the scalar hypothesis for p arbitrarily close to psil and to quantify the dependence of a on that choice.
B.6
Proofs of Lemmas 3.9 and 3.10
For x, y, B, w in the scalar hypothesis, set u = x/w, v = y/w, p = 1/ν, and τ = ε 1/p . Here 0 < u, v < 1, since x, y ≥ a and B > 0. The scalar relations imply u + v + χuv = 1 +
a ≥ 1. w
(62)
Since B/w = χuv and κ = (ε/χ)1/p , dividing (20) by wν gives the target u1/p + v1/p − τ(uv)1/p ≥ 1.
(63)
To see why the silver inequality appears, consider the ideal limiting scalar problem χ = 1, ε = 0. Writing X = u1/p and Y = v1/p , a violation would have Y < 1 − X. The expression X p +Y p + X pY p increases with Y , and its boundary value is X p + (1 − X) p + [X(1 − X)] p .
If this expression is at most 1, the target inequality (63) must hold. Otherwise, (62) would be violated. Lemma 3.9 gives this bound at the silver exponent. Proof of Lemma 3.9. Write α = psil − 1 ∈ (0, 1/3), and denote the left side of (27) by F(z). For 0 < z < 1/2, F ′ (z) = φ (z) := (1 − z)−α − z−α + 1 − 2z. psil [z(1 − z)]α Moreover,
The endpoint values satisfy
φ ′′ (z) = α(α + 1) (1 − z)−α−2 − z−α−2 < 0. φ (0+) = −∞,
φ ′ (0+) = +∞, 24
φ (1/2) = 0,
and
1 φ ′ (1/2) = α2α+2 − 2 < 27/3 − 2 < 0. 3 ′ Thus φ has exactly one zero in (0, 1/2), and φ first increases and then decreases. Since φ ′ (1/2) < 0, φ is positive immediately to the left of 1/2. It therefore has exactly one zero in (0, 1/2), with negative sign before that zero and positive sign after it. Consequently, √ F first decreases and then increases on [0, 1/2], and its maximum occurs at an endpoint. With ρ = 1 + 2, those endpoint values are F(0) = 1,
F(1/2) =
2 1 + = 1. ρ ρ2
Symmetry under z 7→ 1 − z proves the result. For p ∈ [psil , 3/2] and 0 < χ ≤ 2, set
G p,χ (z) := z p + (1 − z) p + χ[z(1 − z)] p .
Writing t+ = max{t, 0}, we have G p,χ (z) ≤ 1 − p − psil − (χ − 1)+ z(1 − z),
z ∈ [0, 1].
(64)
Proof of the slack estimate (64). For 0 < z < 1, the inequalities − log z ≥ 1 − z and − log(1 − z) ≥ z give −∂ p G p,1 (z) ≥ z p (1 − z) + (1 − z) p z = z(1 − z) z p−1 + (1 − z) p−1 ≥ z(1 − z).
The last inequality uses 0 < p − 1 ≤ 1/2. Integrating in p from psil , and applying Lemma 3.9, yields G p,1 (z) ≤ 1 − (p − psil )z(1 − z). Changing the coefficient from 1 to χ increases the expression by at most (χ −1)+ z(1−z), since [z(1−z)] p ≤ z(1 − z). This proves the estimate, and continuity gives the endpoint cases. Proof of Lemma 3.10. Let x, y ≥ a and B > 0 satisfy w = x + y + B − a,
wB = χxy.
Set u = x/w and v = y/w. Since a > 0, x, y ≥ a, and B > 0, we have 0 < u, v < 1. The two relations imply (62). Dividing wν + κBν ≤ xν + yν by wν , and using B/w = χuv, reduces the desired conclusion to (63). Suppose this inequality fails. Put X = u1/p and Y = v1/p . Then 0 < X,Y < 1 and Y<
1−X =: A. 1 − τX
Here 0 < A < 1. Since the derivative of t p on [0, 1] is at most p, the mean value theorem gives p A − (1 − X) p (1 + χX p ) ≤ p A − (1 − X) (1 + χ) pτ(1 + χ) ≤ X(1 − X) ≤ 6τX(1 − X). 1−τ
The final step uses p ≤ 3/2, χ ≤ 2, and τ ≤ 1/10. Consequently,
u + v + χuv < X p + A p + χX p A p ≤ G p,χ (X) + 6τX(1 − X) ≤ 1,
where the last inequality follows from (64) and (28). This contradicts (62). 25
B.7
Proof of Theorem 1.1
Fix 0 < η ≤ 1/10 and use the parameter choice (29). These choices give p ∈ [psil , 3/2], 0 < ε < 1/2, and ε 1/p = η/16 ≤ 1/10. Also, ε 2 ≤ (η/16)2 ≤ η/6, so c2 = 1 +
2η η 2 η + ε2 ≤ 1 + ≤ 1+ . 2 3 3
Consequently, 0 < χ ≤ c ≤ 1 + η/3 < 2, and (χ − 1)+ + 6ε 1/p ≤
η 3η 17η + = < η = p − psil . 3 8 24
Lemma 3.10 therefore verifies (20) with the coefficient κ = (ε/(c − ε))1/p prescribed in (23). The weighted recursion, Lemma 3.8, and (26) now give the lower bound with exponent psil + η. For an excess exponent larger than 1/10, the result with η = 1/10 already implies the corresponding weaker polynomial bound. To quantify the dependence on η, take the constants from the transfer construction to be R :=
q ε 2 + (1 + γ)2 ,
H :=
C0 := ε + ε −1 + H/ε,
c(1 + γ + R) R/γ − 1, ε(γ + R)
B0 := 2(1 + ε −2 ),
(65)
a := max{2, 2C0 /c, 2B0 + 2}. In particular, a ≥ 2B0 + 2, as required. Under (29), the quantities c and R are bounded above and bounded away from zero by absolute constants, while log(1/ε) = p log(16/η) = O(log(1/η)),
R = O(1/η). γ
The logarithm of the base defining 1 + H is O(log(1/η)). Hence R c(1 + γ + R) log(1 + H) = log = O η −1 log(1/η) . γ ε(γ + R) Since C0 = ε + (1 + H)/ε and log B0 = O(log(1/η)), the choice of a gives (30) with an absolute implied constant. Proof of Theorem 1.1. For any 0 < η ≤ 1/10, the preceding parameter choice and (26) yield, for every n ≥ 1 and every nonnegative schedule h ∈ [0, ∞)n , Rn (h) ≥
1 n−p . 22p+1 a
Using p = psil + η and (30), we obtain (31). The implied constant is absolute and the estimate is uniform √ over h. For sufficiently large n, choose η as in (32). Then η log n = log n log log n, and η −1 log(1/η) = √ O( log n log log n). Taking the infimum over schedules in (31) proves (33) for an absolute constant C > 0. The hard function and the parameters may depend on n, since Rn (h) takes a separate supremum over hard functions at each finite horizon.
26
C
Proofs for the Anytime Lower Bound
C.1
Proof of Lemma 4.1
We prove Lemma 4.1. Fix p ∈ (psil , psil + 1/10] and the corresponding parameters, and recall that ν = 1/p and d = ε/c ∈ (0, 1). We may take 1 1 . r0,p := min , 8 16c2 At a record time satisfying the lemma’s assumptions, write M := Mn = hn ,
R := rn ,
ξ := Hn−1 ,
Λ := a + dM,
V := VΛ (ξ ).
A lower bound on the cost of the prefix. The deletion argument in the proof of Lemma 3.3 shows that deleting any selected step of size at most a/2 decreases the checkpoint cost. Thus a set attaining V selects only steps larger than a/2 ≥ B0 . Append the final step M to this set. Let s be the sum of the stepsizes after the last selected step in the prefix, or of all stepsizes in the prefix if no step is selected. The corresponding cost factor becomes c(Λ + s)/M, since c(a + s) + εM = c(Λ + s). There are no updates after the selected final step, so Lemma 2.2 gives R≥ Counting steps above a threshold.
M2 , 4c2V 2
V≥
M √ ≥ 2M ≥ 2dM. 2c R
(66)
For 0 < u ≤ M, let Nξ (u) := {t < n : ht > u} = k.
List these k steps in the order they occur as b1 , . . . , bk , and let ξ (0) , . . . , ξ (k) be the blocks between them, including the initial and final blocks. Write m j for the length of ξ ( j) . Then ∑kj=0 (m j + 1) = n. Select b1 , . . . , bk and an optimal checkpoint set inside each block. The cost of this set gives k
c Va+dbi (ξ (i−1) ). b i=1 i
Va+dM (ξ ) ≤ Va+dM (ξ (k) ) ∏
(67)
Indeed, multiplying the preceding block’s final factor a + s + dbi by c/bi gives ε + c(a + s)/bi , the factor for bi . This is an identity between checkpoint costs, so the selected bi need not exceed the threshold B0 required by Lemma 2.2. Applying (24) to each block and using (a + db)ν ≤ aν + d ν bν gives c aν (mi−1 + 1) 1/ν (i−1) Va+dbi (ξ ) ≤ ε 1+ , (68) bi d ν bνi aν (mk + 1) 1/ν Va+dM (ξ (k) ) ≤ dM 1 + . (69) d ν Mν Since bi > u, M ≥ u, and 1 + z ≤ ez , substituting these estimates into (67) yields ν V a k −ν ≤ ε exp nu . dM νd ν Together with (66), this implies Nξ (u) ≤
aν nu−ν . νd ν log(1/ε) 27
(70)
Integrating this bound over the threshold gives n−1
aν
Z M
∑ ht = 0 Nξ (u) du ≤ ν(1 − ν)d ν log(1/ε) nM1−ν .
(71)
t=1
Including the last step.
By (66) and (24), √ −ν ν (2c R) M ≤ V ν ≤ aν (n − 1) + (a + dM)ν ≤ aν n + d ν M ν . √ Our choice of r0,p ensures (2c R)−ν ≥ 2ν , and hence aν n. 2ν − d ν
Mν ≤
Adding M ≤ aν nM 1−ν /(2ν − d ν ) to (71) proves the lemma with 1 1 ν + Cp = a . ν(1 − ν)d ν log(1/ε) 2ν − d ν
(72)
□ The explicit choices of r0,p and Cp also justify the dependence on p used in (76). For δ = p− psil ↓ 0, both ν and 1 − ν stay bounded away from zero, while c stays bounded and log(1/d) = O(log(1/δ )). Thus (30) gives logCp = O(δ −1 log(1/δ )). The additional constants in the derivation from (74) to (75) are bounded by fixed powers of a, c, B0 and Cp , which gives the stated bound on log(1/c p ).
C.2
Proof of Theorem 1.2
Selecting no checkpoints in Lemma 2.2 gives rn ≥
1 . 4(1 + Sn )
(73)
If H is bounded, then Sn = O(n), and this is already stronger than the desired bound. We may therefore assume that H is unbounded and consider its infinitely many strict record times. At a record time with Mn ≥ B0 , selecting only the final step in Lemma 2.2 gives 2 1 Mn rn ≥ . (74) 4 c(a + Sn−1 ) + εMn For rn ≤ r0,p , after decreasing r0,p if necessary, we can move the term containing εMn to the left and use √ a + Sn−1 ≤ (1 + a/B0 )Sn to obtain Mn ≤ Cp Sn rn . Also, (73) gives Sn ≥ 1/(8rn ) when rn ≤ 1/8. Combining these estimates with Lemma 4.1 yields Snν ≤ C p nrn
(1−ν)/2
(1+ν)/2
1 ≤ Cp nrn
,
.
Consequently, at every such record time, rn ≥ c p n−β (p) ,
β (p) :=
2p 2 = . 1+ p 1+ν
(75)
It remains to let p approach psil . Write δ := p − psil . The parameter bound (30) and the constants in the proof of Lemma 4.1 imply log(1/c p ) + log(1/r0,p ) = O δ −1 log(1/δ ) , (76) log B0 = O(log(1/δ )) , β (p) = pany + O(δ ). 28
At each sufficiently large strict record time, choose s δ=
log log n . log n
The hard function may depend on n, since Rn (Hn ) takes a separate supremum at each horizon. If Mn < B0 , then Sn ≤ nB0 , and (73) gives rn ≥ n−1−o(1) . If rn > r0,p , then (76) gives rn ≥ n−o(1) . Both cases are stronger than the claimed bound. Otherwise, (75) and (76) give √ − p +C′ log log n/ log n rn ≥ n−pany exp −C δ log n + δ −1 log(1/δ ) ≥ n any . There are infinitely many strict record times, which proves Theorem 1.2.
29