No Universal Remainder Rate for Chambolle-Dossal Acceleration

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.

Source: arXiv:2609.31557v1 - http://arxiv.org/abs/2609.31557v1 PDF: https://arxiv.org/pdf/2609.31557v1 Original Link: http://arxiv.org/abs/2609.31557v1