acceptodds
Desk rejected at ICLR 2027

No Universal Remainder Rate for Chambolle–Dossal Acceleration

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Chambolle–Dossal acceleration guarantees for every fixed smooth convex loss with a minimizer. We show that this qualitative improvement admits no universal quantitative rate. For every damping parameter and positive nondecreasing gain , we construct a fixed one-dimensional smooth convex loss whose exact CD orbit satisfies Thus no divergent gain improves the scale for all fixed losses, even with instance-dependent constants. The construction prescribes queried gradients and realizes infinitely many slow blocks within one smooth convex objective. Under local -power growth with and sufficiently strong damping, we also construct a fixed loss whose exact CD orbit satisfies , , establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.

Primary area:
optimization
Keywords:
convex optimization, accelerated gradient methods, convergence rates, lower bounds, formal verification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yQh3OpenReview ↗
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 F(xn)−F⋆=o(n−2)F(x_n)-F^\star=o(n^{-2}) does not admit a common quantitative improvement over the objective class. Specifically, for every positive nondecreasing sequence G(n)→∞G(n)\to\infty, 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 O(1/(n2G(n)))O(1/(n^2G(n))) cannot hold for all admissible objectives. The constructed objective depends on GG.

The second result establishes sharpness of the rate O(n−2p/(p−2))O(n^{-2p/(p-2)}) under local growth conditions of order p>2p>2, 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
  1. 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.

  2. 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 F(x)∼C∣x∣pF(x)\sim C|x|^p alone does not establish pF(x)≤xF′(x)pF(x)\le xF'(x). Controlling the next asymptotic term and the interpolation error is therefore an essential part of the argument.

Critical weaknesses
  1. 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.

  1. 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
  1. How sensitive is the matching example in Theorem 2 to initialization? For a fixed constructed objective, is the rate F(xn)−F⋆∼Dn−2p/(p−2)F(x_n)-F^\star\sim Dn^{-2p/(p-2)} known to hold for a nontrivial interval of standard initializations x0=x1x_0=x_1, or only for the initialization obtained from the prescribed gradient sequence?

  2. 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
AuthorsOpenReview ↗

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.

  • W1: Terminology and readability

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.

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:

LocationOriginal wordingRevised wording
Title“No Universal Remainder Rate for Chambolle–Dossal Acceleration”“Sharp Asymptotic Convergence Rates for Chambolle–Dossal Acceleration”
Section 3.2 heading“No universal remainder rate”“No common faster convergence rate”
Abstract“positive nondecreasing gain G(n)→∞G(n)\to\infty”“positive nondecreasing sequence G(n)→∞G(n)\to\infty”
Abstract“Thus no divergent gain improves the n−2n^{-2} scale for all fixed losses, even with instance-dependent constants.”“Thus no rate O(1/(n2G(n)))O(1/(n^2G(n))) with G(n)→∞G(n)\to\infty holds for all fixed losses.”
Section 1“prescribed smoothness budget”“prescribed gradient Lipschitz bound”
Section 1“Using the same inverse-orbit construction with gradients that decay as a power”“Using the same construction from a prescribed gradient sequence, now with gradients that decay as a power”
Section 2.3“sparse-scale example”“example of slow convergence”
Figure 1(d)“Late blocks defeat the gain”“Late blocks violate the error bound”
Section 4.3“and an exact power-rate tail”“whose CD error satisfies F(xn)−F⋆∼Dn−2p/(p−2)F(x_n)-F^\star\sim Dn^{-2p/(p-2)}, D>0D\gt 0”
Section 6“The no-gain loss depends on GG”The paragraph has been removed.
Appendix C heading“Exact power witnesses and endpoint flatness”“Examples attaining the power rate and endpoint flatness”

We have also revised other compressed expressions throughout the main text and appendices. The changes are marked in blue in the revised manuscript.

  • W2: Implications beyond the CD schedule

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.

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)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.

AuthorsOpenReview ↗

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 F(xn)−F⋆∼Dn−2p/(p−2)F(x_n)-F^\star\sim Dn^{-2p/(p-2)} known to hold for a nontrivial interval of standard initializations x0=x1x_0=x_1, 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 x0=x1=Rx_0=x_1=R. 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 DD. 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 p>2p\gt 2, L>0L\gt 0, and 0<s<L−10\lt s\lt L^{-1}, 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.
AuthorsOpenReview ↗

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 resultLean 4 declaration
Theorem 1 (d=1d=1)nagCD_noPointwiseUniversalGain_dimOne_prescribedRadius
Theorem 1 (every finite d≥1d\ge1)nagCD_noPointwiseUniversalGain_prescribedRadius
Theorem 2(i), upper boundsharpPowerBoundary_flatnessGrowth
Theorem 2(ii), upper boundsharpPowerBoundary_growthOnly
Theorem 2(i), matching instancesharpPowerBoundary_noFurtherGain
Theorem 2(ii), matching instancesharpPowerBoundary_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.

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

The authors study Chambolle-Dossal acceleration, which is a variant of Nesterov acceleration, and is known to have an o(n−2)o(n^{-2}) rate of convergence. In existing results, the constants as well as the gap between the Chambal-Dossal rate and the O(n−2O(n^{-2} rate established for classical Nesterov acceleration is problem-dependent. The authors establish that this gap is indeed negligible, in the sense that there exist sequences of problems for which the rate will approach n−2n^{-2}. The authors also provide sharp rates under a local growth condition.

The manuscript technically closes an open problem, and the Theorems are verified in Lean and can hence be assumed to be correct. It is however very clearly the result of an almost entirely autonomous agentic workflow. This is also appropriately acknowledged by the authors. In principle, I do not see an issue with manuscripts appearing at ICLR that have been in large part generated by LLMs. However, in evaluating the manuscript, I am looking for added value provided either by the human authors or to the human reader that goes beyond the combination of prompts and compute that generated this manuscript. In light of this, I have the following concerns:

While technically an "open problem", the problem addressed by the LLM is incremental and unlikely to have substantial impact in the ICLR community. For all practical purposes, the difference between an O(1/n^2) and an o(1/n^2) is generally accepted to be negligible, and as such the result, while technically correct is unlikely to change the perception of Cambolle-Dossal acceleration in the community.

The insight provided by the manuscript is limited. Theorem 1 is established by constructing a very particular counterexample, which is unlike any loss function we can expect to encounter in real machine learning or optimization settings. The analysis also does not apply to stochastic, adaptive, or non-convex settings as they are typically encountered in modern ML settings. As such, I do not see a useful take-away from this manuscript, other than the conclusion that Chambolle-Dossal does not provide robust acceleration in general. This has been empirically fairly well-known.

As such, I do not see substantial added value created by this manuscript beyond what could be obtained with sufficient compute and prompting of publicly available models. I do not believe that submissions of this kind to ICLR should be encouraged.

On a separate note, Theorem 2 states that "there exists a coercive loss...", yet following their theorem the author distinguish their contribution relative to existing work by noting that they "extend their upper bound...without requiring coercivity". Which is it?

Critical strengths

The manuscript answers an open problem. Theorems are verified in Lean.

Critical weaknesses

The manuscript establishes something that has been empirically well-known for a while. This is done with an artificial counterexample which is unlike any problem of relevance to the ML or optimization communities. Insight and take-aways for human readers are limited. Value added by human authors is limited. Results apply only for gradient descent, which is not commonly used in ML/AI. Manuscript is difficult to read.

Questions for authors

What is the complete list of prompts used to generate the manuscript? Theorem 2 states that "there exists a coercive loss...", yet following their theorem the author distinguish their contribution relative to existing work by noting that they "extend their upper bound...without requiring coercivity". Which is it? The theorems are verified in Lean, but the manuscript also provided natural language proofs. Do we have any sort of guarantee that the natural language proofs are a faithful representation of the lean arguments? How were the natural language proofs obtained?

7 comments
AuthorsOpenReview ↗

Response to Reviewer yVhw (1)

Thank you for reviewing our paper. We appreciate your recognition that the manuscript resolves an open problem and that the Lean verification supports the correctness of its theorems. We also appreciate your view that substantial LLM use is not, in principle, an obstacle to a paper appearing at ICLR. We first clarify the main results and their implications, which are central to assessing the contribution. We then address your concerns about the significance of the research and the use of AI in the research process.

A. Main results and their implications

  • A1: Sharpness of the little-oo guarantee and asymptotics on a fixed objective

The authors establish that this gap is indeed negligible, in the sense that there exist sequences of problems for which the rate will approach n−2n^{-2}.

For all practical purposes, the difference between an O(1/n^2) and an o(1/n^2) is generally accepted to be negligible, and as such the result, while technically correct is unlikely to change the perception of Cambolle-Dossal acceleration in the community.

Theorem 1 establishes the sharpness of CD's o(n−2)o(n^{-2}) guarantee on general smooth convex problems. Earlier results proved this guarantee but did not determine whether a stronger convergence rate, such as o(1/(n2log⁡log⁡n))o(1/(n^2\log\log n)), might also hold. We prove that, for every positive nondecreasing sequence G(n)→∞G(n)\to\infty, a guarantee of the form O(1/(n2G(n)))O(1/(n^2G(n))) is impossible for CD over general smooth convex losses.

  • A2: The result does not negate acceleration and cannot be established by finite experiments

As such, I do not see a useful take-away from this manuscript, other than the conclusion that Chambolle-Dossal does not provide robust acceleration in general. This has been empirically fairly well-known.

The manuscript establishes something that has been empirically well-known for a while.

Our result preserves the known o(n−2)o(n^{-2}) guarantee on every admissible smooth convex objective and proves that this guarantee is sharp. It does not show that CD fails to accelerate. The claim concerns every proposed common improvement G(n)→∞G(n)\to\infty, for each of which there is a fixed objective that rules out the improved rate O(1/(n2G(n)))O(1/(n^2G(n))). This is a universally quantified statement about limiting behavior, whose validity cannot be determined through empirical experiments.

  • A3: CD is a Nesterov acceleration method with a connection to optimization in ML/AI

Results apply only for gradient descent, which is not commonly used in ML/AI.

Nesterov momentum remains explicitly available through PyTorch's SGD(nesterov=True) interface. CD is an important representative of Nesterov acceleration. To our knowledge, its o(n−2)o(n^{-2}) function-value guarantee is the strongest established asymptotic guarantee for Nesterov-type methods on the general smooth convex class considered here.

To our knowledge, no method in the algorithm families represented by PyTorch's first-order optimizers has a better asymptotic convergence guarantee than CD in the general smooth convex setting. Our result thus characterizes the limitation of a method with a leading theoretical guarantee within an algorithm family that remains relevant to ML/AI optimization.

AuthorsOpenReview ↗

Response to Reviewer yVhw (2)

  • A4: The upper bound without coercivity and the coercive matching example are consistent

Theorem 2 states that "there exists a coercive loss...", yet following their theorem the author distinguish their contribution relative to existing work by noting that they "extend their upper bound...without requiring coercivity". Which is it?

These statements are consistent. Theorem 2 contains two different claims.

Universal upper bound, Theorem 2 of the manuscript:

“… For every CD initialization, F(xn)−F⋆=O(n−2p/(p−2))F(x_n)-F^\star=O(n^{-2p/(p-2)}) holds under either of the following conditions: …”

Matching example, Theorem 2 of the manuscript:

“In each regime, for every admissible parameter choice and every fixed finite dimension, there is a coercive loss satisfying these assumptions … whose exact CD orbit for some initialization satisfies F(xn)−F⋆∼Dn−2p/(p−2)F(x_n)-F^\star\sim Dn^{-2p/(p-2)}, D>0D\gt 0.”

The upper bound does not require coercivity. The matching construction satisfies coercivity in addition to the required assumptions. These strengthen the two statements in different ways: the upper bound applies to a broader class, while sharpness already holds within the smaller class of coercive objectives.

The comparison with previous work refers specifically to the upper bound. Section 3.3 of the manuscript states:

“We extend their upper bound to the finite-dimensional setting of part (ii) without requiring coercivity.”

We hope these distinctions resolve the concerns about the statements of the results.

B. Scientific significance and scope

  • B1: The role of the hard-instance construction

The insight provided by the manuscript is limited. Theorem 1 is established by constructing a very particular counterexample, which is unlike any loss function we can expect to encounter in real machine learning or optimization settings.

The construction proves a statement for every positive nondecreasing sequence G(n)→∞G(n)\to\infty. For any such proposed improvement, it produces a fixed smooth convex objective on which CD does not satisfy O(1/(n2G(n)))O(1/(n^2G(n))). It is therefore a constructive argument that rules out all common quantitative refinements, rather than a single isolated example against one proposed rate.

For this type of theoretical question, we do not think the value of a construction should be determined by how closely it resembles a commonly encountered loss. A familiar example might reveal only familiar behavior. A less typical but admissible objective can instead reveal an interesting phenomenon that empirical experience has not exposed.

  • B2: Why we focus on deterministic smooth convex optimization

The analysis also does not apply to stochastic, adaptive, or non-convex settings as they are typically encountered in modern ML settings.

Stochastic, adaptive, and nonconvex settings are important in ML. The deterministic smooth convex setting also has a foundational role in optimization theory. Even in this setting, the sharp asymptotic rate of CD had remained unresolved. We focus on this question to give the paper a clear and self-contained scope.

  • B3: What the results contribute to the broader community

While technically an "open problem", the problem addressed by the LLM is incremental and unlikely to have substantial impact in the ICLR community.

Insight and take-aways for human readers are limited.

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)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.

AuthorsOpenReview ↗

Response to Reviewer yVhw (3)

C. AI use, research process, and verification

  • C1: The authors' contribution and the standards for evaluating AI-assisted research

In principle, I do not see an issue with manuscripts appearing at ICLR that have been in large part generated by LLMs. However, in evaluating the manuscript, I am looking for added value provided either by the human authors or to the human reader that goes beyond the combination of prompts and compute that generated this manuscript.

As such, I do not see substantial added value created by this manuscript beyond what could be obtained with sufficient compute and prompting of publicly available models. I do not believe that submissions of this kind to ICLR should be encouraged.

Value added by human authors is limited.

Our AI Use Statement discloses the scope of AI use and the human authors' work. The statement in the manuscript reads:

“The initial research was conducted by a fully autonomous in-house research agent system powered by GPT-5.6 Sol and GPT-6 Astra. The human authors' initial contribution was to pose the task of improving the convergence rate of Chambolle–Dossal acceleration or proving that it cannot be further refined. Starting from this task, the agent carried out the entire initial literature search, formulated the mathematical claims, developed and wrote the proofs, produced the manuscript draft, and implemented and checked the Lean 4 formalization. The human authors subsequently used GPT-6 Astra to assist in verifying and correcting the results, refining the arguments, and preparing the final manuscript. The scope and limitations of the formal verification are described in Appendix G.2. The human authors take responsibility for the final content of this work, including all AI-generated text, claims, proofs, and code.”

With this disclosure, we believe that our work should be assessed by its scientific content under the same standards as other submissions, regardless of the extent of AI use. We, the authors, deliberately chose and used these AI tools, and the way we used them also reflects our research capabilities. We do not think the authors' contribution can be assessed by separating it entirely from the AI tools they used.

  • C2: Prompts and the scope of the disclosed research task

What is the complete list of prompts used to generate the manuscript?

The research objective stated in our AI Use Statement broadly summarizes the main content of our prompts:

“The human authors' initial contribution was to pose the task of improving the convergence rate of Chambolle–Dossal acceleration or proving that it cannot be further refined.”

This was, in essence, what we asked the system to do. We do not disclose the complete prompts because they form part of our in-house agent system and contain details of its design. The system remains an internal research tool that we have not released.

  • C3: The natural language proofs and their correspondence with Lean

The theorems are verified in Lean, but the manuscript also provided natural language proofs. Do we have any sort of guarantee that the natural language proofs are a faithful representation of the lean arguments? How were the natural language proofs obtained?

Appendix G.2 of the manuscript lists the Lean declarations and the mathematical conclusions they support. The human authors checked the mathematical meaning of these statements and their correspondence with the paper's conclusions. The substantive natural language proofs were developed during the automated research stage. The authors subsequently checked, revised, and organized them into the proofs presented in the paper.

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 resultLean 4 declaration
Theorem 1 (d=1d=1)nagCD_noPointwiseUniversalGain_dimOne_prescribedRadius
Theorem 1 (every finite d≥1d\ge1)nagCD_noPointwiseUniversalGain_prescribedRadius
Theorem 2(i), upper boundsharpPowerBoundary_flatnessGrowth
Theorem 2(ii), upper boundsharpPowerBoundary_growthOnly
Theorem 2(i), matching instancesharpPowerBoundary_noFurtherGain
Theorem 2(ii), matching instancesharpPowerBoundary_growthOnly_noFurtherGain
Reviewer_6pf3OpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether the little-o improvement over the 1/n² rate of Chambolle–Dossal acceleration admits a common quantitative rate. For every proposed divergent gain, it constructs one fixed, one-dimensional smooth convex loss on which that gain fails along an infinite subsequence. It also gives exact discrete examples attaining known rates under local growth conditions.

Critical strengths
  1. I like Figure 1. It clearly illustrates the construction and makes the main idea easier to follow.

  2. The construction uses one fixed loss and works directly with the discrete CD iterations. This gives a precise limitation for the method.

Critical weaknesses
  1. The contribution seems quite specific to the asymptotic behavior of this CD schedule. I am not sure how much the new results change our understanding of accelerated optimization more broadly.
Questions for authors
  1. Can the authors provide more details on the autonomous research process? Roughly how long did the agent run, how often did the authors intervene, and which parts of the proofs and Lean formalization were directly from the authors?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 6pf3

Thank you for your review. We appreciate your recognition of the construction on one fixed loss using the exact discrete CD iterations, and we are glad that Figure 1 helped convey the main idea. We respond to your points below.

  • W1: Implications for accelerated optimization more broadly

The contribution seems quite specific to the asymptotic behavior of this CD schedule. I am not sure how much the new results change our understanding of accelerated optimization more broadly.

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)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.

  • Q1: Autonomous research process and the authors' contributions

Can the authors provide more details on the autonomous research process? Roughly how long did the agent run, how often did the authors intervene, and which parts of the proofs and Lean formalization were directly from the authors?

We are happy to provide more details. Our automated research had two stages: developing proofs in natural language and formalizing them in Lean. Both used GPT-5.6 Sol. The first stage, including further exploration of extensions, spanned about 11 days and 22 hours. The Lean formalization of the two main results took about 48 hours. These are elapsed times for the respective stages. During both stages, humans only set the tasks and did not intervene during the runs. The substantive proof constructions and Lean formalizations were produced by our in-house agent system.

After these stages, the authors used GPT-6 Astra to assist in understanding, checking, and revising the natural language proofs. We checked the mathematical meaning of the Lean statements and their correspondence with the paper's conclusions, and reorganized the manuscript. We devoted particular effort to presenting the core construction clearly, including designing and repeatedly revising Figure 1.

Thank you again for your comments. We hope these responses address your concerns about the broader significance of our results and your questions about the autonomous research process.

Dear Reviewer,

Thank you again for your thoughtful review. Since the discussion period ends soon, we’d be grateful to hear whether our response has addressed your concerns. If anything remains unclear, we’d be happy to discuss it further.

Best regards,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers for their careful reviews and constructive comments. We appreciate their recognition that our work resolves an open problem (Reviewer yVhw) and develops nontrivial constructions on fixed objectives (Reviewers 6pf3 and yQh3). We also appreciate the positive feedback on Figure 1 for clearly illustrating the construction and making the main idea easier to follow (Reviewer 6pf3). We thank the reviewers for their suggestions on clarity and terminology (Reviewers yQh3 and yVhw) and their questions about the broader impact of our results (Reviewers 6pf3, yVhw, and yQh3). This feedback helped us improve the exposition and clarify the broader impact of our results. We updated the manuscript and supplementary materials, with manuscript changes marked in blue. The main additions and improvements are as follows:

  1. Revising the title and improving the exposition. The title was changed to “Sharp Asymptotic Convergence Rates for Chambolle–Dossal Acceleration.” We refined the wording and expressions throughout the manuscript for greater precision and clarified the notation and figure captions. We thank Reviewers yQh3 and yVhw for their feedback on the writing. For more details, see our responses to these reviewers.

  2. Expanding the discussion of broader impact. At the end of Section 6 of the revised manuscript, we added a discussion of the broader impact of our results and directions for future research. We thank Reviewers 6pf3, yVhw, and yQh3 for their questions about the broader impact of our results. For more details, see our responses to these reviewers.

  3. Updating the Lean correspondence table and formalization materials. Table 1 of the revised manuscript (Appendix G.2) was updated to make the correspondence between the main results and their Lean declarations explicit. We also updated the supplementary source code and instructions for building and auditing the formalization. We thank Reviewers yVhw and yQh3 for their questions about formal verification. For more details, see our responses to these reviewers.

Summary of responses to reviewers

  • We clarified the meaning and scope of the main results. For more details, see our response to Reviewer yVhw.

  • We discussed the broader impact of our results on accelerated optimization and future research. For more details, see our responses to Reviewers 6pf3, yVhw, and yQh3.

  • We explained the research process and the use of AI. For more details, see our responses to Reviewers 6pf3 and yVhw.

  • We described how the proofs were checked and how the manuscript corresponds to the Lean formalization. For more details, see our responses to Reviewers yVhw and yQh3.

  • We answered the initialization question through a separate supplementary analysis. For more details, see our response to Reviewer yQh3.

We thank the reviewers again for their feedback, which helped us improve the paper.

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

Related papers

Discussion (0)

Sign in to comment.