# Day 7｜优化进阶：从收敛速度到 XGBoost

选优化算法，既要看每一步获得多少信息，也要看这些信息需要多少计算。牛顿法、拟牛顿法和 Adam，是不同资源约束下的取舍。

## 一、先分清三种“阶”

### 1. 导数阶数、收敛阶与复杂度

二阶导数描述曲率；二阶收敛描述误差衰减关系；$O(n^3)$ 描述计算规模增长。三者回答不同问题，不能把“使用二阶信息”直接等同于“处处二阶收敛”。

### 2. 大 O 与小 o

$f=O(g)$ 表示在指定极限附近存在常数 C，使 $|f|\le C|g|$；$f=o(g)$ 表示 $f/g\to0$。

例如 $h\to0$ 时，$h^3=o(h^2)$；$O(h^2)$ 只是上界，不保证恰好同阶。写余项或复杂度时必须明确变量趋向哪里。

### 3. 线性收敛与二阶收敛

误差满足 $|e_{t+1}|\approx q|e_t|$（$0<q<1$）时是典型线性收敛；满足 $|e_{t+1}|\approx C|e_t|^2$ 时是典型二阶收敛。

牛顿法的快速收敛通常是局部结论，不能忽略初值、光滑性与非退化条件。

## 二、牛顿法：信息丰富，但代价较高

多维牛顿步求解 $Hd=-g$。Hessian 正定时，它能利用曲率修正不同方向的尺度，缓解狭长谷地中的低效迭代。

但稠密 Hessian 的存储随参数量平方增长；非凸问题还可能出现不定或奇异 Hessian。因此需要考虑线搜索、信赖域和近似方法。

## 三、拟牛顿法：从历史变化估计曲率

### 1. 割线条件与 BFGS

设 $s_t=x_{t+1}-x_t$、$y_t=g_{t+1}-g_t$，拟牛顿法希望曲率近似 B 满足：

$$
B_{t+1}s_t=y_t.
$$

BFGS 根据新观测修正矩阵；在初始正定和 $s_t^Ty_t>0$ 等条件下，可保持正定近似。它利用梯度差获取曲率信息，不必每次显式计算 Hessian。

### 2. L-BFGS：只保留有限历史

L-BFGS 不保存完整稠密矩阵，而是保留最近 m 对向量，典型存储规模为 $O(mn)$。它常用于光滑、梯度较稳定的优化问题；是否优于一阶方法取决于问题与计算预算。

## 四、Adam：动量与自适应步长

### 1. 两种滑动平均

$$
m_t=\beta_1m_{t-1}+(1-\beta_1)g_t,
$$

$$
v_t=\beta_2v_{t-1}+(1-\beta_2)g_t\odot g_t.
$$

m 平滑梯度方向，v 记录梯度平方的平均尺度。这里的二阶矩不是 Hessian，Adam 仍使用一阶梯度信息。

### 2. 偏差修正与参数更新

从零初始化时，早期滑动平均偏向零，因而使用 $\hat m_t=m_t/(1-\beta_1^t)$、$\hat v_t=v_t/(1-\beta_2^t)$，再逐元素更新：

$$
\theta_{t+1}=\theta_t-\eta\frac{\hat m_t}{\sqrt{\hat v_t}+\epsilon}.
$$

Adam 的状态存储随参数数目线性增长，适合大规模随机梯度训练，但仍需选择学习率等超参数，也没有普遍的二阶收敛保证。

## 五、XGBoost：让树模型使用二阶近似

### 1. 梯度提升：逐轮增加模型

加法模型写成 $F_t=F_{t-1}+f_t$。新一轮根据当前预测的损失信息学习新树，再加入整体模型；平方损失时可直观理解为拟合残差。

### 2. 二阶目标与正则化

忽略与新树无关的常数，目标近似为：

$$
\widetilde L^{(t)}=\sum_i\left[g_i f_t(x_i)+\frac12h_i f_t(x_i)^2\right]+\Omega(f_t).
$$

$g_i$、$h_i$ 是损失对当前预测的一阶、二阶导数；$\Omega$ 惩罚树的复杂度。它将泰勒展开用于选择分裂和叶子输出，是二阶信息的工程应用。

### 3. 工程实现与使用场景

分箱或排序减少候选分裂的搜索成本；学习缺失值的默认方向处理部分缺失情况；特征搜索等工作可以并行。逐轮提升仍依赖前轮预测，并不意味着所有树可以独立同时训练。

XGBoost 常用于结构化表格数据。LightGBM 同属梯度提升树体系，采用直方图和按叶生长等设计；不能无条件断言某一种实现总是更快或更准。

## 六、怎样公平地比较算法？

先建立 Baseline，固定训练、验证与测试划分，再比较效果、时间和内存。超参数在验证集上选择，测试集用于最终评估；时间序列任务还要避免未来信息泄漏。

**收敛速度、单步成本、随机梯度噪声、曲率结构和泛化表现，都应进入选择依据。**