REVIEW 3 major objections 4 minor 4 cited by
Anytime Acceleration of Gradient Descent
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper constructs a fixed stepsize schedule under which gradient descent reaches error O(T^{-1.119}) at every stopping time T, the first provable anytime acceleration beyond the classic 1/T rate.
desk verdict Resolves the COLT anytime-GD open problem with a clever schedule; the proof has a real, likely patchable gap in Lemma 10's length-one case. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the primitive stepsize schedule and its concatenation rule. A schedule $s=\alpha_{1:k-1}$ is primitive if it satisfies a descent-potential inequality that yields $f_k-f^*\le O(1/A_k)$ at its final point, where $A_k$ is the sum of its step sizes. Two primitive schedules $s$ and $r$ can be joined by inserting the step $\varphi(1^\top s,1^\top r)$, where $\varphi$ is the unique positive value keeping the combined schedule primitive. The paper's schedule repeats the $j$-th order silver schedule $s_j$ (total step sum $\rho^j-1$) for $k_j\approx 2^{c j}$ repetitions with $c=\log_2\rho$, producing many join steps while keeping the total step sum large. The new ingredient is Lemma 10: inside a silver block, if the incoming step size $\alpha$ is at least $(\sqrt2-1)A_k+\sqrt2$, every intermediate gap $f_\ell-f_0$ is bounded by $432\alpha^2\|g_0\|^2$, which prevents intermediate iterates from overshooting.
What would settle it
Check whether Lemma 10's subcase for a block of length one can be proved without the displayed division by $\rho^0-1=0$; if no separate argument exists, the lemma's proof is incomplete. Empirically, run the constructed schedule on a family of smooth convex quadratics and record $f(x_T)-f^*$ at all $T$; if $T^{1.119}(f(x_T)-f^*)/\|x_1-x^*\|^2$ is unbounded at any time $T$, the $O(T^{-1.119})$ anytime claim is false.
Extended reading notes
Core claim
The central claim is Theorem 1: there exists a stepsize schedule $\{\alpha_t\}$, fixed in advance and independent of the stopping time, such that gradient descent on a 1-smooth convex function obeys $f(x_T)-f^* \le O(\|x_1-x^*\|^2 / T^\theta)$ for every $T\ge 1$, where $\theta = 2\log_2\rho/(1+\log_2\rho) \approx 1.119$ and $\rho=1+\sqrt2$ is the silver ratio. Previously, acceleration by step-size design was known only at exponentially spaced checkpoints or when the stopping time was fixed in advance; the paper's contribution is to close the gap at every integer time and to extend the same schedule to strongly convex objectives with an anytime rate $\exp(-\Omega(T/\kappa^{0.893}))$.
Load-bearing premise
The anytime guarantee rests on Lemma 10, the claim that inside a silver block with a large-enough incoming step, every intermediate function gap stays below $432\alpha^2\|g_0\|^2$; if that intermediate control fails, the schedule's fast rate at join steps does not transfer to arbitrary stopping times.
Editorial extensions
If this is right
- A fixed step-size schedule gives worst-case anytime error $O(T^{-1.119})$ for smooth convex gradient descent, beating the $O(1/T)$ barrier at every stopping time.
- The guarantee holds without knowing $T$ in advance, so the schedule is usable when the iteration count is chosen online or by a random stopping rule.
- For smooth strongly convex objectives, the concatenation idea gives an anytime rate $\exp(-\Omega(T/\kappa^{0.893}))$, improving the exponent's dependence on the condition number relative to the standard $\exp(-\Omega(T/\kappa))$.
- The result affirmatively answers a 2024 open problem asking whether stepsize-based acceleration can achieve an anytime rate of $o(1/T)$.
Reading between the lines
- Editorial extension: the construction leaves the repetition exponent $c$ free and only fixes $c=\log_2\rho$ at the end; if a sharper version of Lemma 10 existed, a different $c$ could push the anytime exponent closer to $\log_2\rho \approx 1.272$.
- Editorial extension: because the objective value is non-monotone between join steps, a practical stopping rule that trusts the last observed gap could be misled; a natural test is whether stopping at scheduled checkpoints recovers the anytime guarantee in practice.
- Editorial extension: the concatenation framework is not tied to the silver schedule, so the same proof strategy could be tried with other primitive blocks, for example blocks tailored to composite objectives or to linear convergence, potentially transferring the anytime property to proximal or coordinate-descent methods.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a predetermined infinite stepsize schedule for gradient descent on smooth convex functions and proves an anytime bound f(x_T)-f* = O(||x1-x*||^2 / T^theta) with theta = 2 log_2 rho / (1+log_2 rho) = 1.119..., valid for every stopping time T. The schedule is built by concatenating silver stepsize schedules, using the Zhang-Jiang primitive-schedule framework, with each silver order repeated an exponentially growing number of times. The main technical novelty is a lemma controlling the gradient norms at all intermediate iterations inside a silver block; this is what upgrades fast convergence at join steps into an anytime guarantee. The paper also gives a strong-convexity extension by periodically restarting this schedule, obtaining exp(-Omega(T/kappa^{0.893})).
Significance. If the proof is made fully rigorous, the result is significant: it affirmatively answers the COLT 2024 open problem of Kornowski and Shamir and is the first provable anytime acceleration of gradient descent beyond the O(1/T) baseline. The paper is largely self-contained; it reproduces the Zhang-Jiang concatenation lemmas in the appendices, and the construction has no fitted parameters, with the final exponent obtained by balancing two proven rates rather than by numerical fitting. The main risk is a technical one in the intermediate-gradient control, which is exactly where the proof currently has gaps.
major comments (3)
- [Section 3.3, Lemma 10 (displayed inequalities (29)-(31))] Case 2 of Lemma 10 is not proved for m_{j+1}=0. In that case the subblock has length one, bA_{m_{j+1}} = bA_0 = 0, and the displayed inequalities (29), (30), and (31) all divide by bA_{m_{j+1}} or by bA_{m_{j+1}}(bA_{m_{j+1}}+1), so Lemma 9 cannot be invoked. This is not a marginal subcase: the binary expansion of an arbitrary intermediate index ell can end with 2^0, so the current proof of Lemma 10 does not cover odd ell. The gap appears repairable by a direct one-step argument: for the single step alpha = sqrt(2), use (8f) together with ||g(x - sqrt(2) g)|| <= (1+sqrt(2))||g|| to show alpha^2_{tau_{j+1}} ||g_{tau_{j+1}}||^2 <= 12 alpha^2_{tau_j} ||g_{tau_j}||^2. This should be written out explicitly, since Lemma 10 is load-bearing for the anytime claim.
- [Section 3.4, around equations (37)-(39)] The formula t_{i+1} = t_i + 2^{o_{t_i}+1} is inconsistent with the stated construction. With t_i defined as the length of bs_i after i concatenations in (12), the next concatenation adds one join step plus a silver schedule of order o_{t_i}, so the increment is 2^{o_{t_i}}, not 2^{o_{t_i}+1}; for example, if k_1 is the first repetition count, then t_1=2 and t_2=t_1+2, while the displayed formula would give t_2=6. If instead t_i is intended to be the cumulative length after an entire silver-order group, then the later claim that the union of intervals equals [3,infty) fails because t_1 = 2k_1 is about 10. Either way, the indexing must be repaired. The proof likely goes through with the corrected exponent and adjusted constants, since Lemma 7 bounds 2^{o_{t_i}} as needed, but as written this part of the proof of Theorem 1 is not verifiable.
- [Section 4, equations (42)-(44)] The proof of Theorem 11 needs a lower bound tau^theta >= c kappa in order to conclude f_{tau+1} - f* <= ||x1-x*||^2 / (144 kappa), but the displayed argument only yields tau <= 144 C0 kappa^{1/theta}, i.e., tau^theta <= (144 C0)^theta kappa. The missing ingredient is the opposite control: either a lower bound on the hitting time tau, equivalently an upper bound A_t(bs) <= C t^theta on the aggregate stepsizes, or a direct bound showing that the first time A_{tau+1} reaches 4 C0 kappa indeed occurs when tau^theta = Theta(kappa). This upper bound on A_t is plausible from the block construction (each order-j block contributes aggregate rho^j - 1 and length about 2^{(c+1)j}), but it is not stated or proven in the manuscript. Please add this argument before the contraction step.
minor comments (4)
- [Section 3.3, equation (31)] The line for (31) contains a duplicated inequality sign ('<= <='); this should be cleaned up.
- [Section 3.3, equation (35)] The constant 432 is introduced abruptly. The summation in (36) shows the intended use, but the text should explicitly say that (35) is a coarse uniform bound obtained by combining the geometric decay in Case 1 with the large but finite constant in Case 2.
- [Section 3.4, paragraph after (39)] The claim that the union of intervals (t_i,t_{i+1}] equals [3,infty) requires treating the endpoints ell = t_i + 1, which are covered by the primitive bound (38a) rather than by Lemma 10; this should be stated explicitly to avoid an apparent off-by-one gap.
- [Section 3.3, Lemma 10] The notation A_k in the statement of Lemma 10 and bA_j in its proof should be aligned; the condition alpha >= (sqrt(2)-1)A_k + sqrt(2) uses A_k = 1^T s_i, and the proof would be easier to read if the same symbol were used throughout.
Circularity Check
No circularity: the anytime rate is derived from primitive-schedule concatenation lemmas with proofs included, not from the target rate as input.
full rationale
The paper's central derivation is self-contained and does not reduce to its inputs. Theorem 1's exponent is obtained by balancing two independently proven upper bounds rather than by inserting the desired rate into the construction: after bounding the gap at join steps by the primitive-schedule inequality and bounding intermediate gaps by Lemma 10, the proof sets the free parameter c to equal log2 rho so that the two exponents 2c/(c+1) and (c+log2 rho)/(c+1) coincide (Eqs. (39)-(40)). No parameter is fitted to the claimed O(T^{-1.119}) rate. The load-bearing concatenation lemmas 3 and 12 are attributed to Zhang and Jiang (2024), but the paper reproduces their proofs in Appendix B ('We present the proof for completeness'), so this self-citation is not relied upon as an unverified black box. Definition 2's primitive-schedule condition is a strong potential-function inequality, and Lemma 8, Lemma 9, and Lemma 10 are each proven from smooth convex inequalities and the algebraic definition of the silver schedule; none of these proofs assumes the final function-gap bound. The final claim is thus a genuine analytical consequence of the constructed schedule. The only substantive manuscript-level concern is a rigor gap in Lemma 10's m=0 subcase (Section 3.3, Eqs. (29)-(31)): the displayed derivation divides by bA_{m_{j+1}} = rho^{m_{j+1}}-1, which vanishes when m_{j+1}=0. That is a correctness/completeness issue, not a circularity issue, and it does not make the theorem's conclusion an input to the derivation; it is therefore not reflected in the circularity score.
Assumptions & free parameters
free parameters (1)
- repetition growth exponent c =
c = log2 rho approximately 1.2716
assumptions (3)
- domain assumption The objective f is 1-smooth and convex (or mu-strongly convex) over R^d with a minimizer x*; gradient descent uses x_{t+1} = x_t - alpha_t grad f(x_t).
- standard math Standard inequalities for smooth convex functions given in (8a)-(8f), cited from Beck (2017) and Zhang and Jiang (2024, Section 2.1).
- standard math Primitive stepsize schedule concatenation lemmas (Lemma 3 and Lemma 12) from Zhang and Jiang (2024), with proofs reproduced in Appendix B.
Cite this review
Pith. "Pith review of Anytime Acceleration of Gradient Descent." pith.science (2026). https://pith.science/paper/EAYW3NX4
@misc{pith2026241117668,
author = {Pith},
title = {Pith review of: Anytime Acceleration of Gradient Descent},
year = {2026},
howpublished = {\url{https://pith.science/paper/EAYW3NX4}},
note = {Machine review of arXiv:2411.17668}
}
abstract
This work investigates stepsize-based acceleration of gradient descent with {\em anytime} convergence guarantees. For smooth (non-strongly) convex optimization, we propose a stepsize schedule that allows gradient descent to achieve convergence guarantees of $O(T^{-1.119})$ for any stopping time $T$, where the stepsize schedule is predetermined without prior knowledge of the stopping time. This result provides an affirmative answer to a COLT open problem \citep{kornowski2024open} regarding whether stepsize-based acceleration can yield anytime convergence rates of $o(T^{-1})$. We further extend our theory to yield anytime convergence guarantees of $\exp(-\Omega(T/\kappa^{0.893}))$ for smooth and strongly convex optimization, with $\kappa$ being the condition number.
Figures
Forward citations
Cited by 4 Pith papers
-
Optimized methods for composite optimization: a reduction perspective
A reduction framework converts unconstrained optimized first-order methods into composite-setting methods with analogous rates, yielding new proximal OGM and proximal OGM-G guarantees.
-
Accelerating Proximal Gradient Descent via Silver Stepsizes
Proximal and projected gradient descent using the silver stepsize schedule achieve the silver convergence rate O(ε^{-log_ρ 2}) for composite convex optimization, matching the rate known only for unconstrained smooth g...
-
Adaptive control mechanisms in gradient descent algorithms
A feedback-feedforward adaptive stepsize law for gradient descent is shown via Lyapunov analysis to achieve O(1/k) last-iterate convergence for convex locally smooth objectives with robustness to inexact gradients.
-
Finite Horizon Optimization: Framework and Applications
A finite-horizon stepsize rule for the primal-dual method on LP, found via a 4x4 SDP, is claimed to accelerate convergence at the T-th iteration and to give about 3.9x speedup on Netlib instances.
Reference graph
Works this paper leans on
-
[1]
Altschuler, J. (2018). Greed, hedging, and acceleration in convex optimization . PhD thesis, Massachusetts Institute of Technology
work page 2018
-
[2]
Altschuler, J. M. and Parrilo, P. A. (2023a). Acceleration by stepsize hedging i: Multi-step descent and the silver stepsize schedule. arXiv preprint arXiv:2309.07879
arXiv 2023
-
[3]
Altschuler, J. M. and Parrilo, P. A. (2023b). Acceleration by stepsize hedging ii: Silver stepsize schedule for smooth convex optimization. arXiv preprint arXiv:2309.16530
work page Pith review arXiv 2023
-
[4]
Beck, A. (2017). First-order methods in optimization . SIAM
2017
-
[5]
Daccache, A., Glineur, F., and Hendrickx, J. (2019). Performance estimation of the gradient method with fixed arbitrary step sizes . PhD thesis, Master’s thesis, Universit \'e Catholique de Louvain
work page 2019
-
[6]
Das Gupta, S., Van Parys, B. P., and Ryu, E. K. (2024). Branch-and-bound performance estimation programming: A unified methodology for constructing optimal optimization methods. Mathematical Programming , 204(1):567--639
work page 2024
-
[7]
and Teboulle, M
Drori, Y. and Teboulle, M. (2014). Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming , 145(1):451--482
2014
-
[8]
Eloi, D. and Glineur, F. (2022). Worst-case functions for the gradient method with fixed variable step sizes . PhD thesis, Master’s thesis, Universit \'e Catholique de Louvain
work page 2022
Show all 18 references
-
[9]
Grimmer, B. (2024). Provably faster gradient descent via long steps. SIAM Journal on Optimization , 34(3):2588--2608
2024
-
[10]
Grimmer, B., Shu, K., and Wang, A. L. (2023). Accelerated gradient descent via long steps. arXiv preprint arXiv:2309.09961
2023 arXiv
-
[11]
Grimmer, B., Shu, K., and Wang, A. L. (2024a). Accelerated objective gap and gradient norm convergence for gradient descent via long steps. arXiv preprint arXiv:2403.14045
2024 arXiv
-
[12]
Grimmer, B., Shu, K., and Wang, A. L. (2024b). Composing optimized stepsize schedules for gradient descent. arXiv preprint arXiv:2410.16249
2024
-
[13]
and Shamir, O
Kornowski, G. and Shamir, O. (2024). Open problem: Anytime convergence rate of gradient descent. In Conference on Learning Theory , volume 247, pages 5335--5339
2024
-
[14]
Nesterov, Y. (2018). Lectures on convex optimization , volume 137. Springer
2018
-
[15]
Rotaru, T., Glineur, F., and Patrinos, P. (2024). Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions. arXiv preprint arXiv:2406.17506
2024
-
[16]
B., Hendrickx, J
Taylor, A. B., Hendrickx, J. M., and Glineur, F. (2017). Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming , 161:307--345
2017
-
[17]
and Vaisbourd, Y
Teboulle, M. and Vaisbourd, Y. (2023). An elementary approach to tight worst case complexity analysis of gradient based methods. Mathematical Programming , 201(1):63--96
2023
-
[18]
and Jiang, R
Zhang, Z. and Jiang, R. (2024). Accelerated gradient descent by concatenation of stepsize schedules. arXiv preprint arXiv:2410.12395
2024
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.