精读笔记

Problem Setting

这份讲义实际处理的是凸优化的一阶方法体系，而不是某个单一优化任务。问题设置可以概括为：在有限维或 Hilbert-like 空间中，给定凸函数、约束集、非光滑正则项、线性算子复合或随机梯度 oracle，如何建立可验证的最优性条件，并设计只依赖一阶信息或 prox 的迭代算法。

真正困难点是“结构破坏”：约束会让普通梯度步离开可行域；非光滑项让梯度不存在；线性复合 g(Kx) 通常让 prox_{g∘K} 不可显式计算；随机梯度让每步下降不再确定；OT 这种线性规划型问题虽然凸，但原始变量规模和约束结构很硬。以前最朴素的路线，即直接 gradient descent，只适用于光滑无约束问题，无法覆盖这些场景。

关键矛盾是：凸性给了全局结构，但可计算算法只能利用局部、低阶、分裂的信息。整份讲义就是在搭桥：用 subgradient、prox、Fenchel duality、saddle-point reformulation 和 Lyapunov/energy estimates，把全局凸结构转化成局部可迭代更新。

Motivation

已有最基础路线不够，是因为“可微 + 无约束 + 简单欧氏几何”在实际问题中太窄。成像里的 TV/L1 正则、机器学习中的大样本和随机梯度、OT 中的 coupling 约束，都要求算法能够处理非光滑性、约束和线性算子结构。

作者的核心观察并不新，但组织得很清楚：凸优化的关键不是寻找局部下降方向，而是构造全局有效的不等式。subgradient inequality、projection nonexpansiveness、Moreau envelope smoothing、Fenchel inequality、primal-dual gap，本质上都是用来生成可 telescoping 的能量估计。

缺口在于从基础凸分析到实际算法之间经常被讲成一堆方法名。这里试图补上的是推导链条：为什么 subgradient 是 gradient 的正确替代，为什么 prox 是隐式 subgradient step，为什么 duality 能把不可计算 prox 变成可分裂 saddle-point 更新，为什么 acceleration 需要特殊势函数而不是简单加 momentum。

Core Idea

核心思想是把一阶凸优化统一为“支撑结构 + 正则化局部模型 + 对偶分裂”的算法设计范式。对于光滑函数，梯度给出局部线性近似；对于凸非光滑函数，subgradient 给出全局线性下界；对于非光滑但 prox-friendly 的函数，proximal step 等价于在二次稳定项下做隐式最小化；对于含 K 的复合项，Fenchel 对偶把 K 从 prox 内部移到 saddle-point 的双线性耦合中。

这改变的不是某个模型结构，而是建模和求解的接口：不再要求目标整体可微或整体 prox 可解，而是要求每个组成部分有可利用的凸结构。它引入的 inductive bias 是“分裂可计算性”：算法设计围绕哪些部分适合显式梯度、哪些部分适合隐式 prox、哪些部分适合转到 dual。相比单一 gradient descent，这种组织方式更 scalable，因为它允许复杂目标由简单 oracle 组合而成。

Method

1. Subgradient 与支撑超平面：解决非光滑凸函数没有梯度的问题。需要它是因为 L1、indicator、norm、max 等核心对象不可微。核心变化是把“局部一阶近似”替换为“全局线性下界”，从而保留全局最优性条件 0 ∈ ∂f(x)。

2. Projection / projected subgradient：解决约束迭代不可行的问题。projection 的非扩张性是收敛证明的关键，不只是一个修补步骤。它把可行性维护变成几何算子，并允许距离到最优点的递推不等式成立。

3. Proximal operator：解决显式 subgradient step 不稳定、收敛慢、非光滑项难处理的问题。prox 的核心作用是把非光滑部分放进局部二次模型中精确最小化，相当于隐式 Euler。它带来的变化是从“选一个 subgradient”转向“解一个局部正则化问题”。

4. Proximal gradient / FISTA：解决复合结构 f+g 中光滑项和非光滑项应分开处理的问题。f 用线性化加二次上界，g 用 prox 精确处理。FISTA 的加速不是普通 momentum，而是通过特殊 t_k 构造可 telescoping 的能量。

5. Fenchel duality / PDHG / ADMM：解决 g(Kx) 的 prox 通常不可计算的问题。通过 conjugate 和 saddle-point reformulation，K 被移到双线性项中，prox 只作用在 f、g* 或分裂变量上。核心变化是把一个难 prox 问题转化成 primal-dual 交替更新。

6. SGD 与 OT excursion：SGD 部分说明 deterministic subgradient 的证明模板可以在 unbiased bounded-variance oracle 下迁移；OT 部分展示 convex duality 和 entropy regularization 如何导出 Sinkhorn scaling，但更像应用展示而非主线贡献。

Key Insight / Why It Works

最重要的 insight 是：凸优化一阶算法的收敛证明几乎都来自同一种结构，即构造一个单调或可 telescoping 的量。subgradient method 用距离平方递推；proximal gradient 用 descent inequality 和 Fejer monotonicity；FISTA 用带 t_k 的势函数；PDHG 用 primal-dual gap 和正定 block metric；ADMM 用 Lyapunov functional；SGD 则把同样的距离递推放进条件期望中。

真正有效的部分不是某个更新公式，而是每个公式背后的不等式设计。prox 有效是因为二次项提供强凸性和稳定性；Fenchel duality 有效是因为 conjugate 把复杂复合变成可分裂 saddle structure；PDHG 有效是因为步长条件 στ||K||² < 1 保证耦合项能被 block norm 吸收；FISTA 有效是因为 t_k 的递推精确匹配能量差分，而不是因为“加了动量”。

最可能的核心贡献是教学组织上的机制统一，而不是研究创新。文中大部分结果是已有理论重组：Beck 的一阶方法、Chambolle-Pock、Fenchel-Rockafellar、ADMM、Sinkhorn 都是标准路线。所谓增益主要来自更好的 mathematical organization，而不是新的 scaling、data、retrieval 或 representation alignment。

哪些只是辅助：OT 章节更像扩展阅读，和前面算法主线连接有限；SGD 章节只覆盖最基础的 unbiased bounded-variance subgradient setting，离现代 stochastic optimization 的关键技术还很远；heavy ball 的局部线性化分析有价值，但在这份讲义中更多是为了引出 acceleration intuition，而非完整现代加速理论。

Relation To Prior Work

这份讲义最接近 Beck 2017 的 first-order methods 教材路线，加上 Chambolle-Pock 2011、ADMM 标准分析和 Villani OT 基础内容。它不是站在某篇 prior work 上提出改进，而是把几个成熟谱系串起来：convex analysis -> subgradient/prox -> acceleration -> Fenchel duality -> primal-dual splitting -> stochastic variants -> entropy-regularized OT。

真正不同点不在定理本身，而在叙事顺序：从 subgradient 的几何存在性一路推到 prox，再用 duality 解释 primal-dual 方法，最后以 OT/Sinkhorn 展示这些概念在现代应用中的落点。这个组织方式对研究者有用，因为它突出“prox 和 duality 是同一套凸分析语言的两个接口”。

看似新的部分基本都是已有思想重组。FISTA、PDHG、ADMM、Moreau envelope、Fenchel-Rockafellar、Kantorovich duality、Sinkhorn-Knopp 都不是新贡献。实质价值是压缩出一条可复用的推导路径：当遇到新的复合凸问题时，先判断 smooth/prox/linear-coupled/stochastic 结构，再选择对应分裂和能量估计。

Dataset / Evaluation

没有 dataset，也没有实证 evaluation。文中所谓 experiments 线索实际不是实验，而是理论结果、例子和应用性 excursion。评估方式是证明收敛率、最优性条件和 duality equality。

这支持的 claim 只能是教学性和理论正确性：这些算法在给定假设下收敛，某些复杂问题能被等价重写。它不能支持任何关于实际运行速度、数值稳定性、工业规模可扩展性或 benchmark superiority 的结论。

OT/Sinkhorn 部分也没有数值验证。熵正则 OT 的可计算性来自矩阵 scaling 结构，但文中没有讨论 ε 很小时的数值病态、采样误差、GPU 实现、log-domain stabilization 或大规模近似。因此 evaluation 对现代应用 claim 的支持很弱；这不是缺点，而是讲义定位决定的。

Limitation

第一，创新性上限明确：这是一份 lecture notes，不是研究论文。它没有新的算法、理论界、lower bound 或实验发现。若按 arXiv research paper 标准评估，贡献主要是整理。

第二，严谨性不均匀。文中多处证明留作 exercise 或 proof sketch，OT 部分明确不严谨；无限维空间、闭性、紧性、constraint qualification 等细节经常被简化。对研究使用而言，这些地方不能直接引用为完整证明。

第三，算法覆盖偏经典。没有现代 composite optimization 中常见的 variance reduction、coordinate/prox-linear methods、adaptive restart、Catalyst、non-Euclidean mirror/prox geometry、Bregman proximal methods、大规模 randomized linear algebra 等内容。

第四，scalability 讨论不足。prox 是否真的可计算、projection 是否昂贵、K 的 operator norm 如何估计、ADMM 子问题是否易解、Sinkhorn 在小 ε 下是否稳定，都是实际部署中的核心问题，文中基本没有展开。

第五，SGD 部分过于基础。bounded variance + unbiased oracle 的结论不能解释现代深度学习优化，也不涉及 generalization、implicit bias、minibatch scaling 或 adaptive optimizers。这里的“随机优化”更像 deterministic subgradient proof 的期望版，而不是现代 SGD 理论。

第六，OT 部分把 convex optimization 工具迁移到应用场景的方向是对的，但深度有限。Kantorovich duality 和 Sinkhorn 的呈现足够入门，不足以支撑关于 OT 在 ML 中有效性的任何强判断。

Takeaway

• 1. 最值得记住的是统一机制：凸优化算法不是一堆 update rule，而是一堆可 telescoping inequality 的构造方式。
• 2. prox 是从非光滑显式下降转向稳定隐式建模的关键接口；对研究者而言，判断一个新问题是否 prox-friendly 往往比写出目标函数更重要。
• 3. Fenchel duality 的实际算法价值在于移动线性算子 K：它把不可计算的 prox_{g∘K} 变成可分裂的 saddle-point 更新，这是 PDHG/ADMM/Sinkhorn 等方法背后的共同模式。
• 4. 未来真正值得迁移的不是这些具体算法名，而是问题分解原则：识别 smooth part、prox part、linear coupling、constraint geometry 和 stochastic oracle，然后为它们设计匹配的能量函数。

一句话总结

这份讲义在凸优化方向中的位置是一份机制导向的经典一阶方法路线图，真正贡献是把 subgradient、prox、duality、splitting 和 OT scaling 组织成同一套可推导的凸分析语言，而不是提出新的优化算法。