Progressive Power Homotopy for Non-convex Optimization

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.