On Graduated Optimization for Stochastic Non-Convex Problems

Elad Hazan, Kfir Yehuda Levy, Shai Shalev-Shwartz
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1833-1841, 2016.

Abstract

The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convex problems that has received renewed interest over the last decade.Despite being popular, very little is known in terms of its theoretical convergence analysis. In this paper we describe a new first-order algorithm based on graduated optimization and analyze its performance. We characterize a family of non-convex functions for which this algorithm provably converges to a global optimum. In particular, we prove that the algorithm converges to an ε-approximate solution within O(1 / ε^2) gradient-based steps. We extend our algorithm and analysis to the setting of stochastic non-convex optimization with noisy gradient feedback, attaining the same convergence rate. Additionally, we discuss the setting of “zero-order optimization", and devise a variant of our algorithm which converges at rate of O(d^2/ ε^4).

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-hazanb16, title = {On Graduated Optimization for Stochastic Non-Convex Problems}, author = {Hazan, Elad and Levy, Kfir Yehuda and Shalev-Shwartz, Shai}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1833--1841}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/hazanb16.pdf}, url = {https://proceedings.mlr.press/v48/hazanb16.html}, abstract = {The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convex problems that has received renewed interest over the last decade.Despite being popular, very little is known in terms of its theoretical convergence analysis. In this paper we describe a new first-order algorithm based on graduated optimization and analyze its performance. We characterize a family of non-convex functions for which this algorithm provably converges to a global optimum. In particular, we prove that the algorithm converges to an ε-approximate solution within O(1 / ε^2) gradient-based steps. We extend our algorithm and analysis to the setting of stochastic non-convex optimization with noisy gradient feedback, attaining the same convergence rate. Additionally, we discuss the setting of “zero-order optimization", and devise a variant of our algorithm which converges at rate of O(d^2/ ε^4).} }
Endnote
%0 Conference Paper %T On Graduated Optimization for Stochastic Non-Convex Problems %A Elad Hazan %A Kfir Yehuda Levy %A Shai Shalev-Shwartz %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-hazanb16 %I PMLR %P 1833--1841 %U https://proceedings.mlr.press/v48/hazanb16.html %V 48 %X The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convex problems that has received renewed interest over the last decade.Despite being popular, very little is known in terms of its theoretical convergence analysis. In this paper we describe a new first-order algorithm based on graduated optimization and analyze its performance. We characterize a family of non-convex functions for which this algorithm provably converges to a global optimum. In particular, we prove that the algorithm converges to an ε-approximate solution within O(1 / ε^2) gradient-based steps. We extend our algorithm and analysis to the setting of stochastic non-convex optimization with noisy gradient feedback, attaining the same convergence rate. Additionally, we discuss the setting of “zero-order optimization", and devise a variant of our algorithm which converges at rate of O(d^2/ ε^4).
RIS
TY - CPAPER TI - On Graduated Optimization for Stochastic Non-Convex Problems AU - Elad Hazan AU - Kfir Yehuda Levy AU - Shai Shalev-Shwartz BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-hazanb16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1833 EP - 1841 L1 - http://proceedings.mlr.press/v48/hazanb16.pdf UR - https://proceedings.mlr.press/v48/hazanb16.html AB - The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convex problems that has received renewed interest over the last decade.Despite being popular, very little is known in terms of its theoretical convergence analysis. In this paper we describe a new first-order algorithm based on graduated optimization and analyze its performance. We characterize a family of non-convex functions for which this algorithm provably converges to a global optimum. In particular, we prove that the algorithm converges to an ε-approximate solution within O(1 / ε^2) gradient-based steps. We extend our algorithm and analysis to the setting of stochastic non-convex optimization with noisy gradient feedback, attaining the same convergence rate. Additionally, we discuss the setting of “zero-order optimization", and devise a variant of our algorithm which converges at rate of O(d^2/ ε^4). ER -
APA
Hazan, E., Levy, K.Y. & Shalev-Shwartz, S.. (2016). On Graduated Optimization for Stochastic Non-Convex Problems. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1833-1841 Available from https://proceedings.mlr.press/v48/hazanb16.html.

Related Material