No Universal Remainder Rate for Chambolle-Dossal Acceleration

Yuchen Yang; Xinan Dai; Wenhao Deng; Yingdong Shi; Feng Xu; Tailin Wu

In the authors' words

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 \geq 1} n^{2} G (n) (F (x_{n}) - F^{*}) = \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 D n^{- 2 p / (p - 2)}$ , $D > 0$ , establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.

Main resultThe abstract does not state a limitation.

No Universal Remainder Rate for Chambolle-Dossal Acceleration

In the authors' words

More on Optimization that day

TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization

Optimal Prophet Inequalities for Gain from Trade

Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms

Moment Ambiguity and the Limits of Robust Stochastic Optimization