站内快照 · 国内可打开。外网原文可能无法访问。
- 论文公开站arXiv
牛顿法的原始加速方法
Primal Acceleration of Newton's Method
我们开发了一种新的直接加速牛顿法，用于最小化具有Lipschitz连续Hessian的凸函数。该算法仅使用原始变量，每次迭代只需一次线性求解。通过简单的预定参数选择，它在函数残差方面达到O(1/k^3)的全局收敛率。据我们所知，这是此类问题中第一种在每次迭代仅依赖一次线性系统求解（无需求解辅助非线性正则化子问题，如三次正则化，执行非线性参数搜索或使用对偶外梯度校正）就达到此速率的一阶方法。我们的方法可以以无Hessian方式实现，使用非精确线性系统求解器，同时保持快速全局速率。我们进一步将我们的构造扩展到任意几何通过Bregman散度，以及复合优化问题。
意义：该算法在保持二阶方法快速收敛的同时，大幅降低了计算成本，为大规模凸优化提供了新选择，可能推动机器学习中相关问题的求解效率。