No Universal Remainder Rate for Chambolle-Dossal Acceleration
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.31557
curl -X POST /api/v1/records/arxiv/2609.31557/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.31557/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'