- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies the sharpness of asymptotic convergence guarantees for Chambolle–Dossal (CD) acceleration on smooth convex objectives.
The first result shows that the known guarantee does not admit a common quantitative improvement over the objective class. Specifically, for every positive nondecreasing sequence , the authors construct a fixed one-dimensional convex objective with a prescribed gradient Lipschitz bound and initial distance such that
$ \sup_{n\ge1}n^2G(n)\bigl(F(x_n)-F^\star\bigr)=\infty. $
Thus, a bound of the form cannot hold for all admissible objectives. The constructed objective depends on .
The second result establishes sharpness of the rate under local growth conditions of order , together with the stated flatness or damping assumptions. For every admissible parameter choice, the authors construct an objective and initialization satisfying $ F(x_n)-F^\star\sim Dn^{-2p/(p-2)}. $ The construction prescribes gradient values at the extrapolated points, solves the CD recurrence, and interpolates the derivative to obtain a single smooth convex objective.
Critical strengths
-
Theorem 1 addresses a meaningful question. Theorem 1 constructs one objective for which the proposed faster bound fails at arbitrarily late iterations. Allowing the bound’s constant and starting iteration to depend on the objective makes the result strong. The construction also works in one dimension, so the conclusion does not rely on increasing the dimension or changing these parameters with the iteration budget. Overall, the proof idea is nontrivial.
-
Theorem 2 establishes asymptotic equivalence with a positive leading constant, which is stronger than identifying the decay exponent numerically. In the proof of Theorem 2, the leading asymptotic alone does not establish . Controlling the next asymptotic term and the interpolation error is therefore an essential part of the argument.
Critical weaknesses
- The exposition is hard to follow. The paper frequently uses author-defined shorthand and densely compressed phrases whose meanings are not clear in an optimization context. This makes the arguments difficult to follow and obscures the mathematical contributions. Readability is particularly important for a theoretical paper: readers should be able to understand the results, verify the arguments, and build on the methods without repeatedly translating specialized labels into familiar mathematical statements.
Examples include, just list a few of them: “universal remainder rate”, “gain”, “divergent gain”, “no-gain loss”, “prescribed smoothness budget”, “inverse-orbit construction”, “sparse-scale example”, “exact power-rate tail”, “power witnesses”, and “Late blocks defeat the gain”. Some of these may be defined somewhere, but their cumulative use places a lot of interpretive burden on the reader.
- The scope of the contribution is limited. The results concern a particular deterministic CD momentum on convex objectives. This is interesting, but its implications for other accelerated methods and optimizers in AI/ML remain limited.
Although the contribution is reasonable, I doubt that the paper, in its current presentation, would be a fit for ICLR and the community.
Questions for authors
-
How sensitive is the matching example in Theorem 2 to initialization? For a fixed constructed objective, is the rate known to hold for a nontrivial interval of standard initializations , or only for the initialization obtained from the prescribed gradient sequence?
-
Although the main results are formally verified in Lean 4, the formalization may not cover every argument in the manuscript. Have the authors independently checked the complete proof themselves without a machine?
6 comments
Response to Reviewer yQh3 (2)
- Q1: Sensitivity of the matching example to initialization
How sensitive is the matching example in Theorem 2 to initialization? For a fixed constructed objective, is the rate known to hold for a nontrivial interval of standard initializations , or only for the initialization obtained from the prescribed gradient sequence?
Thank you for this question. The original manuscript proves the matching asymptotic equivalence for the constructed objective at the associated standard initialization . We have now studied perturbations of this initialization while keeping the same objective fixed. For the one-dimensional construction, under strict damping, an interval of nearby standard initializations preserves the same asymptotic constant . At the admissible critical parameter, nearby initializations preserve the same convergence order, but every nonreference initialization in this interval has no fixed positive asymptotic constant. These two regimes therefore need to be distinguished when answering the question about asymptotic equivalence.
The precise statement is as follows.
Supplementary proposition: Local stability of the fixed one-dimensional construction under standard initialization.
Fix , , and , and define
\rho=\delta+2,\qquad q=p\delta=\frac{2p}{p-2}.$$ Assume $$\alpha\gt 3,\qquad \alpha\ge1+2\delta,\qquad M\ge\alpha+\frac{\rho}{sL}.$$ Let $F$ be the fixed one-dimensional objective constructed in Appendices C.2–C.3, Lemmas 5–6, of the manuscript. Specifically, set $g_j=(j+M)^{-\rho}$ and use Appendix B.1, Lemma 3, to generate the reference orbit's extrapolated points, where CD evaluates the gradient. Interpolate the prescribed gradient values linearly between these points, extend the resulting function $\psi$ as specified in the manuscript, and define $F(x)=\int_0^x\psi(t)\\,dt$. Thus $F'=\psi$ and $F^\star=F(0)=0$. Let $R\gt 0$ be the standard initial point associated with this construction, and set $$A=\frac{s}{\delta(\alpha-\delta-1)},\qquad D=\frac{A}{p}.$$ For the same objective $F$, let $x_n(r)$ denote the exact CD iterates starting from $x_0=x_1=r$. There exists $0\lt \varepsilon\lt R$ such that $I=(R-\varepsilon,R+\varepsilon)$ has the following properties: 1. **Strict damping.** If $\alpha\gt 1+2\delta$, then, for every $r\in I$, $$x_n(r)\sim An^{-\delta},\qquad F(x_n(r))-F^\star\sim Dn^{-q}.$$ Both $A$ and $D$ are independent of $r$. 2. **Critical parameter.** If $\alpha=1+2\delta$, then, for every $r\in I$, $$F(x_n(r))-F^\star=\Theta(n^{-q}).$$ The positive lower and upper constants can be chosen uniformly over $r\in I$. The reference initialization $r=R$ still satisfies both asymptotic equivalences in the first case. For every $r\in I\setminus\\{R\\}$, $$\begin{aligned} 0 &\lt \liminf_{n\to\infty}n^q\bigl(F(x_n(r))-F^\star\bigr)\\\\ &\lt \limsup_{n\to\infty}n^q\bigl(F(x_n(r))-F^\star\bigr) \lt \infty. \end{aligned}$$ Consequently, no $D'\gt 0$ gives $F(x_n(r))-F^\star\sim D'n^{-q}$ for these perturbed initializations. The conclusions in both cases have been formally checked in Lean 4 for this same fixed construction and with the stated parameter conditions. The revised supplementary materials include the complete natural language proof in `CD_initialization_supplement.pdf` and its LaTeX source, together with the separate `cd_initialization_lean/` package. For readability, the proof separates the properties of the normalized variables, the local recurrence, and the energy estimates for the two regimes into lemmas. Section 6 of the supplementary proof describes the formal verification of these additional results.Response to Reviewer yQh3 (3)
- Q2: Scope of formal verification and independent checking by the authors
Although the main results are formally verified in Lean 4, the formalization may not cover every argument in the manuscript. Have the authors independently checked the complete proof themselves without a machine?
Yes. The human authors independently reviewed the complete mathematical proofs after the assisted checking and revision process described below.
For the mathematical proofs, the authors first used GPT-6 Astra to assist in understanding the core arguments in the initial draft. We then examined each lemma, theorem, and proposition, working through the proof ideas and using Astra for adversarial checks. The authors identified omitted steps, insufficiently explained derivations, and unclear notation, and used Astra to help make the proofs complete and explicit. Finally, the human authors independently reviewed the complete proofs. AI assistance was used in the analysis and revision. The final complete review was performed independently by the human authors.
We have made the correspondence more explicit in Appendix G.2 of the revised manuscript. Table 1 of the revised manuscript now maps each statement in Theorems 1 and 2 to its specific Lean 4 declaration, as reproduced below. All declarations belong to the NAGPointwiseRates namespace.
Table 1 of the revised manuscript: Correspondence between manuscript results and Lean 4 declarations.
| Manuscript result | Lean 4 declaration |
|---|---|
| Theorem 1 () | nagCD_noPointwiseUniversalGain_dimOne_prescribedRadius |
| Theorem 1 (every finite ) | nagCD_noPointwiseUniversalGain_prescribedRadius |
| Theorem 2(i), upper bound | sharpPowerBoundary_flatnessGrowth |
| Theorem 2(ii), upper bound | sharpPowerBoundary_growthOnly |
| Theorem 2(i), matching instance | sharpPowerBoundary_noFurtherGain |
| Theorem 2(ii), matching instance | sharpPowerBoundary_growthOnly_noFurtherGain |
Thank you again for the detailed comments. They led us to improve the exposition and to establish the additional initialization results. We hope the revisions and supplementary proofs address your concerns.
Response to Reviewer yQh3 (1)
Thank you for your careful review. We appreciate your recognition of the significance and nontrivial construction in Theorem 1, and of the difficulties in proving Theorem 2. We respond to your suggestions and questions below.
Thank you for identifying these specific issues. We have revised the terms you highlighted, along with similar expressions elsewhere, to describe the mathematical content more directly. The following examples show the original and revised wording:
We have also revised other compressed expressions throughout the main text and appendices. The changes are marked in blue in the revised manuscript.
We welcome the opportunity to discuss this question. Our results focus on the CD schedule. However, CD is an important representative of Nesterov acceleration, and, to our knowledge, its o(n−2) guarantee is the strongest established asymptotic function-value guarantee for Nesterov-type methods in the general smooth convex setting. Our work establishes the sharpness of this guarantee and determines the precise convergence limitation of CD.
This leads to a broader question: without strengthening the smooth convex assumptions, can a Nesterov-type method admit a stronger common asymptotic guarantee, or does the limitation shown by CD reflect a boundary shared by a wider range of acceleration mechanisms?
Our result provides a concrete starting point for both directions. If the limitation extends to other methods, our hard-instance construction may provide a basis for broader lower bounds. If other methods can overcome it, the mechanism behind our slow convergence examples provides an obstacle against which new update rules can be tested and designed. We hope this work encourages further investigation of whether classical acceleration has reached its limits or whether new acceleration mechanisms remain to be discovered.
We have added this discussion to Section 6 (Conclusion and limitation) of the revised manuscript, outlining this open question and how our construction may inform future research.