TY - GEN
T1 - On graduated optimization for stochastic non-convex problems
AU - Hazan, Elad
AU - Levy, Kfir Y.
AU - Shalev-Shwartz, Shai
N1 - Publisher Copyright:
© 2016 by the author(s).
PY - 2016
Y1 - 2016
N2 - The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convcx 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/ϵ4) 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(d2/ϵ4).
AB - The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convcx 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/ϵ4) 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(d2/ϵ4).
UR - http://www.scopus.com/inward/record.url?scp=84998952820&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84998952820&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84998952820
T3 - 33rd International Conference on Machine Learning, ICML 2016
SP - 2726
EP - 2739
BT - 33rd International Conference on Machine Learning, ICML 2016
A2 - Weinberger, Kilian Q.
A2 - Balcan, Maria Florina
PB - International Machine Learning Society (IMLS)
T2 - 33rd International Conference on Machine Learning, ICML 2016
Y2 - 19 June 2016 through 24 June 2016
ER -