第24章 · 数值分析与凸优化补遗 · 闪卡¶
一 · 浮点与稳定性 (8 张)¶
Q1: IEEE 754 单精度 (FP32) 组成? A1: 1 位符号 + 8 位指数 + 23 位尾数, 总 32 位, 范围 ±3.4×10³⁸, 精度 ~7 位有效数字。
Q2: bfloat16 与 FP16 区别? A2: 都是 16 位。FP16: 1+5+10 (指数少, 范围小); bfloat16: 1+8+7 (指数多, 范围同 FP32)。bf16 是 Google 专为 ML 设计。
Q3: Machine Epsilon 是什么? A3: 1.0 + ε ≠ 1.0 的最小 ε。FP32 = 1.19e-7, FP16 = 9.77e-4, bf16 = 7.81e-3。
Q4: 条件数 (Condition Number) 是什么? A4: κ(A) = ||A|| × ||A⁻¹||。κ 大 → 病态 → 数值不稳定。SVD 时 κ = σ_max / σ_min。
Q5: 什么是 Catastrophic Cancellation? A5: 两个相近大数相减, 损失精度。例: x=1.000001, y=1.000000, x-y 应=1e-6 但 FP32 只有 7 位有效。
Q6: Kahan 求和如何减少误差? A6: 跟踪每步舍入误差, 加到下次累加。复杂度 O(n) 但误差从 O(nε) 降到 O(ε)。
Q7: Softmax 的数值稳定性技巧? A7: 减去 max(x), 避免 exp 溢出。softmax(x)_i = exp(x_i - max(x)) / Σ exp(x_j - max(x))。
Q8: BatchNorm 如何帮数值稳定? A8: 归一化到均值 0 方差 1, 让梯度不会爆炸 / 消失, 是训练深度网络的基础。
二 · 凸集凸函数 (8 张)¶
Q9: 凸集定义? A9: ∀x, y ∈ C, ∀θ ∈ [0,1], θx + (1-θ)y ∈ C。直观: 连接集合内两点的线段在集合内。
Q10: 凸函数判别 (一阶条件)? A10: f(y) ≥ f(x) + ∇f(x)ᵀ(y-x), ∀x, y。几何: 切线在函数下方。
Q11: 凸函数判别 (二阶条件)? A11: Hessian 半正定 ∀x: ∇²f(x) ⪰ 0。这是充要条件。
Q12: 强凸函数定义? A12: f(y) ≥ f(x) + ∇f(x)ᵀ(y-x) + (μ/2)||y-x||², μ>0。强凸保证唯一全局最优。
Q13: Lipschitz 梯度 (L-smooth) 定义? A13: ||∇f(x) - ∇f(y)|| ≤ L||x-y||。保证梯度不会跳变太大, 是 SGD 收敛的基础。
Q14: 共轭函数 (Conjugate) 是什么? A14: f*(y) = sup_x {yᵀx - f(x)}。是凸分析的"对偶", 用于推导对偶问题。
Q15: 什么是 Moreau 包络? A15: M_λf(x) = min_z {f(z) + (1/2λ)||z-x||²}, 凸函数的"光滑化"。
Q16: 凸包 (Convex Hull) 是什么? A16: 包含集合 S 的最小凸集, 等于 S 中所有凸组合的集合。
三 · 对偶与 KKT (8 张)¶
Q17: Lagrange 函数定义? A17: L(x, λ, ν) = f(x) + Σλᵢgᵢ(x) + Σνⱼhⱼ(x), gᵢ≤0 不等约束, hⱼ=0 等约束。
Q18: 对偶函数 g(λ, ν)? A18: g(λ, ν) = inf_x L(x, λ, ν)。弱对偶: g(λ, ν) ≤ f(x*)。
Q19: Slater 条件? A19: ∃x strictly feasible: gᵢ(x) < 0 ∀i。Slater 成立 → 强对偶: g(λ, ν) = f(x*)。
Q20: KKT 4 个条件? A20: ① Stationarity: ∇f + Σλᵢ∇gᵢ + Σνⱼ∇hⱼ = 0; ② Primal feasibility; ③ Dual feasibility λ≥0; ④ Complementary slackness λᵢgᵢ=0。
Q21: SVM 的对偶推导关键? A21: 拉格朗日 → KKT → w = Σλᵢyᵢxᵢ → 只依赖支持向量 (λ>0) → Kernel Trick。
Q22: 互补松弛的意义? A22: λᵢgᵢ(x*)=0, 约束不起作用时 λᵢ=0; 约束起作用 (gᵢ=0) 时 λᵢ>0。"互补"。
Q23: 什么是鞍点? A23: (x, λ) 是 L 的鞍点: L(x, λ) ≤ L(x, λ) ≤ L(x, λ)。强对偶时 (x, λ) 即鞍点。
Q24: KKT 与 SVM 的"支持向量"? A24: SVM 中 λᵢ>0 对应支持向量 (在 margin 上); λᵢ=0 对应非支持向量 (在 margin 外)。
四 · 二阶方法 (8 张)¶
Q25: Newton 法的迭代公式? A25: x_{k+1} = x_k - [∇²f(x_k)]⁻¹ ∇f(x_k)。收敛速度: 二次收敛 (局部)。
Q26: Newton 法 vs 梯度下降? A26: 梯度下降只用一阶, O(1/k) 收敛; Newton 用二阶, O(1/k²) 但每步要算 Hessian 逆, O(n³)。
Q27: BFGS 是什么? A27: Quasi-Newton, 用秩 2 修正近似 Hessian 逆, 避免显式计算 Hessian。O(n²) 每步。
Q28: L-BFGS 的改进? A28: Limited-memory BFGS, 只保留最近 m 个 (s, y) 对, O(mn) 内存, 适合大模型。
Q29: Trust Region 方法? A29: 在 x_k 附近"信赖区域"内求 min, 区域大小根据实际下降 vs 预测下降调整。比 Line Search 更稳健。
Q30: 自然梯度 (Natural Gradient)? A30: 用 Fisher 信息矩阵 F 替代 Hessian, θ_{k+1} = θ_k - α F⁻¹ ∇L。考虑参数化不变性, RL 常用。
Q31: K-FAC 是什么? A31: Kronecker-Factored Approximate Curvature, 近似 Fisher 矩阵为 A ⊗ G 形式, 实用化的二阶方法, 用于大型 NN 训练。
Q32: Shampoo 是什么? A32: Google 2024 的二阶方法, 用左右特征向量 preconditioner, 在 Transformer 训练上比 Adam 加速 2-3×。
五 · 分布式优化 (8 张)¶
Q33: 同步 SGD vs 异步 SGD? A33: 同步: 等所有 worker 算完梯度再更新 (稳定但慢); 异步: worker 独立更新 (快但有 staleness)。
Q34: Hogwild! 是什么? A34: 无锁异步 SGD, 多 worker 直接读写共享参数。稀疏梯度时收敛, 密集梯度会发散。
Q35: AllReduce 是什么? A35: 集合通信原语, N 个 worker 求和后广播给所有人。NCCL / Gloo 实现, 主流分布式训练基础。
Q36: Ring AllReduce 原理? A36: N 个 worker 排成环, 每个发送 chunk 给下一个, N-1 步完成 reduce。带宽最优 O(N), 延迟 O(N-1)。
Q37: Parameter Server 架构? A37: Server 存参数, Worker 拉取 + 推送梯度。适合超大规模但 Server 是瓶颈。
Q38: FedAvg (联邦学习) 流程? A38: ① 中心服务器发模型; ② 各客户端本地训练; ③ 上传模型 (不是梯度); ④ 中心加权平均。
Q39: 什么是 ZeRO (Zero Redundancy Optimizer)? A39: DeepSpeed 的内存优化, 3 阶段: ① 优化器状态分片; ② 梯度分片; ③ 参数分片。单卡可训 1T 模型。
Q40: DDP vs FSDP? A40: DDP 每 worker 完整副本 + AllReduce 梯度; FSDP 把模型/优化器/梯度都分片。FSDP 内存更省但通信更多。