Yuchen Yang

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 alpha > 3 and positive nondecreasing gain G(n) tendin...