Ch24 数值分析与凸优化补遗 · 复习大纲¶
目标: 60 分钟复习数值分析与凸优化核心 受众: 算法工程师 / ML 工程师 / 面试候选人
一、知识地图(7 大模块)¶
§01 浮点与数值稳定性¶
- IEEE 754: FP32 (1+8+23) / FP16 (1+5+10) / BF16 (1+8+7) / FP8 / FP4 / 1.58-bit
- Machine Epsilon: FP32 = 1.19e-7, FP16 = 9.77e-4, BF16 = 7.81e-3
- 误差类型: 舍入 / 截断 / Catastrophic Cancellation
- 算法: Kahan 求和 / Softmax 减 max / BatchNorm / Loss Scaling
§02 迭代法与稀疏线代¶
- 矩阵分解: LU / QR / SVD / Cholesky
- 迭代法: CG / GMRES / BiCGSTAB
- 稀疏存储: CSR / COO / ELL / Block Sparse
- 预条件子: Jacobi / ILU / AMG
§03 凸集与凸函数¶
- 凸集: 定义 / 凸包 / 凸锥 / 仿射集
- 凸函数: 一阶条件 / Hessian 半正定 / 强凸 / 平滑
- Lipschitz 梯度: ||∇f(x) - ∇f(y)|| ≤ L||x-y||
- 共轭: f*(y) = sup_x {yᵀx - f(x)}
§04 对偶与 KKT¶
- Lagrange: L(x,λ,ν) = f(x) + λg(x) + νh(x)
- 弱对偶: g ≤ f(x*)
- 强对偶: Slater 条件 + 凸
- KKT 4 条件: Stationarity / Primal Feasibility / Dual Feasibility / Complementary Slackness
§05 二阶方法¶
- Newton: 二次收敛, O(n³)
- BFGS: 秩 2 修正, 超线性
- L-BFGS: O(mn) 内存
- Trust Region: 比 Line Search 稳健
- K-FAC / Shampoo: 实用化二阶, 训练加速 2-3×
§06 约束优化¶
- Interior Point: Barrier Method
- 投影梯度: 简单约束
- Frank-Wolfe: 凸包优化
- SQP: 强约束
- ADMM: 分布式
§07 分布式与随机优化¶
- 同步 SGD: AllReduce (Ring, NCCL)
- 异步 SGD / Hogwild!: 无锁
- Parameter Server: 超大规模
- FedAvg: 联邦学习
- EA-SGD: 弹性平均 + 拜占庭鲁棒
二、重点公式¶
IEEE 754 FP32¶
\[x = (-1)^s \times 2^{e-127} \times (1.m)\]
Kahan 求和¶
\[y = a - c; \quad t = b + y; \quad c = (t - b) - y; \quad \text{sum} = t\]
Softmax 减 max(数值稳定)¶
\[\text{softmax}(x_i) = \frac{e^{x_i - \max x}}{\sum_j e^{x_j - \max x}}\]
凸函数 Hessian 判别¶
\[\nabla^2 f(x) \succeq 0, \quad \forall x\]
强凸 + 平滑 → 线性收敛¶
\[\frac{L}{\mu} = \kappa \text{(条件数)}\]
KKT Stationarity¶
\[\nabla f(x^*) + \sum \lambda_i \nabla g_i(x^*) + \sum \nu_j \nabla h_j(x^*) = 0\]
L-BFGS 更新¶
\[s_k = x_{k+1} - x_k; \quad y_k = \nabla f_{k+1} - \nabla f_k; \quad \rho_k = \frac{1}{y_k^T s_k}\]
AllReduce Ring¶
\[T_{\text{Ring}} = 2(N-1) \times \frac{M}{N}\]
三、必会题(15 题)¶
- FP32 vs BF16 vs FP16 核心区别?
- Catastrophic Cancellation 何时发生?
- 凸集的定义?3 个反例?
- 强凸 + 平滑 → 线性收敛?
- KKT 4 条件具体内容?
- Newton 与 BFGS 区别?
- L-BFGS 内存复杂度?
- Interior Point 何时优于 SQP?
- ADMM 适用场景?
- Ring AllReduce 复杂度?
- Hogwild! 何时有效?
- FedAvg 与同步 SGD 区别?
- CSR 内存公式?
- K-FAC 为何实用?
- 机器精度 Epsilon?
四、5 道深入题¶
- 设计一个数值稳定的 Cross Entropy 实现?(含 Softmax)
- Newton 法在 LLM 训练中如何近似?(K-FAC/Shampoo)
- KKT 在 SVM 中如何推导?(完整推导)
- 分布式训练通信优化策略?(梯度压缩/AllReduce/PS)
- 凸优化 vs 非凸优化在大模型训练中的对比?
五、实践作业¶
- 实现 Kahan 求和,对比朴素求和的精度
- 实现 Softmax 减 max,验证数值稳定
- 实现 L-BFGS 优化 Rosenbrock 函数
- 实现 Ring AllReduce 模拟
- 阅读 K-FAC/Shampoo 论文, 总结核心思想
六、参考资源¶
- Boyd & Vandenberghe《Convex Optimization》
- Nocedal & Wright《Numerical Optimization》
- DeepSpeed ZeRO 论文
- FedAvg (McMahan et al. 2017)
- Shampoo (Anil et al. 2020)
- K-FAC (Martens & Grosse 2015)
七、自检清单¶
- [ ] 能列出 4 种浮点格式差异
- [ ] 能写出 4 种 Catastrophic Cancellation 案例
- [ ] 能背诵 KKT 4 条件
- [ ] 能区分 BFGS / L-BFGS / Newton
- [ ] 能写出 Ring AllReduce 公式
- [ ] 能解释 Interior Point 原理
- [ ] 能描述 ADMM 3 个变量更新