acceptodds
Under review as a conference paper at ICLR 2027

Polylog-Tight Bounds for Step-Size Acceleration of GD under Strong Convexity

Abstract

We study how much a predefined nonnegative step-size schedule can accelerate gradient descent on -smooth, -strongly convex functions. For condition number and , we prove lower complexity bounds of rate for relative squared distance to the minimizer in both *non-anytime* and *anytime* settings. Here, is the silver ratio. We also find that the periodic Silver step-size schedule (Altschuler & Parrilo, 2025a) achieves the *anytime* upper complexity bound , extending its known bound at completed-block endpoints to every iterate beyond the accuracy threshold. Hence, our lower bounds tightly match the upper bounds up to . We also derive bounds for the function value gap and squared gradient norm.

Primary area:
optimization
Keywords:
gradient descent, iteration complexity, acceleration, non-anytime, anytime

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_AfbPOpenReview ↗
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 O(κlog⁡(1/ε))O(\kappa\log(1/\varepsilon)), recent developments involving the Silver step-size schedule have established improved upper bounds of O(κ0.786log⁡(1/ε))O(\kappa^{0.786}\log(1/\varepsilon)). However, the optimality of this dependence on the condition number κ\kappa 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 ν≈0.786\nu\approx0.786 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 (log⁡κ)γ∗(\log\kappa)^{\gamma_*}, 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 (log⁡κ)γ∗(\log\kappa)^{\gamma_*}. 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 κ\kappa, 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 κ\kappa. 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

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.

  • We agree that the current proof sketches (especially in Sections 3 and 4), as well as the full proofs, are quite difficult to follow. For our response to the readability issue, please see our response to W1 by reviewer whdf.
  • Before submission, we tried several variants of hard instance constructions, but they did not succeed in further reducing the polylogarithmic gap (log⁡κ)γ∗(\log \kappa)^{\gamma_*}. Thus, in our personal view, we believe it is very difficult to improve upon this unless we come up with a new hard instance construction beyond simply combining multiple two-coordinate transfers. In other words, we are not absolutely certain this gap is irreducible because we believe it is an artifact of the proof technique, so we do not make such a claim.
  • In the revised manuscript, we also added Remark 3.1 right after the “Why γ∗\gamma_*?” paragraph in Section 3.2, in order to provide some discussion on the polylogarithmic factor.

W2. Unclear quantitative significance of the lower bound for moderate condition numbers.

  • As the reviewer may have noticed, the current proof of Lem 2.1 only requires that κ∗\kappa_* is a universal constant. Since we have not tried to optimize our proofs in terms of the values of universal constants like κ∗\kappa_*, C0C_0, and C1C_1, the actual values of them required by the Lemma’s proof can be extremely large.
  • Using Codex (GPT-6.1 Sol Ultra Fast), we obtained a conservative upper bound of κ∗\kappa_* for which Lem 2.1’s proof works for any κ≥κ∗\kappa\ge \kappa_* as roughly 3.5×1063.5\times 10^{6}.
  • In our experience, however, we were able to shrink the eligible value of κ∗\kappa_* to 2 if we apply a more sophisticated construction of a hard-instance function based on the case analysis on the range of κ\kappa. However, we discarded this proof because the initial draft expanded to more than 90 pages, which would harm the paper's readability.
  • Nevertheless, this does not mean that our main theorem (Thm 1.1) is true only for sufficiently large values of κ\kappa. As the reviewer noted, by applying the classical quadratic lower bound, we can prove the same statement for any κ≥κ0\kappa\ge \kappa_0 with any universal constant κ0>1\kappa_0>1: please refer to our answer to the reviewer QJK8.

W3. The results only apply to deterministic, nonadaptive step-size schedules.

  • Thank you for pointing this out. We made this clear in the introduction and problem setup sections.

W4. Lack of numerical illustration

  • To empirically validate the lower bound, we indeed planned to run numerical evaluations of GD with predefined schedules, including the periodic Silver schedule (used in our anytime upper bound) on our hard instance function. However, as we mentioned in our answer to W2, the rough values of universal constants (used in the construction of the hard function) are extremely large, and the resulting hard function was almost impossible to practically implement in Python. This prevented us from conducting meaningful numerical experiments on the constructed hard instance.

Q1. Comparison of hard-instance construction from Liu and Ye (2026) / which ideas are responsible for improving the gap?

  • As we noted in our response to W1 by reviewer whdf, we believe the most critical part of our hard-instance construction is the individual optimization of the rotating shape for each local hard function. Please refer to that response for more detail.

Thank you again for your review, and we hope our answer resolves all your concerns.

After reading rebuttals from the authors. I remain my original score.

Reviewer_whdfOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the complexity of gradient descent with predefined (non-adaptive) step-sizes for smooth strongly convex minimization. For nonnegative step-sizes, the paper establishes the near-optimal complexity bound O(κνlog⁡(1/ε))O(\kappa^\nu \log(1/\varepsilon)) with ν=log⁡1+22≈0.786\nu = \log_{1+\sqrt{2}} 2 \approx 0.786 for achieving ∣xN−x⋆∣2∣x0−x⋆∣2≤ε\frac{\\|\boldsymbol{x}_N - \boldsymbol{x}^\star\\|^2}{\\|\boldsymbol{x}_0 - \boldsymbol{x}^\star\\|^2} \le \varepsilon, up to a polylogarithmic O((log⁡κ)−0.322)O((\log \kappa)^{-0.322}) factor gap. More precisely, a lower bound of N=Ω(κν(log⁡κ)−0.322log⁡(1/ε))N = \Omega(\kappa^\nu (\log \kappa)^{-0.322} \log (1/\varepsilon)) is provided, and an anytime O(κνlog⁡(1/ε))O(\kappa^\nu \log(1/\varepsilon)) complexity upper bound for periodic silver step-size schedule is established.

Critical strengths

This paper studies a problem that has recently attracted a significant interest from the theoretical optimization community, namely the step-size acceleration of GD. The problem setting is a bit different from the standard formulation of optimizing the order of sublinear convergence rate with respect to the function value gap f(xN)−f⋆f(\boldsymbol{x}_N) - f_\star for non-strongly convex smooth ff, because it focuses on the distance to the minimizer in the strongly convex setting, but it is still a closely related and interesting problem by itself.

The work tightly matches the upper and the lower complexity bounds, which is how fundamental results in optimization are stated. There is still a polylogarithmic factor gap that is not yet closed, but as this result seems to be one of the first results showing the optimality of polynomial power, I would classify it as a strong result, at least according to the traditional model of optimization research. It is also interesting that their upper bound result is anytime while the lower bound is not, which means that the two bounds are paired in a stronger sense.

Critical weaknesses

I would say that the weakness is primarily in the readability of the paper. Sections 3 and 4 reminds me of how the chain-of-thought documentation from LLM are written (e.g., as in OpenAI's famous "math" repository https://github.com/openai/math/tree/main/reasoning_traces) rather than a refined form of human explanation. The paper's AI use statement clarifies that the text was polished based on reinterpretation and refinement of the results, but as a reader, the exposition does not seem to be much more than a dry and dense proof outline. Nevertheless, there seems to be no notable flaw in the technical arguments themselves.

As a related point on readability, I think Section 1.3 could be polished further. It might be beneficial to have paragraph titles, explain the connection between the non-strongly convex and strongly-convex bounds on GD (how restarting argument can transfer non-strongly convex GD rates on function value gap to strongly convex rates on distance to solution, and how strongly convex lower bound can be used to derive a non-strongly convex lower bound by choosing κ\kappa appropriately), and explain how the literature on fundamental polynomial exponent has evolved in both settings and what the differences are. Having a table or a figure would also be preferable. In particular, I think this paper's strongly convex lower bound can be used to derive a non-strongly convex lower bound by setting κ=N1/ν(log⁡N)γ⋆/ν\kappa = N^{1/\nu} (\log N)^{\gamma_\star/\nu}, and that's tighter than the Ye & Liu (2026b) lower bound, but such connection has not been highlighted in the paper.

Finally, while I believe that the paper's theoretical results are strong and solid, given the AI's superior ability in closing theoretical questions (which also benefited the progress of this work), the paper might need a short justification that the polylogarithmic gap the paper leaves open cannot be closed or reduced easily, even with the aid of AI. The paper's analysis seems to be performed quite tightly and therefore, stepping from here to the perfect resolution of the upper-lower complexity gap will likely require a fundamentally new intuition. While the paper already explains where the polylog factor comes from, explicitly adding some sort of tightness claim might further justify the value of their approach.

Questions for authors

Please refer to the Weakness section. I would say my rating below is contingent on authors addressing the points on presentation mentioned there.

2 comments

We thank the reviewer for their constructive feedback and positive assessment. The reviewer acknowledges the significance of our problem setting, the novelty of our theoretical contributions, the correctness of the proof, and the strength of the near-tight matching between the (non-anytime) lower bound and the (anytime) upper bound.

Below, we address their concerns one by one.

W1. Readability issue

  • We agree that the proof sketch in the main text (mostly in Sections 3 and 4) and the main proofs are difficult to interpret. Due to time constraints, we will further enhance the interpretability of the proof (sketches) in our final camera-ready version. For now, the uploaded revision contains (i) a few more remarks that help readers understand the problem setting and difficult steps better, (ii) additional convergence lower bounds for smooth non-strongly convex problems under non-anytime & anytime stopping models (Cor. 1.4 & 1.5), and (iii) several notational changes to make the proof a bit more human-readable.
  • Nevertheless, we would like to briefly discuss why we obtained a polylog-tight lower bound (in Cor 1.2), compared to a concurrent preprint by Liu & Ye (2026). Both proofs use rotating gradients of local hard functions. Liu & Ye determine the rotating shape identically across the entire hard-instance construction; they explain that this is the main reason for the exp⁡(Clog⁡κ)\exp(C\sqrt{\log \kappa}) loss. On the other hand, we individually optimize the bending parameter (also called “pitch” of a logarithmic spiral, in our paper) for each local hard function according to its associated gap step sum ss and checkpoint size bb (in Eq. (3.2)). We believe that such a detailed construction is the most critical part in our proof to obtain a polylogarithmic complexity gap. We also believe that the choice of logarithmic spiral is important in obtaining the exponent γ∗≈0.322…\gamma_*\approx 0.322…; with the circular arc used by Liu & Ye, or any other curved shapes, we were not able to yield such a small exponent.
  • In fact, we have also obtained an initial draft of a proof for the same lower bound as Cor 1.2 using a single coordinate chain, without phase coupling or Brouwer’s fixed-point argument. Once we fully verify this simpler proof, we also plan to include it in the camera-ready version.

W2. Presentation of related work & Derivation of tighter non-strongly convex lower bounds

  • Thank you for your constructive suggestion. Your claim is correct. More precisely, let us take N≥2N\ge 2 and κ=2N1/ν(log⁡N/log⁡2)γ⋆/ν≥2\kappa = 2 N^{1/\nu}(\log N/\log2)^{\gamma_\star/\nu} \ge 2. Then, it implies Q(κ)=Θ(N)\mathcal{Q}(\kappa) = \Theta(N). Thus, by strong convexity and the statement of Thm 1.1, we obtain

    \ge \frac{\lVert x_N - x_\star \rVert^2}{\kappa\lVert x_0 - x_\star \rVert^2} \ge \frac{1}{\kappa} \exp\left(-\frac{CN}{\mathcal{Q}(\kappa)}\right) = \Theta\left(\frac{1}{N^{1/\nu} (\log N)^{\gamma_\star / \nu}}\right)\approx\Theta\left(\frac{1}{N^{1.271}(\log N)^{0.410}}\right).$$ This gives a **non-anytime** lower bound on GD’s convergence rate for smooth, non-strongly convex functions. It tightly matches the corresponding upper bound of rate $O(N^{-1.271})$ up to a polylogarithmic factor in $N$, which strictly improves upon the previous state-of-the-art non-anytime lower bound by Ye & Liu (2026b). We add this result as Corollary 1.4 in our revised manuscript.
  • By applying some lemmas to prove Thm 1.1 (more precisely, Lem 2.1) and borrowing the proof structure for the anytime lower bound by Jung et al. (2026) and Ye & Liu (2026b), we could also figure out the following anytime rate lower bound result for the smooth, non-strongly convex case: no step-size schedule can achieve o(N−21+ν(log⁡N)−2γ⋆1+ν)≈o(N−1.120(log⁡N)−0.361)o\left(N^{-\frac{2}{1+\nu}} (\log N)^{-\frac{2 \gamma_\star}{1+\nu}}\right) \approx o(N^{-1.120}(\log N)^{-0.361}) anytime convergence rate. We also added this result as Corollary 1.5 in our revised manuscript, with its full proof in our new Appendix I.

  • As per the reviewer’s suggestion, we added the paragraph titles in the related work part (Sec. 1.3). We also added a detailed comparison table in Appendix A of the revised manuscript.

W3. Justification for the difficulty of reducing the remaining polylogarithmic gap

  • Thank you for pointing this out. In the revised manuscript, we have added Remark 3.1 immediately after the “Why γ∗\gamma_*?” paragraph in Section 3.2 to clarify the limitation of our analysis.
  • Also, please take a look at our response to Reviewer AfbP’s W1 regarding what we have tried to do to enhance our lower-bound proofs.

Thank you again for your review, and we hope our response addresses all your concerns.

I thank the authors for the response. I maintain my score.

Reviewer_QJK8OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proves lower complexity bounds of gradient descent on LL-smooth, μ\mu-strongly convex functions. For the condition number κ=L/μ≥2\kappa = L/\mu \geq 2 and ϵ∈(0,1/2]\epsilon \in (0, 1/2], the lower complexity bounds of rate ≈Ω(κ0.786(log⁡κ)−0.322log⁡(1/ϵ))\approx \Omega(\kappa^{0.786}(\log \kappa)^{-0.322}\log(1/\epsilon)) for relative squared distance to the minimizer in both non-anytime and anytime settings are established.

Critical strengths

The complexity bound lower bounds tightly match the upper bounds up to a polynomial factor of log⁡κ\log \kappa in the anytime setting.

Critical weaknesses

The requirement on the condition number κ≥2\kappa \geq 2 exclude a large class of well-conditioned functions, for example quadratic functions.

Questions for authors

Is the condition number of the hard function close to the region 1≤κ≤21 \leq \kappa \leq 2? If so, what could be say about the complexity bound if 1≤κ≤21 \leq \kappa \leq 2 functions are included? If not, why these functions are excluded in the current results.

2 comments

Thank you for your comments and questions. We handle your concerns below.

W1/Q1. The requirement on the condition number κ≥2\kappa\ge 2…

  • In smooth strongly-convex minimization problems, the condition number κ\kappa is the key parameter that determines the “hardness” of convergence for an optimization method. It means that a larger κ\kappa of an objective function induces a slower convergence rate. Thus, the ultimate goal of convergence analysis is to figure out how fast a method converges when κ\kappa is large in particular. This is why we use asymptotic notation (OO, Ω\Omega, Θ\Theta, etc.) to compare the convergence rates.
  • On the other hand, when κ\kappa is small, it is difficult to compare the convergence rates in the asymptotic notions. Especially when κ=Θ(1)\kappa=\Theta(1) (e.g., 1≤κ≤21\le \kappa\le 2), for instance, the rates Θ(κlog⁡(1/ϵ))\Theta(\sqrt{\kappa} \log(1/\epsilon)), Θ(κlog⁡(1/ϵ))\Theta(\kappa \log(1/\epsilon)), and Θ(κ2log⁡(1/ϵ))\Theta(\kappa^2 \log(1/\epsilon)) are all the same, at least asymptotically.
  • We would also like to highlight that the boundary “2” is not necessary in our proof. We choose 2 only for simplicity in presenting the proof. In fact, we can replace it with any scalar strictly larger than 1 (e.g., 1.001). You can see this in our proof of Thm 1.1 in the later part of Sec 2.1: first, the constant CsmallC_{\rm small} in the proof is defined as a maximum of a univariate continuous function 2Q(κ)log⁡(κ+1κ−1)2\mathcal{Q}(\kappa)\log(\tfrac{\sqrt\kappa+1}{\sqrt\kappa-1}) on a closed interval [2,κ∗][2,\kappa_*]. Even when we replace the interval’s left end (”2”) with any number larger than 1, the function has a maximum on that interval as well, and thus CsmallC_{\rm small} is well-defined. Hence, we can extend the statement of our Thm 1.1 to κ≥κ0\kappa \ge \kappa_0 for any universal constant κ0>1\kappa_0>1. We also made this point clear in our main text with a footnote. Moreover, in our revised manuscript, we update the statement of Lemma D.1 (regarding the quadratic lower bound) and its proof so that it applies to any κ≥1\kappa\ge 1.

We hope our answer resolves the reviewer’s concern.

Thank the authors for the response. I will keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.