第5章优化：按主题组织的课程讲解

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

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

小规模数据部分先从回归、平方误差和普通梯度下降建立更新规则。大规模数据部分加入PRAM、DAG、工作量、深度，再比较批量、SGD与Hogwild!。应用部分把前面的结论带入Spark，并连接PCA与线性规划。

读图时应关注分支颜色：P002高亮小规模数据，P010改为大规模数据，P024再改为应用。这个视觉变化就是模块切换标记。

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

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

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

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

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

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

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

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

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

课件的结论是：没有对所有搜索问题都最好的方法。后面的批量、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展开引出Hessian。梯度只告诉当前斜率，Hessian还描述各方向曲率；用曲率校正更新可把不同尺度的坐标统一起来，并允许课件所说的步长1。代价是构造并求解二阶系统，直接求逆复杂度记为 O(n^3)，当模型维数很大时未必划算。

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

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

课件把批量方法描述为最优、SGD描述为足够好，并认为随机性有助于逃离局部最小值。对前面给定的强凸问题，局部最小值并非核心困难；这组话适用于可能含局部极小点的非凸优化。P019会把可比较部分收敛到工作量、深度与 ε。

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

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

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

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

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则把这些系统成本放回分析。

分析顺序很直接：先画依赖，算总工作量，再找深度，最后用处理器数估计 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的基础求和把所有元素串行累加，工作量与深度都是 O(n)；这会浪费处理器。树形归约第一层同时算相邻两项，下一层再合并部分和，层数为 O(\log n)。总加法数没有下降，所以工作量仍为 O(n)。

把同一思路用到样本和坐标，可在理想PRAM下把 mn 份工作安排为对数深度。P017因而给目标值和梯度都标为工作量 O(mn)、深度 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)) 轮。这个迭代数不是来自并行求和，而是来自优化误差递减。

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

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

这里的数量级建立在平方损失、强凸性、L‑光滑、理想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 个样本，单轮工作量从 O(mn) 降为 O(n)；长度 n 的内积和向量操作可归约到 O(\log n) 深度。

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

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

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

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

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

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

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

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

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

问题的根源不是梯度公式错误，而是读取–修改–写入缺少原子性。把 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!取消的是参数更新的全局锁，误差监测仍可按系统需要安排。

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

普通SGD单轮深度低，却难以让多个处理器同时更新；Hogwild!借助稀疏性把它变成接近无需同步即可并行。批量方法每轮工作多，但局部梯度天然可拆分并归约。

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

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

前面已经知道批量方法可按样本分区后归约、SGD迭代多、Hogwild!依赖共享内存。P024的应用高亮表示现在要把这些判断放进一个真实执行框架，而不是重新介绍梯度下降。

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

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

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

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

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

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

更新 w 发生在聚合之后，这形成清晰的同步屏障：所有任务使用同一轮参数，完整梯度确定后才进入下一轮。这是批量方法确定性和“各任务可独立执行后统一归约”的系统表达。

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

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

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

增加映射任务数只在可并行工作量足以覆盖调度和归约开销时有效。任务过细会制造更多调度与归约开销，任务过粗又降低并行度。P028进一步说明，Spark的容错屏障让细粒度异步Hogwild!更难实现。

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

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

第一种是尝试随机更新，只接受能降低目标的候选；第二种是小批量方法：每轮选“许多”样本而非一个，并在该子集上执行批量更新。后者在随机性与规整映射/归约之间折中。

小批量方法增大单轮计算，使广播与屏障成本能被更多样本摊薄；同时比全批量方法少处理数据。批大小因此是系统参数，也是优化噪声参数。

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

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

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

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

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

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

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

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

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

P006已用旅行商等问题说明优化结构多样，P030再次回到算法适配：即使都能写成最小化，线性约束结构会导向单纯形。它为没有免费午餐定理提供了一个具体收尾。

第一、二问要求定义批量方法与随机方法并比较单轮和总成本；第三问要求用PRAM、工作量、深度分析并行性；第四问要求说明Hogwild!的随机采样、稀疏坐标和无锁更新；第五问要求把批量方法与SGD放进Spark的映射、归约、广播与屏障。

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

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