On Graduated Optimization for Stochastic Non-Convex Problems

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 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 ε-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 a variant of our algorithm which converges at rate of O(d^2/ε^4).

17 pages

References in corpus (1)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

Cited by in corpus (31)

• Noisy Networks for Exploration
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Fast and Scalable Bayesian Deep Learning by Weight-Perturbation in Adam
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Binary MIMO Detection via Homotopy Optimization and Its Deep Adaptation
• Maximum Mean Discrepancy Gradient Flow
• Robust Optimization for Non-Convex Objectives
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Training Recurrent Neural Networks by Diffusion
• Homotopy Analysis for Tensor PCA
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• ActiveStereoNet: End-to-End Self-Supervised Learning for Active Stereo Systems
• The Bayesian Learning Rule
• Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
• Tractable structured natural gradient descent using local parameterizations
• DynaNewton - Accelerating Newton's Method for Machine Learning
• Learning Data Teaching Strategies Via Knowledge Tracing
• Convex Relaxation Regression: Black-Box Optimization of Smooth Functions by Learning Their Convex Envelopes
• Data Transformation Insights in Self-supervision with Clustering Tasks
• The sharp, the flat and the shallow: Can weakly interacting agents learn to escape bad minima?
• Structured second-order methods via natural gradient descent
• Online Newton Step Algorithm with Estimated Gradient
• Graduated Optimization of Black-Box Functions
• Convergence Analysis of Homotopy-SGD for non-convex optimization
• Submodular + Concave
• An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs