On Graduated Optimization for Stochastic Non-Convex Problems

By Elad Hazan, Kfir Yehuda Levy, Shai Shalev-Shwartz. 2015

127 citations recorded by the source corpus.

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 its popularity, very little is known in terms of theoretical convergence analysis. In this paper we describe a new first-order algorithm based on graduated optimiza- tion and analyze its performance. We characterize a parameterized 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 {\epsilon}-approximate solution within O(1/\epsilon^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 a variant of our algorithm which converges at rate of O(d^2/\epsilon^4).

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Noisy Networks for Exploration (2017, background): “, Neural diffusion process (Mobahi, 2016) and graduated optimisation (Hazan et al., 2016)).”
Fast and Scalable Bayesian Deep Learning by Weight-Perturbation in Adam (2018, methodology): “, Gaussian-homotopy continuation methods (Mobahi & Fisher III, 2015), smoothedoptimization method (Leordeanu & Hebert, 2008), graduated optimization method (Hazan et al., 2016), and stochastic search methods (Zhou & Hu, 2014).”
Robust Optimization for Non-Convex Objectives (2017, background): “Finally, we note that unlike recent work on non-convex optimization [6, 1, 7] our goal in this paper is not to optimize a non-convex function.”
Empirical Analysis of the Hessian of Over-Parametrized Neural Networks (2017, background): “89) aims to ﬁnd the global minimum through the diffusion equation. Modern attempts on the same idea can be found in Mobahi & Fisher III (2015b), Mobahi & Fisher III (2015a), Mobahi (2016) and Hazan et al. (2016). Convolving the original landscape is another similar idea to transform the ener”
Learning to Teach (2018, background): “Graduated optimization (Hazan et al., 2016) heuristically reﬁnes the non-convex loss function in a from-smooth-to-sharp manner, in order to make the machine learning process more robust.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, background): “This includes random seeding, graduated optimization [25] and others.”
Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis (2017, methodology): “line of work on continuation methods and graduated optimization (Hazan et al., 2016) attempts to create sequences of smoothed approximations that can successively localize the optimum.”
Learning to Teach with Dynamic Loss Functions (2018, background): “Specially designed loss functions play important roles in boosting the performances of real-world tasks, either by approximating the non-smooth task-specific objective such as 0-1 accuracy in classification [40], NDCG in ranking [49], BLEU in machine translation [45, 3] and MAP in object detection [”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, background): “, converging to a global minimum) of stochastic algorithms has been studied in [9] for a certain family of problems, which is beyond the setting of the present work.”