No Universal Remainder Rate for Chambolle-Dossal Acceleration
En palabras de los autores
Chambolle-Dossal acceleration guarantees for every fixed smooth convex loss with a minimizer. We show that this qualitative improvement admits no universal quantitative rate. For every damping parameter and positive nondecreasing gain , we construct a fixed one-dimensional smooth convex loss whose exact CD orbit satisfies . Thus no divergent gain improves the 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 -power growth with and sufficiently strong damping, we also construct a fixed loss whose exact CD orbit satisfies , , establishing the sharpness of the known convergence rate. Both main results are formally verified in Lean 4.
Apareció: lunes, 28 de septiembre. arXiv. Preprint, todavía sin revisión por pares.