Frank–Wolfe 算法学习笔记

1. Frank–Wolfe 到底解决哪类问题

Frank–Wolfe（也叫 conditional gradient）主要解决光滑凸约束优化 min_{x∈D} f(x)。它特别适合这样一种结构：把点投影回可行域 D 很贵，但在 D 上求一个线性目标的最小值却很容易。它不做“梯度一步 + 投影”，而是调用线性最小化 Oracle 找到一个有利的可行极点，再用凸组合向它移动。

minimize f(x) subject to x ∈ D, f convex and differentiable, D compact and convex

关键要点

FW 并不是普遍意义上“更好的梯度下降”，而是利用了某些可行域的特殊几何结构。
典型可行域包括 simplex、ℓ1 ball、flow polytope、matroid polytope、nuclear-norm ball 等。
当稀疏解或低秩迭代本身有价值时，FW 往往格外合适。

2. 为什么投影可能比求梯度还贵

投影梯度法先计算 y_t=x_t−η∇f(x_t)，然后还要解一个投影问题 min_{x∈D} ‖x−y_t‖²。若 D 是 box，投影很简单；但对复杂结构域，投影本身可能就是一次不小的优化，甚至需要完整矩阵分解。FW 用同一个可行域上的线性优化替代了投影。

Projected GD: yₜ=xₜ−η∇f(xₜ), xₜ₊₁=Π_D(yₜ)

FW: sₜ=argmin_{s∈D}⟨∇f(xₜ),s⟩

关键要点

在 ℓ1 ball 上，欧氏投影要做阈值/排序类操作，而 LMO 只需找到绝对梯度最大的坐标及其符号。
在 nuclear-norm ball 上，投影往往需要完整或大规模 SVD；LMO 只需最大奇异向量对。

3. 线性最小化 Oracle：整个算法的核心

在当前点 x_t，梯度给出局部上升方向，因此 FW 求 s_t=argmin_{s∈D}⟨∇f(x_t),s⟩，也就是问：在一阶线性近似下，可行域里哪个点最有利？对紧致凸多面体，线性目标的最优点通常位于极点，因此 s_t 往往就是一个 atom/vertex。

sₜ = LMO(∇f(xₜ)) = arg min_{s∈D} ⟨∇f(xₜ), s⟩

关键要点

LMO 只依赖可行域与当前梯度，因此可以复用针对该结构的专用组合优化算法。
在概率 simplex 上，LMO 直接选择梯度分量最小的那个顶点。
在某些 flow polytope 上，LMO 可以转化为最短路或最小费用流。

4. Frank–Wolfe 的基本迭代

LMO 得到 s_t 后，定义方向 d_t=s_t−x_t，再用 x_{t+1}=x_t+γ_t d_t 更新，其中 γ_t∈[0,1]。由于新点是 x_t 与 s_t 的凸组合，而二者都在凸可行域中，因此 x_{t+1} 自动保持可行。这就是“projection-free”的本质：只要初始点可行，后续每一步都不需要再做投影。

dₜ=sₜ−xₜ

xₜ₊₁=(1−γₜ)xₜ+γₜsₜ

关键要点

每次 FW 最多向 active set 中加入一个新 atom。
这种增量式表示使 FW 在较早迭代就能得到稀疏组合或低秩矩阵。
若 γ_t=1，旧点被完全丢弃；γ 较小时，则通过凸组合保留过去已选 atom 的权重。

5. 步长：固定规则还是线搜索

步长决定本次更新把多少权重转移到新 atom 上。经典理论步长是 γ_t=2/(t+2)。精确 line search 则直接在 γ∈[0,1] 上最小化 f(x_t+γd_t)，如果一维优化很便宜，通常效果更好。无法精确 line search 时，也可以利用 smoothness/Lipschitz 常数做自适应步长。

γₜ^LS = arg min_{γ∈[0,1]} f(xₜ + γ(sₜ−xₜ))

关键要点

步长太小会浪费昂贵的 LMO 调用；太大则可能在顶点之间来回跳动。
二次目标下，line search 通常可以得到一个再截断到 [0,1] 的闭式标量解。
步长会影响收敛常数和实际速度，但长期表现往往更受可行域几何结构影响。

6. Frank–Wolfe Gap：可计算的最优性证书

FW gap 定义为 g_FW(x_t)=⟨∇f(x_t),x_t−s_t⟩。由于 s_t 已经是线性化目标在 D 上的最小点，根据凸性可以证明 f(x_t)−f(x*)≤g_FW(x_t)。因此它既是当前是否接近一阶最优的指标，又是凸问题中可计算的 primal suboptimality 上界，而且几乎不增加计算成本，因为 s_t 本来就要由 LMO 算出来。

g_FW(xₜ)=⟨∇f(xₜ), xₜ−sₜ⟩ ≥ f(xₜ)−f(x*) ≥ 0

关键要点

相邻迭代目标值变化很小不一定说明接近最优；FW gap 具有更明确的最优性意义。
对非凸光滑问题，类似 FW gap 仍可用于一阶驻点判据，但不再能作为全局最优差距上界。

7. 为什么经典 FW 是 O(1/t) 收敛

对紧致凸域上的光滑凸函数，一阶线性近似的误差可以由 curvature/smoothness 控制。把下降引理与 LMO 的最优性质结合，可得到目标误差 h_t=f(x_t)−f(x*) 的递推，再配合经典步长可证明 h_t=O(1/t)。关键点是：FW 在不投影的情况下仍然能保证进步；但经典版本在多面体上通常不能直接获得线性收敛，因为它“加新 atom 很容易，删旧 atom 很困难”。

f(xₜ)−f(x*) ≤ 2C_f/(t+2) (classical smooth convex bound)

关键要点

curvature constant C_f 综合反映目标函数曲率和可行域尺度，是 FW 分析中的核心量。
O(1/t) 意味着在渐近阶段，要把误差再减半，迭代次数大致需要再翻倍。
FW 是否实际更快不能只看迭代次数，还要比较一次 LMO 与一次投影到底谁更贵。

8. Active Set、稀疏性与 Zig-Zag 问题

如果 D 是一组 atoms 的凸包，那么 FW 迭代点可写成 x_t=Σ_{v∈S_t} α_v v，其中权重非负且和为 1。Active set S_t 就是目前选入表示的 atoms。这个结构天然产生稀疏表示，但经典 FW 主要擅长“加入新 atom”，没有专门机制快速删除早期选错的 atom，因此在边界最优点附近容易出现 zig-zag，收敛很慢。

xₜ = Σ_{v∈Sₜ} α_v v, α_v ≥ 0, Σ_v α_v = 1

关键要点

若不做额外压缩，第 t 次迭代后最多只需 t+1 个 atom 表示当前解。
这对稀疏混合、结构化预测和低秩矩阵构造非常有吸引力。
但同一结构也会带来问题：当需要大幅降低旧 atom 权重时，经典 FW 会比较慢。

9. Away-Step、Pairwise 与 Fully Corrective FW

Away-step FW 增加了第二种方向：除了朝新 atom 移动，还可以选择一个当前 active set 中最不合适的 atom，并“远离”它，从而降低其权重。Pairwise FW 更直接，把权重从坏的 active atom 转移到新的 LMO atom；Fully Corrective FW 则周期性地对 active set 中所有系数重新优化。这些方法针对的正是经典 FW 难以删除旧 atom 的缺点，并可在更强条件下对多面体获得线性收敛。

FW direction: d_FW=sₜ−xₜ

Away direction: d_A=xₜ−vₜ, vₜ=argmax_{v∈Sₜ}⟨∇f(xₜ),v⟩

Pairwise: d_P=sₜ−vₜ

关键要点

Away step 的最大步长受当前 atom 权重限制，因为系数不能变成负数。
Pairwise FW 能更直接地替换 active set 中的质量分配，通常比经典 FW 更积极。
Fully Corrective 可能显著减少迭代次数，但每次 correction 需要额外求一个 active-set 子问题。

10. 几个真正重要的结构化例子

理解 FW 最好的方式，是看 LMO 在具体可行域上到底做什么。概率 simplex 上，LMO 返回一个标准基向量，因此迭代解是稀疏概率混合；ℓ1 ball 上，LMO 只返回一个带符号坐标，因此自然产生稀疏向量；nuclear-norm ball 上，LMO 返回由最大奇异向量构成的 rank-1 矩阵，因此每次迭代矩阵秩最多增加 1。这些不是边缘例子，而是 FW 在大规模结构优化中真正有价值的原因。

关键要点

Simplex D={x≥0, Σx_i=1}：选择梯度分量最小的顶点 e_j。
ℓ1 ball ‖x‖_1≤τ：选择绝对梯度最大的坐标 j，s=−τ sign(∇_j f)e_j。
Nuclear-norm ball ‖X‖_*≤τ：取 ∇f(X) 的最大奇异向量 u_1,v_1，并令 s=−τu_1v_1^T。

11. 随机、块坐标与大规模 Frank–Wolfe

大规模学习问题中，完整梯度或全局 LMO 都可能太贵。Stochastic FW 用随机梯度，Block-coordinate FW 每次只更新一个变量块，Lazy/Cached FW 则在旧 LMO 解仍足够好时复用它。实际设计时不应该机械追求某个“高级变体”，而要先确定真正瓶颈到底是梯度计算、LMO、通信还是 active-set 维护。

关键要点

只要近似误差受控，approximate LMO 也能保留相应的收敛保证。
当 LMO 可在智能体或数据块之间分解时，Distributed FW 很有吸引力，但通信可能成为新瓶颈。
矩阵问题中，可以使用随机化最大奇异向量算法显著加速 nuclear-norm LMO。

12. 什么时候该用 Frank–Wolfe：选择与排错指南

适合使用 FW 的典型条件是：可行域上线性优化很便宜、投影明显更贵，而且稀疏/极点表示本身有价值。不能因为“问题有约束”就默认 FW 合适；若投影本来就很简单，Projected Gradient 或 proximal 方法可能更快。如果经典 FW 在边界附近停滞，应先检查 active set，并尝试 Away-step/Pairwise，而不是直接认为 projection-free 思路不行。

关键要点

分别监控 objective、FW gap、LMO 耗时、步长和 active-set size。
若 FW gap 仍很大但 objective 几乎不动，步长规则可能过于保守。
若运行时间主要花在 LMO，上层 FW 变体怎么换可能都不如先优化 Oracle 本身。
若 active set 过大，可考虑 corrective step、drop atom 或表示压缩。

这一节要记住

看完这篇后，你应该能够自己推导 FW 更新，为常见可行域写出 LMO，用 FW gap 做停止判据，解释经典 O(1/t) 收敛，并判断什么时候应该使用 Away-step 或 Pairwise 变体。