数学2021arxiv.org
具有全局 O(1/k^2) 收敛性的正则化牛顿法
Regularized Newton Method with Global $O(1/k^2)$ Convergence
进阶 · 约 60 分钟读完前置知识：牛顿法、凸优化基础、Levenberg–Marquardt 正则化
导读
这篇论文提出一种正则化牛顿法，通过将三次正则化思想与自适应 Levenberg–Marquardt 惩罚相结合，在仅假设 Hessian Lipschitz 连续的条件下，对任意凸目标函数从任意初始点出发都能获得全局 O(1/k²) 的收敛速度。核心做法是对 Hessian 进行与梯度范数相关的阻尼正则化，实现简单且优雅。
HN 关注点：教科书上牛顿法的快速收敛依赖强凸等额外假设，而该方法在更弱的假设下仍达到与强凸函数上梯度下降相当的 O(1/k²) 速率，且实现极其简单，让人懊悔没想到。
HN 评论精选
这几条评论里：支持 3 补充 1
补充解释 O(1/k²) 看似慢，实则在更弱假设（仅 Lipschitz Hessian）下成立，阻尼 Hessian 思想由来已久
熟悉牛顿法的人可能会对收敛速率感到意外：1/k² 比教科书上带线搜索的牛顿法的二阶收敛速率（2^{-2^k}，常数步内收敛）慢得多，甚至不比强凸函数上的普通梯度下降快。那为什么要用这么复杂的更新？因为教科书上的快速收敛证明需要对目标函数做额外假设，比如强凸或自和谐（self-concordant），而这篇论文只假设 Hessian Lipschitz 连续。阻尼 Hessian 的想法其实很老（有时叫阻尼牛顿法、信赖域牛顿法或 Levenberg-Marquardt，后两者更具体），这篇论文提供了一种决定阻尼程度的视角。
rahimiali查看英文原文
People who're familiar with Newton's method might be surprised at the convergence rate. 1/k^2 is slower than the textbook rate for Newton's method with line search, which is 2^ {-2^k}, basically implying convergence in a constant number of steps. The rate in this paper seems to be no faster than plain gradient descent on a strongly convex function! So why go through the trouble of the much more complicated update? Because the textbook proof of the fast convergence of Newton's method make additional assumptions on the objective function, for example that it is strongly convex, or it is self concordant. This paper only assumes Lipschitz continuous Hessians. The idea of dampening the Hessian is old (it's sometimes called "damped newton method", or "trust region newton method", or "levenberg-marquardt", though the latter two refer to more specific ideas). This paper offers a view to how much dampening to apply.
支持赞其创新点简单优雅（按梯度范数缩放正则项），是梯度下降与牛顿法的天然折中
很有意思。创新点似乎是在 L-M 步长公式中把单位矩阵按梯度范数的平方根缩放，非常简单优雅、极易实现，很多人会懊悔为什么没想到。动机也很好懂，作者在第二页中部之前就完全解释清楚了：他把一个收敛快但步长难算的著名方法，改造成可以廉价近似这些步长、同时保留大部分收敛优势的方法。这对大规模优化问题可能有重要意义，因为正则化牛顿步在理论和实践上都是梯度下降与完整牛顿法之间的天然折中。
civilized查看英文原文
This is very interesting. It looks like the innovation is to scale the identity matrix in the L-M step formula by the square root of the norm of the gradient. Very simple and elegant, and trivial to implement. Lots of people are going to be shaking their heads wondering why they didn't think of this first. The motivation for the idea is very nice and easy to understand. The author completely explains it before the middle of the second page. I encourage you to look at it if you know enough vector calc to make sense of the notation. Essentially, he takes a well-known fast-converging method whose steps are hard to compute and shows how these steps can be approximated cheaply while still retaining much of the convergence rate benefit. This may have implications for many large-scale optimization problems as L-M regularized Newton steps are a sort of natural halfway house between gradient descent and the full Newton's method, both theoretically and practically.
支持期待该算法被收录进 scipy.optimize
我就等几个月后这个算法出现在 scipy.optimize 里。
nitred查看英文原文
I'll just wait for a few months for this algorithm to show up in `scipy.optimize` [1] [1] https://docs.scipy.org/doc/scipy/reference/optimize.html#
支持感叹论文开篇成果表述的分量
「我们提出一种牛顿型方法，能从任意初始化、对具有 Lipschitz Hessian 的任意凸目标函数快速收敛。」光是读到第一句话就觉得自己很渺小。
marcodiego查看英文原文
> We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cubic regularization with a certain adaptive Levenberg--Marquardt penalty. I feel insignificant just by reading the first phrase.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2021Hacker News 讨论帖235 分 · 103 评
同领域还值得读
一种新的相关系数
A New Coefficient of Correlation
提出了一种新的相关性系数（由 Sourav Chatterjee 提出），能够检测变量之间任意形式（不限于线性）的相关关系，且计算简单高效，主要基于排序和距离计算。
数学2021 · 682 分 · 158 评 · 引用 1进阶 · 约 60 分钟编辑精选数学的两种文化
The Two Cultures of Mathematics (2000)
这是数学家 Timothy Gowers 于 2000 年发表的一篇随笔，他把数学研究大致分成两种文化：一类是“解题者”，热衷于攻克具体难题、发展技巧（如组合数学）；另一类是“理…
数学2009 · 307 分 · 102 评入门 · 约 35 分钟编辑精选重新定义统计显著性
Redefine statistical significance
提议将统计显著性阈值从常用的 p<0.05 收紧到 p<0.005，以降低假阳性率、缓解可重复性危机。
数学2017 · 303 分 · 114 评入门 · 约 45 分钟编辑精选统计建模：两种文化（2001）
Statistical Modeling: The Two Cultures (2001)
讨论统计学中两种建模文化：一种假设数据由某种随机模型生成，侧重推断与系数解释；另一种把数据生成机制视为未知，侧重预测精度，主张使用算法建模。
数学2015 · 254 分 · 36 评进阶 · 约 60 分钟编辑精选通信的数学理论 (1948)
A Mathematical Theory of Communication (1948)
这是香农 1948 年的经典论文《通信的数学理论》，奠定了信息论的基础。
数学2016 · 169 分 · 53 评入门 · 约 90 分钟编辑精选