No Universal Remainder Rate for Chambolle–Dossal Acceleration

Chambolle–Dossal acceleration guarantees $F(x_n)-F^{\ast }=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 $\alpha >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\ge 1}{n}^{2}G(n)(F(x_n)-F^{\ast })=\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^{\ast }\sim D{n}^{-2p/(p-2)}$, $D>0$, establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.