We propose a novel first-order method for non-convex optimization of the form $\max_{ \bm{ w}\in\mathbb{ R}^d}\mathbb{ E}_{ \bm{ x}\sim\mathcal{ D}}[f_{ \bm{ w}}(\bm{ 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,\sigma}(\bm{ \mu}):=\mathbb{ E}_{ \bm{ w}\sim\mathcal{ N}(\bm{ \mu},\sigma^2I_d),\bm{ x}\sim\mathcal{ D}}[e^{ Nf_w(\bm{ x})}]$, while progressively increasing the power parameter $N$ and decreasing the smoothing scale $\sigma$ 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\varepsilon^{ -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.
Categories: math.OC cs.AI cs.LG