Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization

Zeyuan Allen-Zhu
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:179-185, 2018.

Abstract

The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasing important in machine learning, and is the core machinery for PCA, SVD, regularized Newton’s method, accelerated non-convex optimization, and more. We show how to provably obtain an accelerated stochastic algorithm for minimizing sum-of-nonconvex functions, by adding one additional line to the well-known SVRG method. This line corresponds to momentum, and shows how to directly apply momentum to the finite-sum stochastic minimization of sum-of-nonconvex functions. As a side result, our method enjoys linear parallel speed-up using mini-batch.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-allen-zhu18a, title = {{K}atyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization}, author = {Allen-Zhu, Zeyuan}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {179--185}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/allen-zhu18a/allen-zhu18a.pdf}, url = {https://proceedings.mlr.press/v80/allen-zhu18a.html}, abstract = {The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasing important in machine learning, and is the core machinery for PCA, SVD, regularized Newton’s method, accelerated non-convex optimization, and more. We show how to provably obtain an accelerated stochastic algorithm for minimizing sum-of-nonconvex functions, by adding one additional line to the well-known SVRG method. This line corresponds to momentum, and shows how to directly apply momentum to the finite-sum stochastic minimization of sum-of-nonconvex functions. As a side result, our method enjoys linear parallel speed-up using mini-batch.} }
Endnote
%0 Conference Paper %T Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization %A Zeyuan Allen-Zhu %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-allen-zhu18a %I PMLR %P 179--185 %U https://proceedings.mlr.press/v80/allen-zhu18a.html %V 80 %X The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasing important in machine learning, and is the core machinery for PCA, SVD, regularized Newton’s method, accelerated non-convex optimization, and more. We show how to provably obtain an accelerated stochastic algorithm for minimizing sum-of-nonconvex functions, by adding one additional line to the well-known SVRG method. This line corresponds to momentum, and shows how to directly apply momentum to the finite-sum stochastic minimization of sum-of-nonconvex functions. As a side result, our method enjoys linear parallel speed-up using mini-batch.
APA
Allen-Zhu, Z.. (2018). Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:179-185 Available from https://proceedings.mlr.press/v80/allen-zhu18a.html.

Related Material