Progressive Power Homotopy for Non-convex Optimization

Abstract

We propose a novel first-order method for non-convex optimization of the form ${\max }_{\mathbf{w}\in {\mathbb{R}}^d}{\mathbb{E}}_{\mathbf{x}\sim \mathcal{D}}[f_{\mathbf{w}}(\mathbf{x})]$, 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, $F_{N,\ddot{I}ƒ}(\hat{\mathbf{I}}¼):={\mathbb{E}}_{\mathbf{w}\sim \mathcal{N}(\hat{\mathbf{I}}¼,\ddot{I}{ƒ}^2{I}_d),\mathbf{x}\sim \mathcal{D}}[e^{N{f}_w(\mathbf{x})}]$, while progressively increasing the power parameter $N$ and decreasing the smoothing scale $\ddot{I}ƒ$ 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(d^2{\epsilon }^{-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.