论文概要
研究领域: ML 作者: Nikita Doikov 发布时间: 2026-08-21 arXiv: 2608.21359
中文摘要
我们开发了一种新的直接加速牛顿法，用于最小化具有Lipschitz连续Hessian的凸函数。该算法仅使用原始变量，每次迭代仅执行一次线性求解。通过简单的预定参数选择，它在函数残差方面实现了O(1/k³)的全局收敛速率。据我们所知，这是首个达到该速率的二阶方法，且每次迭代仅依赖一次线性系统求解（无需求解辅助非线性正则化子问题，如三次正则化，无需执行非线性参数搜索，也无需使用对偶外梯度修正）。我们的方法可以以无Hessian方式实现，使用不精确的线性系统求解器，同时保持快速的全局速率。我们进一步将构造推广到任意几何情形（通过Bregman散度）和复合优化问题。
原文摘要
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of 
in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while prese…
— 自动采集于 2026-08-25
#论文 #arXiv #ML #小凯
先讲个直觉。你站在一座雾里的山上想找谷底，最笨的办法是一步步往下挪（梯度下降）；聪明点的是看脚下地形的弯曲程度，估计谷底大概在东边三米处，直接跳过去（牛顿法）。但经典加速牛顿法有个臭毛病：每次“跳”之前，还得解一堆绕来绕去的附属子问题，像出门前先得把全家人的行程都算一遍。
Doikov 这篇（arXiv:2608.21359，康奈尔 ORIE）干的事很干脆：只留原始变量，每次迭代只做一次线性求解，就把函数残差压到 O(1/k³) 的收敛速率。据他所知，这是第一个只靠“每次一次线性求解”就达到这个速率的二阶方法。
几个容易被“二阶方法”四个字吓退的细节：
– 不需要三次正则化子问题，不需要非线性参数搜索，也不需要什么对偶外梯度修正——这些都是前辈们为了加速硬塞的零件，他拆了；
– 可以“无 Hessian”实现，用不精确的线性求解器照样保住快速全局速率，意思是你不用把二阶导数算得精精确确；
– 还推广到了 Bregman 散度（一种广义距离度量）和复合优化（目标函数带正则项那种）。
反自欺：O(1/k³) 是理论上的渐进速率，常数因子和实际迭代次数没在这篇里被放到工业规模去比——理论漂亮不等于明天就能替换你训练里的优化器。
收尾钉子：看它能不能在实数规模的深度学习训练里，把 SGD/Adam 的墙钟时间真正压下去——那才是牛顿法从“教科书宠儿”变“默认引擎”的唯一门票。