一种新优化方法，能高效找到非凸问题的全局近似解。
Progressive Power Homotopy for Non-convex Optimization
- 通过渐进提升幂参数并缩小平滑尺度，构造更优的代理目标函数。
- 理论证明迭代复杂度接近 $O(d^2\varepsilon^{-2})$，收敛至全局最优附近。
- 适合样本量逼近理论极限的相位恢复与小规模神经网络训练。
我们提出一种针对非凸优化问题 $\max_{\bm{w}\in\mathbb{R}^d}\mathbb{E}_{\bm{x}\sim\mathcal{D}}[f_{\bm{w}}(\bm{x})]$ 的新型一阶方法，称为渐进幂同伦（Prog-PowerHP）。该方法对经过幂变换和高斯平滑后的代理目标函数 $F_{N,σ}(\bmμ):=\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bmμ,σ^2I_d),\bm{x}\sim\mathcal{D}}[e^{Nf_w(\bm{x})}]$ 进行随机梯度上升，并沿优化轨迹逐步增大幂参数 $N$ 且减小平滑尺度 $σ$。在弱正则性条件下，我们证明了 Prog-PowerHP 可以以几乎 $O(d^2\varepsilon^{-2})$ 的迭代复杂度收敛到全局最优的小邻域内。实验表明，在样本数与维度比接近信息论极限的相位恢复任务中，以及在参数量不足的两层神经网络训练中，Prog-PowerHP 表现显著优于标准一阶方法。这些结果表明，该方法在杂乱的非凸优化景观中尤其有效。
原文摘要 · Abstract (English)
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,σ}(\bmμ):=\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bmμ,σ^2I_d),\bm{x}\sim\mathcal{D}}[e^{Nf_w(\bm{x})}]$, 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(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。