Catalyst for Gradient-based Nonconvex Optimization

Courtney Paquette, Hongzhou Lin, Dmitriy Drusvyatskiy, Julien Mairal, Zaid Harchaoui
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:613-622, 2018.

Abstract

We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them without assuming any knowledge about the convexity of the objective. In general, the scheme is guaranteed to produce a stationary point with a worst-case efficiency typical of first-order methods, and when the objective turns out to be convex, it automatically accelerates in the sense of Nesterov and achieves near-optimal convergence rate in function values. We conclude the paper by showing promising experimental results obtained by applying our approach to incremental algorithms such as SVRG and SAGA for sparse matrix factorization and for learning neural networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-paquette18a, title = {Catalyst for Gradient-based Nonconvex Optimization}, author = {Paquette, Courtney and Lin, Hongzhou and Drusvyatskiy, Dmitriy and Mairal, Julien and Harchaoui, Zaid}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {613--622}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/paquette18a/paquette18a.pdf}, url = {https://proceedings.mlr.press/v84/paquette18a.html}, abstract = {We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them without assuming any knowledge about the convexity of the objective. In general, the scheme is guaranteed to produce a stationary point with a worst-case efficiency typical of first-order methods, and when the objective turns out to be convex, it automatically accelerates in the sense of Nesterov and achieves near-optimal convergence rate in function values. We conclude the paper by showing promising experimental results obtained by applying our approach to incremental algorithms such as SVRG and SAGA for sparse matrix factorization and for learning neural networks.} }
Endnote
%0 Conference Paper %T Catalyst for Gradient-based Nonconvex Optimization %A Courtney Paquette %A Hongzhou Lin %A Dmitriy Drusvyatskiy %A Julien Mairal %A Zaid Harchaoui %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-paquette18a %I PMLR %P 613--622 %U https://proceedings.mlr.press/v84/paquette18a.html %V 84 %X We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them without assuming any knowledge about the convexity of the objective. In general, the scheme is guaranteed to produce a stationary point with a worst-case efficiency typical of first-order methods, and when the objective turns out to be convex, it automatically accelerates in the sense of Nesterov and achieves near-optimal convergence rate in function values. We conclude the paper by showing promising experimental results obtained by applying our approach to incremental algorithms such as SVRG and SAGA for sparse matrix factorization and for learning neural networks.
APA
Paquette, C., Lin, H., Drusvyatskiy, D., Mairal, J. & Harchaoui, Z.. (2018). Catalyst for Gradient-based Nonconvex Optimization. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:613-622 Available from https://proceedings.mlr.press/v84/paquette18a.html.

Related Material