提出可精确控制的扰动算法，高效逃离非凸优化中的鞍点。
Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation
- 基于曲率校准的扰动机制，分离梯度下降与逃逸鞍点阶段。
- 理论证明在 $O(\ell\Delta_f/\varepsilon^2)$ 次梯度评估内收敛到二阶驻点。
- 算法可扩展至随机和有限差分版本，适合实际机器学习任务。
我们对平滑非凸优化中一阶方法逃离严格鞍点的问题进行了全面理论分析。主要贡献是提出一种扰动鞍点逃逸下降（PSD）算法，具有完全显式的常数，并严格区分梯度下降与鞍点逃逸阶段。对于梯度 $\ell$-利普希茨、海森 $\rho$-利普希茨的函数 $f:\mathbb{R}^d\to\mathbb{R}$，我们证明了 PSD 以高概率在最多 $O(\ell\Delta_f/\varepsilon^2)$ 次梯度评估完成下降阶段后，每轮逃逸仅需 $O((\ell/\sqrt{\rho\varepsilon})\log(d/\delta))$ 次评估，且最多需要 $O(\ell\Delta_f/\varepsilon^2)$ 轮逃逸即可找到 $(\varepsilon, \sqrt{\rho\varepsilon})$-近似二阶驻点。我们在合成函数和实际机器学习任务上进行了大量实验，验证了理论预测的对数维度依赖性和每轮函数值下降规律。此外，我们还提供了完整算法实现，包括有限差分变体（PSD-Probe）和鲁棒小批量设计的随机扩展（PSGD）。
原文摘要 · Abstract (English)
We present a comprehensive theoretical analysis of first-order methods for escaping strict saddle points in smooth non-convex optimization. Our main contribution is a Perturbed Saddle-escape Descent (PSD) algorithm with fully explicit constants and a rigorous separation between gradient-descent and saddle-escape phases. For a function $f:\mathbb{R}^d\to\mathbb{R}$ with $\ell$-Lipschitz gradient and $ρ$-Lipschitz Hessian, we prove that PSD finds an $(ε,\sqrt{ρε})$-approximate second-order stationary point with high probability using at most $O(\ellΔ_f/ε^2)$ gradient evaluations for the descent phase plus $O((\ell/\sqrt{ρε})\log(d/δ))$ evaluations per escape episode, with at most $O(\ellΔ_f/ε^2)$ episodes needed. We validate our theoretical predictions through extensive experiments across both synthetic functions and practical machine learning tasks, confirming the logarithmic dimension dependence and the predicted per-episode function decrease. We also provide complete algorithmic specifications including a finite-difference variant (PSD-Probe) and a stochastic extension (PSGD) with robust mini-batch sizing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。