# On Graduated Optimization for Stochastic Non-Convex Problems

arXiv: https://arxiv.org/abs/1503.03712 · HTML: https://mlsanity.com/paper/1503.03712/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2015.

## Built on by (most cited first, 30 of 34)

- [The Bayesian Learning Rule](https://mlsanity.com/paper/2107.04562/) (2021)
- [Smooth Tchebycheff Scalarization for Multi-Objective Optimization](https://mlsanity.com/paper/2402.19078/) (2024)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Tractable structured natural gradient descent using local parameterizations](https://mlsanity.com/paper/2102.07405/) (2021)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization](https://mlsanity.com/paper/2405.19650/) (2024)
- [Where do Large Vision-Language Models Look at when Answering Questions?](https://mlsanity.com/paper/2503.13891/) (2025)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Continuation Path Learning for Homotopy Optimization](https://mlsanity.com/paper/2307.12551/) (2023)
- [Dynamic Flows on Curved Space Generated by Labeled Data](https://mlsanity.com/paper/2302.00061/) (2023)
- [Global Optimality in Bivariate Gradient-based DAG Learning](https://mlsanity.com/paper/2306.17378/) (2023)
- [Structured second-order methods via natural gradient descent](https://mlsanity.com/paper/2107.10884/) (2021)
- [Learning Data Teaching Strategies Via Knowledge Tracing](https://mlsanity.com/paper/2111.07083/) (2021)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)
- [Optimization for Amortized Inverse Problems](https://mlsanity.com/paper/2210.13983/) (2022)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Policy Gradient Algorithms Implicitly Optimize by Continuation](https://mlsanity.com/paper/2305.06851/) (2023)
- [One-Line-of-Code Data Mollification Improves Optimization of Likelihood-based Generative Models](https://mlsanity.com/paper/2305.18900/) (2023)
- [Optimization Guarantees for Square-Root Natural-Gradient Variational Inference](https://mlsanity.com/paper/2507.07853/) (2025)
- [On the Importance of Capturing a Sufficient Diversity of Perspective for the Classification of micro-PCBs](https://mlsanity.com/paper/2101.11164/) (2021)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization](https://mlsanity.com/paper/2311.08745/) (2023)
- [Explicit and Implicit Graduated Optimization in Deep Neural Networks](https://mlsanity.com/paper/2412.11501/) (2024)
- [Stationary MMD Points](https://mlsanity.com/paper/2505.20754/) (2025)
- [An Efficient Algorithm for Deep Stochastic Contextual Bandits](https://mlsanity.com/paper/2104.05613/) (2021)
- [Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Framework](https://mlsanity.com/paper/2406.11159/) (2024)
- [Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Rate](https://mlsanity.com/paper/2409.09984/) (2024)
- [Power Homotopy for Zeroth-Order Non-Convex Optimizations](https://mlsanity.com/paper/2511.13592/) (2025)
- [A Gradient Flow Perspective on Minimum MMD Estimation](https://mlsanity.com/paper/2607.03871/) (2026)
- [AGGLIO: Global Optimization for Locally Convex Functions](https://mlsanity.com/paper/2111.03932/) (2021)

## Abstract (arXiv)

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(d2/ε4).