RT Journal Article
SR 00
ID 10.1007/s10107-021-01618-1
A1 Dragomir, Radu-Alexandru
A1 Taylor, Adrien B.
A1 Aspremont, Alexandre d'
A1 Bolte, Jérôme
T1 Optimal complexity and certification of Bregman first-order methods
JF Mathematical Programming
YR 2022
FD 2022-07
VO Vol. 194
SP 41
OP 83
AB 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
SN 1436-4646
LK https://publications.ut-capitole.fr/id/eprint/50563/
UL http://tse-fr.eu/pub/130392