Optimal Complexity and Certification of Bregman First-Order Methods

Abstract

We provide a lower bound showing that the $O(1/k)$ convergence rate of the NoLips method (a.k.a. Bregman Gradient) is optimal for the class of functions satisfying the $h$-smoothness assumption. This assumption, also known as relative smoothness, appeared in the recent developments around the Bregman Gradient method, where acceleration remained an open issue. On the way, we show how to constructively obtain the corresponding worst-case functions by extending the computer-assisted performance estimation framework of Drori and Teboulle (Mathematical Programming, 2014) to Bregman first-order methods, and to handle the classes of differentiable and strictly convex functions.

arXiv commentTo appear in Mathematical Programming

References in corpus (4)

• Optimized first-order methods for smooth convex minimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Efficient First-order Methods for Convex Minimization: a Constructive Approach
• Quartic First-Order Methods for Low-Rank Minimization

Cited by in corpus (6)

• Automated tight Lyapunov analysis for first-order methods
• Approximate Bregman Proximal Gradient Algorithm for Relatively Smooth Nonconvex Optimization
• Interpolation Constraints for Computing Worst-Case Bounds in Performance Estimation Problems
• Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA
• Dualities for non-Euclidean smoothness and strong convexity under the light of generalized conjugacy
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness