No Universal Remainder Rate for Chambolle-Dossal Acceleration

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 alpha > 3 and positive nondecreasing gain G(n) tending to infinity, we construct a fixed one-dimensional smooth convex loss whose exact CD orbit satisfies sup_{n >= 1} n^2 G(n) (F(x_n) - F*) = infinity. 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* ~ D n^(-2p/(p-2)), D > 0, establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4. This record contains the signed preprint and accompanying research materials: LaTeX sources, Lean 4 formalization sources, simulation code and saved results, figure-generation scripts, and reproduction instructions. Appendix G describes the scope of the formal verification and the supplementary materials. The archive README provides build and reproduction commands. Yuchen Yang and Xinan Dai contributed equally. Corresponding author: Tailin Wu (wutailin@westlake.edu.cn). Xinan Dai and Wenhao Deng contributed to this research during their internships at Westlake University.