# Progressive Power Homotopy for Non-convex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 22 Jan 2026.

## Builds on (most cited first, 25 of 25)

- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Fundamental Limits of Weak Recovery with Applications to Phase Retrieval](https://mlsanity.com/paper/1708.05932/) (2017)
- [On Graduated Optimization for Stochastic Non-Convex Problems](https://mlsanity.com/paper/1503.03712/) (2015)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Dynamic Local Regret for Non-convex Online Forecasting](https://mlsanity.com/paper/1910.07927/) (2019)
- [Single Loop Gaussian Homotopy Method for Non-convex Optimization](https://mlsanity.com/paper/2203.05717/) (2022)
- [Continuation Path Learning for Homotopy Optimization](https://mlsanity.com/paper/2307.12551/) (2023)
- [Realistic Evaluation of Deep Partial-Label Learning Algorithms](https://mlsanity.com/paper/2502.10184/) (2025)
- [Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimization](https://mlsanity.com/paper/2106.11180/) (2021)
- [Neyman-Pearson classification: parametrics and sample size requirement](https://mlsanity.com/paper/1802.02557/) (2018)
- [Universal Convexification via Risk-Aversion](https://mlsanity.com/paper/1406.0554/) (2014)
- [Generalization and Robustness of the Tilted Empirical Risk](https://mlsanity.com/paper/2409.19431/) (2024)
- [Global Optimization with A Power-Transformed Objective and Gaussian Smoothing](https://mlsanity.com/paper/2412.05204/) (2024)
- [Power Homotopy for Zeroth-Order Non-Convex Optimizations](https://mlsanity.com/paper/2511.13592/) (2025)

## Abstract (arXiv)

We propose a novel first-order method for non-convex optimization of the form max_bmw∈ℝdmathbbE_bmx~D[f_bmw(bmx)], termed Progressive Power Homotopy (Prog-PowerHP). The method applies stochastic gradient ascent to a surrogate objective obtained by first performing a power transformation and then Gaussian smoothing, FN,σ(bmμ):=mathbbE_bmw~N(bmμ,σ2Id),bmx~D[e^Nfw(bmx)], while progressively increasing the power parameter N and decreasing the smoothing scale σ along the optimization trajectory. We prove that, under mild regularity conditions, Prog-PowerHP converges to a small neighborhood of the global optimum with an iteration complexity scaling nearly as O(d2varepsilon-2). Empirically, Prog-PowerHP demonstrates clear advantages in phase retrieval when the samples-to-dimension ratio approaches the information-theoretic limit, and in training two-layer neural networks in under-parameterized regimes. These results suggest that Prog-PowerHP is particularly effective for navigating cluttered non-convex landscapes where standard first-order methods struggle.