Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Optimal Complexity and Certification of Bregman First-Order Methods

Radu-Alexandru Dragomir 1 Adrien Taylor 2 Alexandre d'Aspremont 2 Jérôme Bolte 1
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Radu-Alexandru Dragomir <>
Submitted on : Thursday, November 28, 2019 - 11:24:44 AM
Last modification on : Thursday, July 1, 2021 - 5:58:09 PM

Links full text


  • HAL Id : hal-02384167, version 1
  • ARXIV : 1911.08510


Radu-Alexandru Dragomir, Adrien Taylor, Alexandre d'Aspremont, Jérôme Bolte. Optimal Complexity and Certification of Bregman First-Order Methods. 2019. ⟨hal-02384167⟩



Record views