An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Optimization Année : 2019

An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration

Résumé

We propose an inexact variable-metric proximal point algorithm to accelerate gradient-based optimization algorithms. The proposed scheme, called QNing can be notably applied to incremental first-order methods such as the stochastic variance-reduced gradient descent algorithm (SVRG) and other randomized incremental optimization algorithms. QNing is also compatible with composite objectives, meaning that it has the ability to provide exactly sparse solutions when the objective involves a sparsity-inducing regularization. When combined with limited-memory BFGS rules, QNing is particularly effective to solve high-dimensional optimization problems, while enjoying a worst-case linear convergence rate for strongly convex problems. We present experimental results where QNing gives significant improvements over competing methods for training machine learning methods on large samples and in high dimensions.
Fichier principal
Vignette du fichier
quickening_arxiv.pdf (4.58 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01376079 , version 1 (04-10-2016)
hal-01376079 , version 2 (05-04-2017)
hal-01376079 , version 3 (20-07-2018)
hal-01376079 , version 4 (28-01-2019)

Identifiants

Citer

Hongzhou Lin, Julien Mairal, Zaid Harchaoui. An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration. SIAM Journal on Optimization, 2019, 29 (2), pp.1408-1443. ⟨10.1137/17M1125157⟩. ⟨hal-01376079v4⟩
1107 Consultations
1357 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More