Geodesic
Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
Fercoq, Olivier1
1 LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Open Journal of Mathematical Optimization, Tome 4 (2023), article no. 6, 34 p.

Voir la notice de l'article provenant de la source Numdam

We study the linear convergence of the primal-dual hybrid gradient method. After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems. We thus introduce the quadratic error bound of the smoothed gap, a new regularity assumption that holds for a wide class of optimization problems. Equipped with this tool, we manage to prove tighter convergence rates. Then, we show that averaging and restarting the primal-dual hybrid gradient allows us to leverage better the regularity constant. Numerical experiments on linear and quadratic programs, ridge regression and image denoising illustrate the findings of the paper.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/ojmo.26
Keywords: linear convergence, primal-dual algorithm, error bound, restart

Fercoq, Olivier 1

1 LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{OJMO_2023__4__A6_0,
     author = {Fercoq, Olivier},
     title = {Quadratic error bound of the smoothed gap  and the restarted averaged primal-dual hybrid gradient},
     journal = {Open Journal of Mathematical Optimization},
     eid = {6},
     pages = {1--34},
     publisher = {Universit\'e de Montpellier},
     volume = {4},
     year = {2023},
     doi = {10.5802/ojmo.26},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/ojmo.26/}
}
TY  - JOUR
AU  - Fercoq, Olivier
TI  - Quadratic error bound of the smoothed gap  and the restarted averaged primal-dual hybrid gradient
JO  - Open Journal of Mathematical Optimization
PY  - 2023
SP  - 1
EP  - 34
VL  - 4
PB  - Université de Montpellier
UR  - http://geodesic.mathdoc.fr/articles/10.5802/ojmo.26/
DO  - 10.5802/ojmo.26
LA  - en
ID  - OJMO_2023__4__A6_0
ER  - 
%0 Journal Article
%A Fercoq, Olivier
%T Quadratic error bound of the smoothed gap  and the restarted averaged primal-dual hybrid gradient
%J Open Journal of Mathematical Optimization
%D 2023
%P 1-34
%V 4
%I Université de Montpellier
%U http://geodesic.mathdoc.fr/articles/10.5802/ojmo.26/
%R 10.5802/ojmo.26
%G en
%F OJMO_2023__4__A6_0
Fercoq, Olivier. Quadratic error bound of the smoothed gap  and the restarted averaged primal-dual hybrid gradient. Open Journal of Mathematical Optimization, Tome 4 (2023), article  no. 6, 34 p.. doi: 10.5802/ojmo.26

Cité par Sources :