TY  - JOUR
CY  - Berlin
ID  - publications50563
UR  - http://tse-fr.eu/pub/130392
A1  - Dragomir, Radu-Alexandru
A1  - Taylor, Adrien B.
A1  - Aspremont, Alexandre d'
A1  - Bolte, Jérôme
Y1  - 2022/07//
N2  - We provide a lower bound showing that the O(1/k) convergence rate of the NoLips method (a.k.a. Bregman Gradient or Mirror Descent) is optimal for the class of problems satisfying the relative smoothness assumption. This assumption appeared in the recent developments around the Bregman Gradient method, where acceleration remained an open issue. The main inspiration behind this lower bound stems from an extension of the performance estimation framework of Drori and Teboulle (Mathematical Programming, 2014) to Bregman first-order methods. This technique allows computing worst-case scenarios for NoLips in the context of relatively-smooth minimization. In particular, we used numerically generated worst-case examples as a basis for obtaining the general lower bound.
PB  - Springer Verlag
JF  - Mathematical Programming
VL  - Vol. 194
SN  - 1436-4646
TI  - Optimal complexity and certification of Bregman first-order methods
SP  - 41
AV  - public
EP  - 83
ER  -