{"id":"arxiv/2609.31557","url":"https://arxiv.org/abs/2609.31557","tags":["math.OC"],"score":0,"title":"No Universal Remainder Rate for Chambolle-Dossal Acceleration","domain":"math.OC","source":"arxiv","authors":["Yuchen Yang","Xinan Dai","Wenhao Deng","Yingdong Shi","Feng Xu","Tailin Wu"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}