To refer to this page use:
|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).|
|Citation:||Hazan, Elad, Kfir Yehuda Levy, and Shai Shalev-Shwartz. "On Graduated Optimization for Stochastic Non-Convex Problems." In Proceedings of The 33rd International Conference on Machine Learning (2016): pp. 1833-1841.|
|Pages:||1833 - 1841|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings of The 33rd International Conference on Machine Learning|
|Version:||Final published version. Article is made available in OAR by the publisher's permission or policy.|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.