- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper investigates the fundamental limits of accelerating gradient descent (GD) through predetermined, nonnegative, time-varying step-size schedules for smooth and strongly convex optimization problems. While classical gradient descent achieves an iteration complexity of , recent developments involving the Silver step-size schedule have established improved upper bounds of . However, the optimality of this dependence on the condition number has remained unresolved. The authors also derive bounds for the function value gap and squared gradient norm. Overall, the paper addresses a fundamental theoretical question in first-order optimization and provides substantial progress toward characterizing the optimal complexity of gradient descent with predetermined step sizes.
Critical strengths
In this submissions, the authors provided intersting theoretical contribution. The main lower bound substantially narrows the gap between existing lower and upper complexity bounds. Identifying the optimal polynomial exponent is an important theoretical result that helps characterize the intrinsic limitations of predetermined step-size acceleration. That results nearly matched upper and lower bounds. The combination of the new lower bound and the anytime upper bound for periodic Silver schedules provides a particularly satisfying theoretical characterization. The remaining gap is only a factor of , substantially smaller than the previous polynomial gap.
The authors presented novel and technically sophisticated lower-bound construction in the submissions. The hierarchical phase decomposition and coupling of multiple coordinate-chain hard instances appear to be substantial technical innovations. In particular, the construction addresses the difficulty posed by long sequences of small step sizes, which cannot be handled directly by a single coordinate-transfer chain. The results apply to arbitrary predetermined nonnegative step-size schedules and general smooth, strongly convex objectives, rather than only quadratic objectives or a particular family of schedules. The paper also discusses analogous convergence criteria involving function values and gradient norms.
Critical weaknesses
One major disadvantage of this submission is that the extremely complicated lower-bound proof. The proof of Theorem 1.1 is technically intricate and depends on numerous auxiliary lemmas spread across several appendices. The combination of checkpoint optimization, geometric coordinate transfers, phase coupling, and fixed-point arguments makes it difficult to independently verify the result. Although the authors provide proof sketches and a dependency diagram, a more intuitive explanation of the essential construction would substantially improve accessibility. Also there are limited and inadequate discussions of the tightness of the logarithmic factor. The lower and upper bounds still differ by . While the authors acknowledge this open problem, the paper does not provide much discussion of whether the logarithmic correction reflects a fundamental limitation or an artifact of the hard-instance construction. A deeper investigation would help clarify the significance of the refined logarithmic exponent.
Moreover, there is unclear quantitative significance of the lower bound for moderate condition numbers. The proof relies on an asymptotic hard-instance construction for sufficiently large , while the remaining bounded range is handled through a classical quadratic lower bound. The resulting constants are not explicitly quantified. Consequently, it is unclear how informative the new lower bound is for moderate values of . Also, the predetermined step sizes have limited applications for general optimization framework. The results only apply to deterministic, nonadaptive step-size schedules. They do not directly characterize adaptive line-search procedures, stochastic step-size schedules, or gradient methods with momentum. This is a natural limitation of the problem formulation rather than a flaw, but a clearer discussion of the boundary between these algorithmic classes would improve the paper.
Last, there is lack of numerical illustrations. The paper is entirely theoretical and does not include numerical experiments illustrating the behavior of Silver step-size schedules or the proposed hard instances. Although experiments are not essential for a theoretical contribution, numerical examples could help demonstrate the practical implications of the results and clarify the difference between non-anytime and anytime guarantees. Although this is a pure theoretical work, it is still recommended that the authors added some empirical results from numerical experiments to check if they are consistent with the theoretical analysis.
Questions for authors
The authors discuss the concurrent result of Liu and Ye (2026), which also establishes a lower bound with the Silver exponent. Could the authors provide a more explicit comparison of the key technical differences between the two hard-instance constructions and explain which ideas are responsible for improving the logarithmic dependence?
2 comments
After reading rebuttals from the authors. I remain my original score.
We thank the reviewer for their detailed review and comments. The reviewer acknowledges the significance and novelty of our theoretical contribution and notes that we handle several convergence metrics in the appendices.
Let us address the reviewer’s concerns below.
W1. Extremely complicated proof & limited discussion on polylogarithmic factor.
W2. Unclear quantitative significance of the lower bound for moderate condition numbers.
W3. The results only apply to deterministic, nonadaptive step-size schedules.
W4. Lack of numerical illustration
Q1. Comparison of hard-instance construction from Liu and Ye (2026) / which ideas are responsible for improving the gap?
Thank you again for your review, and we hope our answer resolves all your concerns.