# 牛顿法到 XGBoost 的课堂推导

[[MCS/day6/00 学习指南|day6 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day6/阅读核验与疑问|阅读核验与疑问]] · 上一篇：[[MCS/day6/11 Baseline 与模型比较|Baseline 与模型比较]] · 下一篇：[[MCS/day6/13 Hessian 与牛顿方程的求解|Hessian 与牛顿方程的求解]]

> 来源：[[MCS/day6补充8|day6补充8]]。用途：补充。原有推导、追问与解答保留；阅读时请结合本日核验说明。

## 牛顿法、拟牛顿法、Adam 与 XGBoost 二阶泰勒展开：课堂笔记整理

---

### 一、牛顿法的本质：对导数再做一次牛顿求根

我们用切线不断逼近方程的根，这种方法叫牛顿法。我们用牛顿法求了 $\sqrt{2}$，三步就得到了很高的精确度。

切线法可以用来求 $f(x)=0$。今天要求 $f'(x)=0$，因为记住：极小值一定先满足导数为零。

所以，优化里的牛顿法并不是另一套方法，它本质上就是对导数再做一次牛顿求根。

#### 逻辑递进：从“求最小”到“求零点”

1. **Min f → f' = 0：从“求最小”到“求零点”**
   - 当我们想求一个函数 $f(x)$ 的最小值（Min f）时，数学上的一个必要条件是它的导数等于 0，即 $f'(x)=0$。
   - 这一步是降维打击：原本要解决的是一个“优化问题”（找最低点），但通过求导，把它变成了一个“求根问题”（找 $f'(x)=0$ 的点）。

2. **牛顿-拉佛森方法（Newton-Raphson Method）：用来“求零点”的工具**
   - 既然任务变成“求 $f'(x)=0$ 的根”，就需要一个专门求根的算法，这个算法就是牛顿-拉佛森方法（即常说的牛顿法）。

#### 完整逻辑闭环

- **基础工具**：牛顿法利用切线不断逼近，可以用来求方程 $g(x)=0$ 的根。
- **目标转换（优化问题）**：目标是求函数 $f(x)$ 的极小值（Min f）。
- **构造方程**：根据极值定理，极小值点必然满足导数等于 0。所以问题转化为求解方程 $f'(x)=0$。
- **套用工具（优化中的牛顿法）**：把牛顿法用在这个新方程上。

普通牛顿求根公式：

$$
x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)}
$$

现在方程是 $g(x) = f'(x)$，代入得到：

$$
x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}
$$

这个公式，就是优化领域里的“牛顿法”迭代公式（利用一阶导和二阶导，即 Hessian 矩阵）。

**总结**：求根用牛顿-拉佛森方法；求极值先变成求根（$f'=0$），然后再用牛顿-拉佛森方法。优化里的牛顿法并不是另一套方法，它本质上就是对导数再做一次牛顿求根。

---

### 二、海森矩阵：地形的曲率表

中文名叫海森矩阵，我们就叫它“海森”就好了。

你可以把它想象成一张地形的曲率表：这块地往东有多弯、往北有多弯、往南有多弯、往西有多弯；正着走、反着走、斜着走又会怎么样。这就是它给你讲的这张表。

#### 拟牛顿法的历史脉络

- 海森矩阵是 $n \times n$ 的，$n$ 到百万级别时，光存储就不现实，求逆更不可能。
- **1959 年**，Davidon 提出：不需要真的去算海森矩阵，只需要用最近几步梯度的变化去估算曲率就可以了。这就是拟牛顿法最早的源头。
- **1970 年左右**，BFGS 这四个人几乎同时得到了同一类公式。BFGS 就是这四个人名字的首字母，这是一个算法。
- 后来还有 **L-BFGS**。这个算法是用来做近似的。
- **上世纪 80 年代**，Nocedal 做了 L-BFGS。他说矩阵干脆就不要存了，我只记最近 $m$ 次迭代的向量。
- 所以在 scaling 当中，我们做什么？Logistic regression，这叫逻辑回归。

#### Adam 的提出

- 然后我们又讲到了 Adam。Adam 是 **2014 年**提出的，2014 年我们做的是尺度再换一次。
- 在 2014 年的时候，有一个人叫 Kingma（你叫他卡马、K 马都可以，也有人叫他王马或者马王，他是外国人），他和 Welling 一起发表了 Adam 这篇论文。
- 他们发表了 Adam。当参数规模到了千万甚至 billion 级别之后，Adam 解决了这个问题——百万级和十亿级参数下的优化问题。那么连 L-BFGS 它也进行了一个偏重。

**要记住**：如果今天讲课，你只记得牛顿法很快，却忘记了第三种可能，那就好好反思一下为什么会这样。

---

### 三、一阶方法做不好的三件事

我们要知道，为什么会出现这些问题？肯定是有需求，才会出现这些方法。一阶方法有三件事做不好，所以人们才去研究二阶方法。是哪三件事？

1. **学习率（learning rate）**：步长难选。
2. **病态**：在狭长的山谷里面，横着走和顺着走，曲率能差上几十倍甚至几百倍。固定步长下，它就会走出“之字形”——知乎者也的“之”，之字形来来回回弹。这就是海森矩阵条件数很大时的样子。
3. **尺度**：有的变量是像素，有的变量是概率，梯度各分量的量级是不一样的。

所以，精确牛顿法相当于按照曲率重新丈量了这片空间，它是一个 space（空间度量）。因此，它对线性的缩放就没有那么敏感。

#### 为什么牛顿法没有把整个问题都解决掉？

要记住，还是海森矩阵的问题。

- 海森矩阵是 $n \times n$。假设 $n$ 是 100 万，那么双精度存满大概需要 **8 TB** 这样的量级。这里可以记一下，随堂笔记记一下，大概是 8 TB。
- 求逆呢，复杂度是 $O(n^3)$。
- 而在深度神经网络里，参数量动辄是 billion 级别，也就是上亿或十亿级别，根本算不起来。

所以才有了后面的：阻尼修正、拟牛顿，以及我们 2014 年讲的 Adam。

---

### 四、牛顿法公式的推导与理解

#### 一维公式的来源

$$
x_{new} = x - \frac{f'(x)}{f''(x)}
$$

这是不是一维除以二维？它的比值拿 $x$ 去减。这是啥？

这是不是把 $g = f'$ 当成新函数，对 $g(x)$ 做牛顿求根？

**完全正确！** 这张图一针见血地把“优化中的牛顿法”的核心给抓住了。

##### 一维情况

$$
x \leftarrow x - \frac{f'(x)}{f''(x)}
$$

- 分子 $f'(x)$ 是一阶导（梯度）。
- 分母 $f''(x)$ 是二阶导（曲率）。
- 本质是：用一维的梯度除以一维的曲率，也就是一个标量除以标量。

##### 多维情况

$$
x \leftarrow x - H^{-1} \nabla f
$$

- 梯度不再是一个数，而是一个向量（$\nabla f$）。
- 曲率不再是一个数，而是海森矩阵 $H$（一个 $n \times n$ 的矩阵）。
- 在矩阵运算中，“除以一个矩阵”等价于“乘以它的逆矩阵”，所以 $1/f''(x)$ 就变成了 $H^{-1}$。
- 公式变成了：参数更新 = 当前位置 - 海森矩阵的逆 × 梯度。

##### 验证

假设我们要求 $g(x)=0$，其中 $g(x)=f'(x)$（也就是求极值点）。

普通牛顿求根公式是：

$$
x_{new} = x - \frac{g(x)}{g'(x)}
$$

把 $g(x)=f'(x)$ 代入：

- 分子 $g(x)$ 变成了 $f'(x)$（梯度）。
- 分母 $g'(x)$ 变成了 $f''(x)$（二阶导 / 海森矩阵）。

结果完全吻合：一维是 $\frac{f'(x)}{f''(x)}$，多维是 $H^{-1} \nabla f$。

#### 一维牛顿法的完整推导

第一个问题：一维从哪里来？

就是当前的点，我们把它设为 $x_n$。我们用二次多项式来代替 $f$。

那么 $f(x)$ 约等于：

$$
f(x) \approx f(x_n) + f'(x_n)(x - x_n) + \frac{f''(x_n)}{2}(x - x_n)^2
$$

然后我们对 $x$ 进行求导，令导数为零：

$$
f'(x_n) + f''(x_n)(x - x_n) = 0
$$

我们就能得出来：

$$
x = x_n - \frac{f'(x_n)}{f''(x_n)}
$$

这就是一维牛顿法的来源：用二次函数局部近似原函数，然后直接跳到这个二次函数的极值点。

#### 具体例子：$f(x) = (x-3)^2 + 1$

1. **目标函数与导数**
   - 原函数：$f(x) = (x-3)^2 + 1$，这是一个开口向上的抛物线。一眼就能看出，当 $x=3$ 时，函数取得最小值 $1$。
   - 一阶导（梯度）：$f'(x) = 2(x-3)$。令 $f'(x)=0$，得 $x=3$，这就是极值点。
   - 二阶导（曲率）：$f''(x) = 2$，常数 2，说明这条抛物线的曲率是不变的。

2. **牛顿法迭代过程**
   - 初始点：$x_0 = 0$。
   - 套入公式：
     $$
     x_1 = x_0 - \frac{f'(x_0)}{f''(x_0)}
     $$
   - 代入数值：
     $$
     x_1 = 0 - \frac{2(0-3)}{2}
     $$
   - 计算过程：
     $$
     x_1 = 0 - \frac{-6}{2} = 0 + 3 = 3
     $$

**为什么这叫“一步到位”？**

- 本质：牛顿法是在当前点用二次多项式去近似原函数，然后直接跳到这个二次函数的极值点。
- 特例：在这个例子中，原函数 $f(x)$ 本身就是一个二次函数。
- 所以，用二次函数去近似二次函数，近似是绝对完美的。因此，牛顿法不需要像梯度下降那样慢慢迭代，只需要一次（一步）迭代，就精准地找到了全局最优解 $x=3$。

**总结**：这张图就是牛顿法在“二次函数”这个理想场景下的“降维打击”演示。它用最直观的数字，证明了公式 $x = x_n - f'/f''$ 的正确性，也完美展示了它为什么这么快。

---

### 五、二维病态函数：$f(x,y) = x^2 + 10y^2$

这张图 $f(x,y) = x^2 + 10y^2$ 是一个极其经典的二维二次函数（椭圆抛物面），它完美对应了前面笔记里提到的“病态（Ill-conditioning）”和“海森矩阵”的概念。

#### 1. 图像长什么样？（三维几何）

- 这是一个开口向上的“碗”形曲面（抛物面）。
- 它的最低点在原点 $(0,0,0)$。
- **关键特征**：因为 $y^2$ 前面的系数是 10，而 $x^2$ 是 1，这意味着在 $y$ 方向上的曲率（陡峭程度）是在 $x$ 方向上的 10 倍。
- 所以，这个“碗”不是圆的，而是被拉长了的椭圆截面。它在 $x$ 轴方向平缓，在 $y$ 轴方向陡峭。

#### 2. 转换成等高线（二维俯视图）

- 方程是 $x^2 + 10y^2 = c$（$c$ 是常数）。
- 由于 $y$ 方向更陡，为了保持等高，$y$ 的取值范围必须比 $x$ 小得多。所以这些椭圆是扁长的。

#### 3. 为什么这是个“病态”问题？

- **曲率差异**：在 $x$ 方向二阶导 $f_{xx} = 2$；在 $y$ 方向二阶导 $f_{yy} = 20$。曲率差 10 倍。
- **梯度下降的灾难**：如果用普通的梯度下降（固定学习率）来优化它：
  - 为了能在陡峭的 $y$ 方向不震荡，学习率必须设得很小（不能超过 $1/10$）。
  - 但这个学习率放在平缓的 $x$ 方向就太小了，导致 $x$ 方向进展极其缓慢。
  - 所以，梯度下降的路径会在狭长的椭圆山谷里来回横跳（之字形），步子不敢迈大，需要非常非常多次迭代才能慢慢蹭到中心点。

#### 4. 换作“牛顿法”呢？

多维牛顿法公式：

$$
x \leftarrow x - H^{-1} \nabla f
$$

套进这个函数：

- 梯度：
  $$
  \nabla f = \begin{bmatrix} 2x \\ 20y \end{bmatrix}
  $$
- 海森矩阵：
  $$
  H = \begin{bmatrix} 2 & 0 \\ 0 & 20 \end{bmatrix}
  $$
- 海森矩阵的逆：
  $$
  H^{-1} = \begin{bmatrix} 1/2 & 0 \\ 0 & 1/20 \end{bmatrix}
  $$
- 代入公式更新坐标：
  $$
  \begin{bmatrix} x_{new} \\ y_{new} \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} - \begin{bmatrix} 1/2 & 0 \\ 0 & 1/20 \end{bmatrix} \begin{bmatrix} 2x \\ 20y \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} - \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}
  $$

结果一目了然：牛顿法只需要一步，就能直接跳到全局最优点 $(0,0)$！

#### 5.  经典总结

二维病态优化问题中，一阶方法与二阶方法的核心差异，在于对各个方向曲率的感知与适配能力。

一、问题背景

二维病态网指的是优化问题的地形（Loss Landscape）在不同方向上陡峭程度差异巨大。典型例子为 f(x, y) = x^2 + 10 y^2，其等高线呈被捏扁的椭圆，x 方向平缓（曲率 2），y 方向陡峭（曲率 20），两个方向曲率相差 10 倍。

二、二阶方法的行为

牛顿法通过海森矩阵 H 感知各方向曲率：

$H = [[2, 0], [0, 20]]$

其更新方向为 H^-1 * ∇f，其中：

$H^-1 = [[1/2, 0], [0, 1/20]]$

该矩阵的作用是按方向自动缩放步长：

- x 方向（平缓）：步长放大（乘以 1/2）
    
- y 方向（陡峭）：步长缩小（乘以 1/20）
    

因此，无论地形如何扭曲，牛顿法都能自动适配每个方向的曲率，沿直线一步到达最优点。

三、一阶方法的局限

梯度下降法（一阶方法）只有一个全局统一的标量学习率 η，不具备方向感知能力，无法区分 x 方向与 y 方向的差异。

由此产生顾得了东、顾不了西的困境：

- 若为适应 y 方向陡峭曲率而将学习率设得很小（小于 1/10），则 y 方向不再震荡，但 x 方向推进极慢，难以到达终点。
    
- 若为适应 x 方向平缓曲率而将学习率设得很大，则 x 方向推进加快，但 y 方向一步跨过山谷，函数值爆炸，产生震荡发散。
    

四、类比说明

在被拉长的椭圆山谷中：

- 牛顿法类似于能识别路况的驾驶者，陡峭方向上坡时减小油门，平缓方向下行时加大油门，直接抵达终点。
    
- 梯度下降类似于只有单一油门档位的定速巡航，为避免撞墙只能压低整体速度，最终在狭长山谷中反复磨蹭，难以到达终点。
    

五、总结

一句话总结：

病态问题的本质是不同方向曲率差异巨大；一阶方法只有一个全局学习率，无法同时适配所有方向，因此要么收敛过慢，要么震荡发散；二阶方法利用曲率信息，相当于为每个方向配置独立学习率，因此能一步到位。

分层展开：

1. 病态在哪  
    不是梯度大或梯度小的问题，而是不同方向陡峭程度差异过大。地形如同被捏扁的椭圆碗，东西方向平缓，南北方向陡峭。
    
2. 一阶方法为何失效  
    梯度下降只有一个标量学习率 η，全局统一。
    
    - 为避免陡方向发散，只能将 η 压小；
        
    - η 一旦压小，平缓方向推进极慢。  
        因此顾得了东、顾不了西，只能在狭长山谷中来回震荡。
        
3. 二阶方法为何有效  
    牛顿法利用海森矩阵 H 获取各方向曲率，并通过 H^-1 自动缩放步长：
    
    - 陡方向用小步；
        
    - 缓方向用大步。  
        等价于每个方向拥有独立学习率，因此能直指最优点。
        

精炼表述：

病态地形如同一条又窄又长的山谷。  
梯度下降仅有一个定速巡航档位，油门单一：踩大撞墙，踩小磨蹭。  
牛顿法具备自适应悬挂，能识别各方向坡度，陡坡小油门、缓坡大油门，因此直达终点。

---

### 六、实际应用：样本量中等时用什么优化算法？

我们前面不是讲了逻辑回归、广义线性模型吗？那在这个当中，样本量中等的时候，我们的 scaling（尺度化 / 优化算法选择）用什么模型？

结合前面的笔记，如果样本量是中等（比如几千到几万），并且参数量不是特别大（比如特征维度几百到几千），这个时候海森矩阵还能存得下、算得动。所以通常的答案是：

**用牛顿法（或拟牛顿法），比如 BFGS / L-BFGS。**

具体来说：

- **样本量中等、维度中等**：直接用牛顿法（精确海森矩阵）或者 BFGS 来优化逻辑回归/广义线性模型。
- **样本量再大一点、维度高一点**：用 L-BFGS（Limited-memory BFGS），不存完整海森矩阵，只存最近 $m$ 步的梯度变化，内存可控。
- **样本量巨大、参数上亿（深度学习）**：才转向 Adam 这类一阶方法。

#### 核心结论

在逻辑回归（Logistic Regression）和广义线性模型（GLM）中，当样本量中等时，scikit-learn（sklearn）等主流机器学习库最常用的优化求解器是：

- **lbfgs**（拟牛顿法，Limited-memory BFGS）
- **newton-cg**（牛顿-共轭梯度法，Newton-Conjugate Gradient）

#### 为什么是这两个？

1. **为什么不用纯一阶（SGD/Adam）？**
   - 样本量中等、特征维度不是上亿级别时，海森矩阵还能被近似或存储。此时用一阶方法收敛太慢，且对学习率敏感，容易走出“之字形”（顾得了东顾不了西）。

2. **为什么不用精确牛顿法（直接求 $H^{-1}$）？**
   - 直接求逆复杂度 $O(n^3)$。即使样本中等，特征维度几百到几千时，直接求逆依然太慢，且容易遇到非正定海森矩阵（如鞍点）导致崩溃。

3. **为什么是 lbfgs？**
   - L-BFGS 是 80 年代 Nocedal 等人的成果，不存完整海森矩阵，只记最近 $m$ 步的梯度变化来估算曲率。内存极省，且完美继承牛顿法“自动按方向缩放步长”的优点。

4. **为什么是 newton-cg？**
   - 牛顿-共轭梯度法是牛顿法和共轭梯度法（CG）的结合。它不直接求海森矩阵的逆，而是通过迭代解线性方程组（$Hd = -g$）来求牛顿方向。它同样避免了显式存储 $H^{-1}$ 和 $O(n^3)$ 的求逆开销，对于稀疏或大一点的特征矩阵效率极高。

#### 课堂逻辑的闭环

1. **提出理想**：牛顿法（二阶）极快，一步到位。
2. **遇到现实**：海森矩阵 $n \times n$，100 万维就是 8 TB，求逆更不可能。
3. **寻找出路**：引入拟牛顿法（割线法），用梯度差商近似曲率。
4. **工程实践**：lbfgs 和 newton-cg 是这套理论在逻辑回归和广义线性模型里最成功的实际应用。

**一句话总结**：在中小规模逻辑回归/GLM 场景下，L-BFGS 和 Newton-CG 是兼顾了牛顿法“二阶曲率自适应”优势与计算资源可行性的标准工业解法。

---

### 七、牛顿法的每一步都在解线性方程组

那是 10 多位，所以说它每一步其实都在解什么？解线性方程组：

$$
Hd = -g
$$

然后我们就知道：

$$
x_{new} = x + d
$$

可以推导到 $x$。这叫这是什么？这叫高斯消元。这边就是高斯消元了。

#### 对称矩阵与正定性

它是 $d_{ij}$ 或 $d_{ji}$ 项是多少多少，我们叫什么？叫对称矩阵，是不是？对称矩阵。

它关键是什么？三方面：

1. **特征值全正**：这叫正定。
2. **特征值全负**：这叫负定。
3. **有正有负**：这叫不定，对应的是马鞍面，让我们看鞍点。

但是牛顿法的话，它还是不看这些。它是只奔着梯度等于零去做的。这个是牛顿法，它一步到位。

#### 拟牛顿法：用割线代替曲率

然后拟牛顿法，他说不管你真海森，是维护一个对称矩阵 $B$ 去近似它。啊，其实就是什么？割线嘛。

你比如说满足我的割线方程：

$$
Bs = y
$$

那 $s$ 就相当于走的多点（自变量变化量），那 $y$ 就是梯度变了多少（梯度变化量）。意味着拟牛顿法就是说用差商来代替 $f''$，这叫割线法。

---

### 八、XGBoost 最大升级：二阶泰勒展开

XGBoost 最大的升级，就是用了二阶泰勒展开。

所以说，XGBoost 在每一步构建树的时候，同时使用了损失函数的一阶导和二阶导。

明白吗？同时用了 $g$ 和 $h$：一阶导数 $g$，二阶导数 $h$（也就是 Hessian 的对角线元素）。它们有了这样一个公式。

#### 核心公式

$$
L^{(t)} \approx \sum_i \left[ g_i w_i + \frac{1}{2} h_i w_i^2 \right] + \Omega(f_t)
$$

##### 公式逐项拆解

- $L^{(t)}$：第 $t$ 轮迭代时的目标函数（损失函数）。
- $\sum_i$：对每一个样本 $i$ 进行求和。
- $g_i$：损失函数在当前预测值处的一阶导数（梯度）。对应前面笔记的“梯度”。
- $h_i$：损失函数在当前预测值处的二阶导数（海森矩阵的对角线元素）。对应前面笔记的“曲率”。
- $w_i$：当前样本落在的叶子节点的权重（预测值）。这是我们需要去求解的变量。
- $\Omega(f_t)$：正则化项，用来惩罚树的复杂度（比如叶子节点数量和叶子权重的大小），防止过拟合。

#### 为什么是巨大的升级？（对比传统 GBDT）

前面整理的笔记里提到：“一阶方法顾得了东顾不了西”。传统的 GBDT 只用了一阶导数（梯度），相当于用一阶泰勒展开来近似目标函数。

而 XGBoost 使用了二阶泰勒展开，相当于它在每一步构建树的时候，不仅看了“往哪走”（梯度），还看了“地形有多弯”（曲率，即 $h_i$）。

**好处是什么？**

1. **更精准**：二阶近似比一阶近似更贴近真实的损失函数形状。
2. **定步长自动**：看公式里的 $w_i$ 和 $w_i^2$，因为有了二阶项 $\frac{1}{2} h_i w_i^2$，在求解最优 $w_i$ 时，分母会自动带上 $h_i$（即海森对角线）。
   - 这其实就是牛顿法（$x_{new} = x - g/h$）的投影。
   - 这意味着 XGBoost 不需要手动设置很精细的学习率（步长），它通过 $g_i$ 和 $h_i$ 的比值，自动实现了按方向缩放步长（这是前面笔记里讲二阶方法“自动按方向缩放步长”的完美应用）。

#### 关键结论

这个公式清楚地告诉我们：

> XGBoost 在构建每一棵树的时候，本质上是把当前损失函数局部近似成了一个二次函数（抛物线），然后用牛顿法的思想直接去算这棵树的叶子节点权重 $w_i$。

所以，XGBoost 的最大升级不是随便用了二阶展开，而是把前面讲的“拟牛顿/牛顿法”思想，完美地融合进了决策树的构建过程中，实现了精度和效率的双重飞跃。

---

### 九、核心记忆点汇总

- 优化里的牛顿法并不是另一套方法，它本质上就是对导数再做一次牛顿求根。
- 求根用牛顿-拉佛森方法；求极值先变成求根（$f'=0$），然后再用牛顿-拉佛森方法。
- 海森矩阵可以想象成地形的曲率表：往东、往北、往南、往西有多弯。
- 拟牛顿法最早源头：1959 年 Davidon 提出用最近几步梯度的变化估算曲率。
- BFGS：1970 年左右四个人几乎同时得到同一类公式，名字首字母组成 BFGS。
- L-BFGS：80 年代 Nocedal 提出，不存完整海森矩阵，只记最近 $m$ 次迭代的向量。
- Adam：2014 年 Kingma 和 Welling 发表，解决千万甚至 billion 级参数的优化问题。
- 一阶方法做不好的三件事：学习率、病态、尺度。
- 海森矩阵 $n \times n$，100 万维双精度存储约 8 TB，求逆复杂度 $O(n^3)$。
- 牛顿法每一步都在解线性方程组 $Hd = -g$，本质上是高斯消元。
- 对称矩阵正定性：特征值全正 → 正定；全负 → 负定；有正有负 → 不定（马鞍面）。
- 拟牛顿法用割线方程 $Bs = y$ 近似海森矩阵，用差商代替 $f''$。
- 中小规模逻辑回归/GLM：用 L-BFGS 或 Newton-CG。
- XGBoost 最大升级：二阶泰勒展开，同时使用一阶导 $g$ 和二阶导 $h$。
- XGBoost 核心公式：$L^{(t)} \approx \sum_i \left[ g_i w_i + \frac{1}{2} h_i w_i^2 \right] + \Omega(f_t)$。
- XGBoost 本质：把当前损失函数局部近似成二次函数，用牛顿法思想算叶子节点权重。