Skip to main content

On Graduated Optimization for Stochastic Non-Convex Problems

Author(s): Hazan, Elad; Levy, Kfir Y; Shalev-Shwartz, Shai

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).
Publication Date: 2016
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.
ISSN: 2640-3498
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.