No Universal Remainder Rate for Chambolle-Dossal Acceleration
Abstract
Chambolle-Dossal acceleration guarantees F(xn)−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)→∞, we construct a fixed one-dimensional smooth convex loss whose exact CD orbit satisfies supn≥1 n2G(n)(F(xn)−F*)=∞. 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(xn)−F*∼ Dn−2p/(p−2), D>0, establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.
Related
- The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization
- The kinematics of global warming: Semiparametric analysis of warming level, rate, and acceleration
- A Solvable Model of Adaptive Learning Rate Rescaling: Acceleration, Stability & Scaling
- Finite-Time Blowup for Navier-Stokes with Smooth Forcing, Part I: Construction of Self-Similar Solutions with Admissible Stress and Flat Remainder
- Chance-Constrained Nonlinear Covariance Control via Robust Linearization Remainder Bounds
BibTeX
@misc{yang2026universal,
title = {{No Universal Remainder Rate for Chambolle-Dossal Acceleration}},
author = {Yuchen Yang and Xinan Dai and Wenhao Deng and Yingdong Shi and Feng Xu and Tailin Wu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31557},
eprint = {2609.31557},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31557},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - No Universal Remainder Rate for Chambolle-Dossal Acceleration
AU - Yuchen Yang
AU - Xinan Dai
AU - Wenhao Deng
AU - Yingdong Shi
AU - Feng Xu
AU - Tailin Wu
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31557
UR - https://arxiv.org/abs/2609.31557
AB - 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)→∞, we construct a fixed one-dimensional smooth convex loss whose exact CD orbit satisfies sup_n≥1 n^2G(n)(F(x_n)−F^*)=∞. 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^*∼ Dn^−2p/(p−2), D>0, establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.
ER -