No Universal Remainder Rate for Chambolle-Dossal Acceleration
Yuchen Yang, Xinan Dai, Wenhao Deng, Yingdong Shi, Feng Xu, Tailin Wu
math.OC
Sep 25, 2026 · v1
TL;DR
Both main results on Chambolle-Dossal acceleration's lack of universal remainder rate and rate sharpness are formally verified in Lean 4.
Abstract
Chambolle-Dossal acceleration guarantees $F(x_n)-F^*=o(n^{-2})$ for every fixed smooth convex loss with a minimizer. We show that this qualitative improvement admits no universal quantitative rate. For every damping parameter $α>3$ and positive nondecreasing gain $G(n)\to\infty$, we construct a fixed one-dimensional smooth convex loss whose exact CD orbit satisfies $\sup_{n\ge1} n^2G(n)\bigl(F(x_n)-F^*\bigr)=\infty$. Thus no divergent gain improves the $n^{-2}$ 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 $p$-power growth with $p>2$ and sufficiently strong damping, we also construct a fixed loss whose exact CD orbit satisfies $F(x_n)-F^*\sim Dn^{-2p/(p-2)}$, $D>0$, establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.
Problem
Chambolle-Dossal (CD) acceleration guarantees F(x_n)-F* = o(n^{-2}) for every fixed smooth convex loss with a minimizer. The question is whether this qualitative improvement admits any universal quantitative decay rate for the normalized residual, with instance-dependent constants.
Approach
For every damping α>3 and every positive nondecreasing divergent gain G(n), a fixed one-dimensional smooth convex loss is constructed whose exact CD orbit defeats the proposed gain. The construction prescribes nonincreasing queried gradients, inverts the CD recurrence to recover an exact orbit, and interpolates and integrates the derivative to obtain a coercive C^{1,1} loss with separated constant-gradient blocks. Under local p-power growth (p>2) with strong damping, a shifted power gradient sequence yields a loss with exact power-rate asymptotics.
Results
No divergent gain improves the n^{-2} scale for all fixed losses: sup_n n^2 G(n)(F(x_n)-F*) = ∞. A fixed loss with F(x_n)-F* D n^{-2p/(p-2)}, D>0, establishes sharpness of the known convergence rate. Both main results are formally verified in Lean 4.
