5. Optimization（优化） | 内容聚合讲解（逻辑增强版）

这讲不是把优化当作孤立的数学主题。课程名指向 big data，章节名是 Optimization，因此后面所有算法都会同时接受两个标准：目标函数是否下降，以及数据规模、处理器和通信是否允许这样算。

P001 的作者与学期信息保留了来源边界。P002 则把 Optimization 放在中心，三条分支不是并列术语表，而是后续页面的真实顺序。

Small data 部分先从回归、平方误差和普通梯度下降建立更新规则。Big data 部分加入 PRAM、DAG、work、depth，再比较 batch、SGD 与 Hogwild!。Applications 部分把前面的结论带入 Spark，并连接 PCA 与线性规划。

读图时应关注分支颜色：P002 高亮 Small data，P010 改为 Big data，P024 再改为 Applications。这个视觉变化就是模块切换标记。

全讲反复改变的是计算粒度：先对一个残差定义损失，再对全部样本求和；随后把总梯度拆到处理器；最后在共享内存或集群中决定同步方式。每次“扩展”都不会改变优化目标，却会改变单步成本与系统瓶颈。

回归先区分因变量与自变量。以 P004 为例，Protein 是输入，Sugar 是响应；模型接收横坐标并给出蓝线上的预测。linear、logistic 和 polynomial 的形式不同，但给定参数后，每个样本都会产生一个预测和一个误差。

P003 用 sum of squares 评价整组预测：把每个样本的残差平方后相加。参数学习随之变成明确的最小化任务，目标是让所有样本的总误差尽量小。

红点是观测，蓝线是预测，黑色竖线是在固定 Protein 值下沿 Sugar 轴量出的预测误差。红点在线上方时残差为正，在线下方时为负；平方后两类误差都贡献正值。图中较长的黑线在平方和里权重更大，所以拟合会优先压低大的偏差。

横纵轴都以克为单位，残差沿 Sugar 方向测量。这幅图用来固定误差的定义：同一 Protein 值下，比较观测 Sugar 与蓝线预测 Sugar 的差。

P005 把依赖输入 x 的函数 f 叫作 objective function 或 criterion；做最小化时又常叫 cost、loss 或 error function。这些词在本讲里承担同一角色：用一个标量判断当前参数好坏，梯度下降负责把它压低。

在残差均值已控制、样本数固定的回归设置中，平方和与残差方差只差比例因子或自由度修正，因此课件把最小化平方误差和写成最小化方差。

从一张拟合图可写出优化任务：选择模型参数，计算每个样本的预测残差，平方并求和，再寻找总和最小的位置。P007 给出寻找最小值的梯度下降机制，P015 再把同一个目标写成向量形式并拆成可并行的逐样本项。

芯片布线关心几何交叉，排课关心离散冲突，旅行商关心排列与路径长度。三者都能写成最小化，却有不同的变量、约束和邻域操作；同一个搜索策略不会在三类结构上自动保持优势。

课件的结论是：没有对所有搜索问题都最好的方法。后面的 batch、SGD、Hogwild! 也应按这个标准阅读。比较对象不是一个脱离环境的“最快算法”，而是问题曲率、数据稀疏性、目标误差、内存与通信共同决定的合适方案。

对 X=(x_1,\ldots,x_n) 而言，梯度收集各坐标偏导，指向函数增长最快方向。最小化使用负梯度，标准一步写作 X_{k+1}=X_k-\alpha\nabla f(X_k)。课件说“选择方向并继续向下”，P008 的数值更新明确了这里实际减去梯度。

梯度为零只是驻点条件。P007 加入凸性不等式，是为了排除局部低谷：凸函数任意两点之间的函数值不超过端点线性插值，因而不存在比当前局部谷底更低的隐藏区域。若进一步强凸，最小值唯一，后文还可给出误差收敛率。

目标函数 f(X)=0.5x_1^2+0.2x_2^2+0.6x_3^2 的三个偏导分别是 x_1、0.4x_2、1.2x_3。在 X_0=(-2,2,-2) 处，梯度是 (-2,0.8,-2.4)。课件把它称为最陡下坡方向，但数值更新使用的是减去该向量；严格说，梯度本身是最陡上升方向，负梯度才是下坡方向。

步长为 1 时，X_1=X_0-\nabla f(X_0)：第一坐标变成 0，第二坐标从 2 降为 1.2，第三坐标从 -2 跳到 0.4。三个方向的曲率不同，所以收缩速度不同；到 X_6 时第三坐标约为 0.0000256，第二坐标仍约为 0.0569。

沿某个坐标看，步长过小会让每次变化很少；步长过大则可能从谷底一侧跳到另一侧，甚至发散。这个例子中第三坐标系数最大，梯度对同样坐标值反应更强，固定步长最容易在高曲率方向发生过冲。

因此步长不是与问题无关的常数。P014 后面给出在 L‑Lipschitz 梯度条件下取 α<1/L 的理论界，用曲率上界限制稳定步长。

P008 最后用 Taylor expansion 引出 Hessian。梯度只告诉当前斜率，Hessian 还描述各方向曲率；用曲率校正更新可把不同尺度的坐标统一起来，并允许课件所说的步长 1。代价是构造并求解二阶系统，直接求逆复杂度记为 O(n^3)，当模型维数很大时未必划算。

这正呼应 U03：一阶法每步便宜但可能多走很多步，二阶法每步昂贵却可能更快靠近最小值。算法选择取决于维数、曲率和可用计算资源。

Batch 使用全数据，一步慢但方向稳定，达到目标误差所需迭代少；SGD 一步只看随机样本，一步快却需要更多迭代。课件左右栏的“slow but fast to converge”和“fast but slow to converge”必须按这两个时间尺度理解。

课件把 batch 描述为最优、SGD 描述为足够好，并认为随机性有助于逃离局部最小值。对前面给定的强凸问题，局部最小值并非核心困难；这组话更像面向一般非凸优化的直觉。P019 会把可比较部分收敛到 work、depth 与 ε。

P010 高亮 Big data，意味着问题从“更新公式怎么写”转向“哪些操作能同时做”。P011 把每条指令画成 DAG 节点；若 u 依赖 v，则必须等 v 完成后才能得到 u。图中 a 是最终结果，向下连接 b、k、c 等依赖分支。

互不相连的分支可以并行，例如 a 所需的 b、k、c 在其各自依赖满足后可同时准备；同一条链上的节点不能调换。沿图从 a 到叶节点的最长依赖链，给出了算法无法被更多处理器消除的串行部分。

T_1 是单处理器时间，可视为完成全部基本操作的总工作规模；T_p 是实际给 p 个处理器后的完成时间；T_\infty 假设可用处理器无限，时间由依赖链决定，因此对应 depth 或 critical path。

P012 的问题可直接从 DAG 读取：若最长依赖链有四层，即使每层所有节点同时完成，计算仍需四个单位时间。更多处理器分摊同层 work，关键路径保留顺序。

Brent 定理给出 T_1/p\leq T_p\leq T_1/p+T_\infty。左边是容量下界：p 个处理器每单位时间最多消化 p 份工作。右边说明可以把调度做到接近理想均分，额外损失不超过一条关键路径量级。

当 T_1/p 远大于 T_\infty 时，增加处理器能近似线性加速；当 T_1/p 已经很小，关键路径占主导，再加处理器收益有限。于是 T_1 和 T_\infty 缺一不可：只看总工作不知道并行上限，只看深度不知道资源不足时的代价。

课件关于 CPU 数的结论处在 PRAM 设定中：共享内存访问等成本，不计网络、缓存一致性和锁竞争。后文的 Hogwild! 与 Spark 则把这些系统成本放回分析。

分析顺序很直接：先画依赖，算总 work，再找 depth，最后用处理器数估计 T_p。P016-P017 会把这套方法用于平方损失的求和和梯度。

总体目标 F(w)=\sum_{i=1}^{m}F_i(w,x_i,y_i) 把 m 个样本贡献相加。对平方损失，单项是 \lVert x_i^\top w-y_i\rVert_2^2：先做长度 n 的内积，再形成残差与平方。不同样本之间独立，单个内积的不同乘加也能拆分，所以课件把 m 称为数据并行，把 n 称为模型并行。

目标值和梯度都需要聚合全部样本。梯度 2\sum_i x_i(x_i^\top w-y_i) 的每项是长度 n 的向量；每个处理器可先算局部向量，随后按坐标归约。两者都保留相同的 mn 总算术规模。

若按 P016 的 Basic summation 把所有元素串行累加，work 与 depth 都是 O(n)；这会浪费处理器。树形归约第一层同时算相邻两项，下一层再合并部分和，层数为 O(\log n)。总加法数没有下降，所以 work 仍为 O(n)。

把同一思路用到样本和坐标，可在理想 PRAM 下把 mn 份工作安排为对数深度。P017 因而给目标值和梯度都标为 work O(mn)、depth O(\log mn)。这里的对数深度假设有足够处理器和并行归约结构。

梯度算完后，参数按 w_{k+1}=w_k-\alpha\nabla F(w_k) 更新。第 k+1 次梯度必须用新的 w_{k+1} 才能计算，迭代之间形成一条串行链，不能像样本项那样同时展开。

在强凸、可微且梯度 L‑Lipschitz 的课件条件下，取 \alpha<1/L 可得到几何收敛：误差每轮按固定比例缩小，因此达到 \varepsilon 需要 O(\log(1/\varepsilon)) 轮。这个迭代数不是来自并行求和，而是来自优化误差递减。

每轮 depth 是 O(\log mn)，轮数是 O(\log(1/\varepsilon))；由于轮与轮串行，总 depth 相乘为 O(\log(1/\varepsilon)\log mn)。总 work 同理是 O(mn\log(1/\varepsilon))；P017 只把总 depth 写在页上，P019 会把总 work 一并列出。

这个推导给出一个重要分界：样本内与样本间的算术能高度并行，优化迭代链不能。后面 SGD 会通过减少每轮样本把单步 work 降低，却会付出更多迭代。

这里的数量级建立在平方损失、强凸性、L‑smooth、理想 PRAM 与树形归约上。把它部署到集群后，梯度传输、参数广播和慢节点等待会进入每轮时间；P023 与 P027 接着用通信轮数和 Spark 数据流分析这些成本。

SGD 在第 k 轮均匀抽取索引 s_k，只算 \nabla F_{s_k}(w_k) 并更新 w_{k+1}=w_k-\alpha\nabla F_{s_k}(w_k)。由于不再遍历 m 个样本，单轮 work 从 O(mn) 降为 O(n)；长度 n 的内积和向量操作可归约到 O(\log n) depth。

这一步是有噪声的完整梯度估计。不同随机样本给出不同方向，轨迹会抖动，因而课件采用的误差轮数从 batch 的 O(\log(1/\varepsilon)) 变为 O(1/\varepsilon)。

Batch 总 work 是 O(mn\log(1/\varepsilon))；SGD 总 work 是 O(n/\varepsilon)。前者随样本数 m 线性增长，后者在课件模型中与 m 脱钩，却对高精度 \varepsilon 更敏感。

例如只从数量级看，数据极大而容许中等误差时，省掉每轮全数据扫描可能占优；若要求极小误差，1/\varepsilon 的轮数会快速压过对数项。课件因此用问句收尾，而不是宣布固定赢家。

Batch 总 depth 为 O(\log(1/\varepsilon)\log mn)；SGD 为 O(\log n/\varepsilon)。SGD 单轮 depth 低，但轮数多，并且轮与轮仍依赖前一个参数。低单轮 depth 并不自动等于低总 depth。

还有一个尚未计入的系统问题：多个处理器若同时做 SGD，会读写同一 w。P020-P022 将显示，真正难点不是单个随机梯度怎么算，而是并发更新是否需要锁。

先确定数据规模 m、模型维度 n 和目标误差 ε，再看硬件能否提供理想归约。最后还要加入同步与通信。这样得到的是条件化选择：单机共享内存、GPU 数量、稀疏性与分布式网络会改变同一复杂度式子的实际代价。

P019 把两种方法放在同一误差符号 \varepsilon 下，比较的是同一目标差或解误差的收敛阶。表中的 \log(1/\varepsilon) 与 1/\varepsilon 说明高精度目标会显著放大 SGD 的迭代数。

随机梯度的方差和步长安排也会影响实际轨迹。本讲保留源页给出的迭代阶，下一单元转向并发写入，把复杂度表外的共享参数成本加入讨论。

在 PRAM 设置中，所有 CPU 都读写同一 w。一次 SGD 更新包含读取参数、计算随机梯度、写回新参数。若两个 CPU 同时读到旧值，它们各自完成计算后再写回，后一次写入可能覆盖前一次更新；即使没有整向量覆盖，某些坐标也会丢失增量。

问题的根源不是梯度公式错误，而是 read–modify–write 缺少原子性。把 w 加全局锁可以恢复顺序语义，却会让所有处理器排队，SGD 的并行收益随之消失。

样本 x_i=(x_i^{(1)},\ldots,x_i^{(n)}) 若稀疏，单次梯度只更新与非零特征对应的少量 w^{(k)}。两个处理器随机抽到的样本支持集常常不重叠，于是它们可同时写不同坐标，无需为整向量加锁。

即使支持集偶尔重叠，课件的判断是碰撞概率在大数据稀疏场景中较低。这个判断依赖特征分布：若少数热门坐标在几乎所有样本中非零，实际冲突仍可能集中发生，Hogwild! 的优势会下降。

每个处理器独立重复三步：从 \{1,\ldots,m\} 随机采样 j；读取共享内存中当下可见的 w 并计算 F_j(w) 与 \nabla F_j(w)；只对样本非零坐标做 w^{(k)}\leftarrow w^{(k)}-\alpha[\nabla F_j(w)]^{(k)}。算法没有全局锁，也不等待其他 CPU 完成。

因此某个梯度可能基于稍旧的参数，写入顺序也不确定。Hogwild! 接受这种异步噪声，以换取接近 CPU 数量的线性加速；可接受的前提是目标更新稀疏、步长和延迟不会让误差失控。

P022 先采样索引 j，随后写出 x_i^{(k)}\neq0。这里应按所采样样本的非零坐标执行更新；逐页翻译保留原式，并标出这一处记号跳变。

“直到达到期望误差条件”给出停止目标。实现时可定期汇总或抽样评估当前误差；Hogwild! 取消的是参数更新的全局锁，误差监测仍可按系统需要安排。

Batch 的并行点在一轮内部：各处理器算局部梯度，再同步归约。Hogwild! 的并行点跨越更新本身：处理器不等归约，直接异步改参数。两种方案分别把同步成本放在“每轮一次”和“尽量不锁”，这会直接影响单机与分布式系统的选择。

普通 SGD 单轮 depth 低，却难以让多个处理器同时更新；Hogwild! 借助稀疏性把它变成接近 embarrassingly parallel。Batch 每轮工作多，但局部梯度天然可拆分并归约。

跨机器时，参数或梯度需要通信。课件把通信轮数近似为迭代数：batch 为 O(\log(1/\varepsilon))，stochastic 为 O(1/\varepsilon)。因此单机多 GPU 常偏向 stochastic，共享内存和高速互联能支撑频繁更新；分布式系统更常用 batch，以较少轮次换取每轮较大的并行工作。

先问内存模型：同机共享参数还是跨机通信；再问数据稀疏性是否支持无锁更新；最后用 ε 对应的迭代数估算同步轮次。这个顺序比只比较每轮 FLOPs 更接近课件的最终判断。

前面已经知道 batch 易归约、SGD 迭代多、Hogwild! 依赖共享内存。P024 的 Applications 高亮表示现在要把这些判断放进一个真实执行框架，而不是重新介绍梯度下降。

工具选择决定可用执行原语；batch 或 stochastic 决定每轮读多少样本；数据大小与稀疏性决定内存和冲突。课件指定 Spark，并假设模型维数 n 足够小可放入内存，而样本数 m 不设上限。

这意味着不能把完整数据复制到每台机器，但可以反复传递相对较小的参数 w。最终问题“如何在集群存储数据”自然导向按行分区的 RDD。

实现需要回答三件事：样本分区是否复用，参数每轮发送几次，局部梯度如何聚合。P026 给出基线流程，P027 专门追问通信瓶颈，P028 再检验 SGD/Hogwild! 是否适配 Spark 的同步边界。

数据先按行放入 RDD，每一行对应样本 p。map 使用当前参数 w 把样本变成局部梯度 \nabla F_p(w)；reduce 把所有局部梯度相加；driver 或控制端据此更新 w。然后从 map 梯度这一步开始下一轮，直到误差条件满足。

第 2 步提到 closure，表示 map 函数携带计算所需的参数环境。第 3 步 cache 让 RDD 的样本分区跨迭代复用，避免每轮重新从上游读取或重算。源页称 cache 为 action；在解释层应关注它的目的，即把迭代数据保留在内存。

map 阶段没有样本间依赖，正对应 P015 的 data parallelism。每个任务只读 w 并输出梯度，不应原地修改共享参数。reduce 阶段执行树形向量求和，对应 P016 的并行归约；其输出长度是模型维数 n。

更新 w 发生在聚合之后，这形成清晰的同步屏障：所有任务使用同一轮参数，完整梯度确定后才进入下一轮。这是 batch 方法确定性和易并行的系统表达。

第一组问题围绕 w：每轮是否随任务重复发送，mapper 是否只读，它相对带宽和内存有多大，以及是否应使用 broadcast。P025 的 n 可入内存假设允许保存参数；广播频率仍决定网络成本。

第二组问题转向端到端时间。样本 RDD 被 cache 后，反复扫描可留在内存；参数广播、梯度 shuffle/reduce、慢任务等待和迭代轮数共同决定瓶颈。应据 n、分区数、网络与轮数逐项估算。

每轮局部计算约随本分区样本数乘 n 增长，通信至少要分发或引用 w 并归约长度 n 的向量。数据越多，局部计算越能摊薄固定广播成本；模型越大，参数与梯度传输越突出。

因此优化不是简单增加 mapper 数。任务过细会制造更多调度与归约开销，任务过粗又降低并行度。P028 进一步说明，Spark 的容错屏障让细粒度异步 Hogwild! 更难实现。

Hogwild! 希望处理器随时读取和写回共享参数；Spark 的 mapper 要等 broadcast 完成，下一次 broadcast 又要等当前 mapper、reducer 全部结束。每轮都存在同步屏障，正是 Hogwild! 想避免的协调。

Spark 用 lineage、stage 和重算获得容错，这要求执行边界清晰。把共享内存的无锁细粒度更新原样搬进这种模型，会失去近似连续的异步写入。

第一种是尝试随机更新，只接受能降低目标的候选；第二种是 mini-batch：每轮选“许多”样本而非一个，并在这个子集上执行 batch 更新。后者在随机性与规整 map/reduce 之间折中。

mini-batch 增大单轮计算，使 broadcast 与 barrier 成本能被更多样本摊薄；同时比 full batch 少处理数据。批大小因此是系统参数，也是优化噪声参数。

SGD 的 O(1/ε) 迭代倾向意味着通信轮数多，Spark 屏障会放大这一缺点。mini-batch 试图用每轮更多工作换更少或更有效的同步轮次，延续了本讲一贯的 work、depth 与通信权衡。

当原始维数太大，先用 PCA 把数据投影到较低维子空间，再在近似数据上运行梯度下降。这样降低单样本向量长度 n，因而同时降低内积、梯度、参数和通信规模；代价是丢失被舍弃方向上的信息。

黄色 V 是均值中心化后的样本向量，绿色 M 是它在虚线候选主轴上的投影，红色 m 是从投影点到原向量端点的正交残差。三者构成直角三角形，因此 V^2=M^2+m^2。

对固定 V，左侧长度不变。最大化投影 M 会自动最小化残差 m；对全部样本求和后，最大投影方差与最小平方重构误差成为同一几何选择。

课件用“最大化 \mathbb{E}[XX^\top] 的方向”概括协方差方向。均值中心化让二阶矩对应方差结构；PCA 选最大特征值对应的轴。将残差平方和写成目标后，也可用优化方法寻找重构误差最小的方向。

PCA 与本讲优化线的连接在于投影—残差关系：保留方差大的方向，同时压低正交残差。选出的轴会缩小后续模型的 n，直接改变前文含 n 的计算和通信量。

目标是在线性等式或不等式约束限定的可行域内最大化线性函数。最大化可以通过目标取负改写为最小化，因此能够与本讲统一使用“让目标下降”的语言。

simplex 从一个基本解出发，通过选择 pivot 移动到更好的基本解。不同 pivot 规则会产生不同路径和收敛速度；课件把最佳 pivot 类比为寻找最能改进目标的方向。

两种方法的移动方式不同：梯度下降在连续空间按局部导数更新，simplex 沿可行多面体的边在基本解之间跳转。二者都反复改进目标，线性约束的几何结构使本页采用 pivot。

P006 已用旅行商等问题说明优化结构多样，P030 再次回到算法适配：即使都能写成最小化，线性约束结构会导向 simplex。它为 No Free Lunch 提供了一个具体收尾。

第一、二问要求定义 batch 与 stochastic 并比较单轮和总成本；第三问要求用 PRAM、work、depth 分析并行性；第四问要求说明 Hogwild! 的随机采样、稀疏坐标和无锁更新；第五问要求把 batch/SGD 放进 Spark 的 map、reduce、broadcast 与 barrier。

完整回答从平方损失 F(w) 出发，说明 batch 与 SGD 如何取梯度，再给出 m、n、\varepsilon 下的 work/depth；接着把共享内存竞态和分布式通信放入选择，最后落到 Spark 的迭代数据流。

P032 只显示 Thank you 和课程标志。它不提供新结论，因此本讲知识链在 P031 的五问处已经闭合。