首个无需调参的加速优化算法，理论性能达最优。
A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate
- 自适应估计局部曲率，无需预先知道光滑性参数。
- 理论复杂度达到O(ε^{-5/3} log(1/ε))，优于现有方法。
- 实测表现超越主流无参算法，可替代共轭梯度法。
我们提出PF-AGD，首个无需调参、确定性且加速的一阶优化算法，用于最小化充分光滑的非凸函数时，实现O(ε^{-5/3} log(1/ε))的预言机复杂度界，这是当前一阶方法在光滑非凸目标下的最优已知结果。不同于以往需先验知晓光滑常数的方法，我们采用自适应回溯机制与基于梯度的重启策略，动态估计局部曲率。该算法兼具理论最优性与实用性，实验表明其性能优于AGD-Until-Guilty（Carmon等，2017）的实用变体及其他无参算法，是共轭梯度法的可行替代方案。
原文摘要 · Abstract (English)
We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve $O(ε^{-5/3}\log(1/ε))$ oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。