远离步 Frank–Wolfe 法

普通Frank–Wolfe每次向一个有利原子靠近，其他旧权重同比缩小。若某个旧原子已经不合适，反复缩小它可能很慢。远离步允许直接沿“离开这个原子”的方向移动；真正需要记录的状态于是除了当前位置，还有产生它的那份凸组合。

形式陈述

输入、方向与权重更新

设 $V\subset\mathbb R^d$ 为非空有限原子集， $d\ge1$ ，可行域 $C=\operatorname{conv}(V)$ 是它的凸包。 $f$ 在 $C$ 的邻域可微、在 $C$ 上凸，梯度在 $C$ 上为 $L$ -Lipschitz，取正的有效上界 $L>0$ 。输入一份已知可行表示

x_0=\sum_{v\in S_0}w_vv,\qquad S_0\subseteq V,\quad w_v>0,\quad\sum w_v=1,

以及精确线性最小化oracle、容差与预算。原子集不要求每个成员都是极点，但同一原子只记一次。

在当前状态 $(x,S,w)$ ，沿用Frank–Wolfe的线性oracle与gap，并在当前支持内寻找最不利原子：

\begin{aligned} s&\in\arg\min_{z\in V}\langle\nabla f(x),z\rangle, & G&=\langle\nabla f(x),x-s\rangle,\\ v&\in\arg\max_{z\in S}\langle\nabla f(x),z\rangle, & A&=\langle\nabla f(x),v-x\rangle. \end{aligned} \tag{1}

$G,A\ge0$ ，因为 $x$ 是所比较原子的凸组合。若 $G\le\varepsilon$ ，返回可行点及误差证书 $0\le f(x)-f^*\le G$ 。否则按较大下降量选方向，并在并列时选FW：

(d,\gamma_{\max},g)= \begin{cases} (s-x,\ 1,\ G),&G\ge A,\\ (x-v,\ w_v/(1-w_v),\ A),&G<A. \end{cases} \tag{2}

当支持只有一个原子时， $A=0$ ，不会选到第二分支，因此不会除以零。本页固定使用可直接计算的短步长

\gamma=\min\left\{\frac{g}{L\|d\|_2^2},\gamma_{\max}\right\}, \qquad x^+=x+\gamma d. \tag{3}

未停止时 $g>0$ ，故 $d\ne0$ 。FW分支将旧权重乘 $1-\gamma$ ，再给 $s$ 加 $\gamma$ ；away分支将所有旧权重乘 $1+\gamma$ ，再从 $v$ 的权重减 $\gamma$ 。删去恰为零的权重，得到新支持。

在away分支若 $\gamma=\gamma_{\max}$ ，称本页的一次drop步：所选原子被删去。其余更新称good步，包括可能一步到达 $s$ 的FW步。这个计数约定用于后文证明，不把FW重置支持与away截短步混为同一类。

直觉

可行性为什么依赖当前表示

FW分支的权重显然非负且和为1。away分支中，除 $v$ 外的权重都增加；唯一可能变负的是

w_v^+=(1+\gamma)w_v-\gamma =w_v-\gamma(1-w_v).

所以 $\gamma\le w_v/(1-w_v)$ 恰好保持这份表示非负。全部新权重之和是 $(1+\gamma)-\gamma=1$ ，因而仍得到 $x^+\in C$ 。这证明了每轮执行不变量。

在线性oracle值最低的原子 $s$ 之外，算法还查当前支持里值最高的 $v$ 。向 $s$ 靠近和离开 $v$ 都可能降低当前线性模型，比较 $G,A$ 决定采用哪种。away并不只是把质量从 $v$ 直接交给 $s$ ，而是按原比例增加所有其他当前权重；直接在两个原子之间换质量属于另一种pairwise更新。

下降量怎样支付

对可行线段，下降引理给

f(x+\gamma d)\le f(x)-\gamma g+\frac L2\gamma^2\|d\|^2. \tag{4}

式(3)在该二次上模型的最小点与权重允许上限之间取较小值。因此每轮目标不增。不过away允许上限可能非常小：即使方向很好，本轮也只能删掉一点剩余权重。这解释了为什么drop不能统一当成具有固定进展量的一轮。

例子与边界

两轮到达一个边界最小点

在概率单纯形 $C=\{x\in\mathbb R^3:x_i\ge0,\sum x_i=1\}$ 上，令

f(x)=\frac12\|x-a\|^2, \qquad a=(4/5,1/2,-3/10),\qquad x_0=(1/3,1/3,1/3). \tag{5}

原子为 $e_1,e_2,e_3$ ，初始权重各 $1/3$ ， $L=1$ 。梯度为 $(-7/15,-1/6,19/30)$ ，与 $x_0$ 内积为零。因此 $s=e_1,v=e_3$ ， $G=7/15,A=19/30$ ，应选away。

方向 $d=(1/3,1/3,-2/3)$ 有 $\|d\|^2=2/3$ ，未截短步长为 $19/20$ ；权重只允许 $(1/3)/(2/3)=1/2$ 。执行 $\gamma=1/2$ 后， $e_3$ 权重归零，另外两个变为 $1/2$ ：

x_1=(1/2,1/2,0).

第二轮梯度 $(-3/10,0,3/10)$ ， $G=A=3/20$ 。按并列规则选FW， $d=(1/2,-1/2,0)$ ，故 $\gamma=(3/20)/(1/2)=3/10$ ，得到

x_2=(13/20,7/20,0).

此时梯度为 $(-3/20,-3/20,3/10)$ ，最小原子价格与当前加权价格同为 $-3/20$ ，所以 $G=0$ 。最优值为 $27/400$ 。三轮检查中的目标与gap分别是

\begin{array}{c|ccc} &x_0&x_1&x_2\\\hline f&97/300&9/100&27/400\\ G&7/15&3/20&0 \end{array}

三原子单纯形上的away删原子与随后FW更新，右侧列出每轮支持权重 — 远离步的几何与权重账

图中第一步是drop，第二步是good。目标下降与支持缩小分别有各自的计算依据，不能只凭某个坐标显示为零就宣布全局最优。

表示上限可能早于几何边界

取正方形原子 $(0,0),(1,0),(1,1),(0,1)$ ，权重为 $(1/10,1/5,1/2,1/5)$ ，得到 $x=(7/10,7/10)$ 。对线性目标 $f(x)=-x_1-x_2$ ，away原子是 $v=(0,0)$ ， $A=7/5$ ，大于FW gap $3/5$ 。

当前表示允许 $\gamma_{\max}=1/9$ ，所以drop后位置为 $(7/9,7/9)$ ，仍在正方形内部。沿同一几何射线其实能走到 $\gamma=3/7$ 才碰到 $(1,1)$ ，但超过 $1/9$ 会使原来 $(0,0)$ 的权重为负。若想继续走，必须先找另一份非负表示；本算法没有假定拥有这样的额外子程序。

不能只看away gap停止

当 $S$ 只有一个原子时， $A=0$ 恒成立，原问题却未必最优。例如在式(5)从 $e_3$ 出发，away gap为零，但FW方向仍能大幅降低目标。停止量必须是全域线性oracle给的 $G$ ，不是只在当前支持内搜索得到的 $A$ 。

若oracle近似，需像普通FW一样给可信误差预算，不能把一个随意候选的线性差当成精确gap。若目标非凸， $G=0$ 一般只是一阶可行性信息，失去全局目标差证书；本页的收敛预算也随之失效。

推论与应用

good步的完整函数值界

令 $h_t=f(x_t)-f^*$ 。取正数 $R$ 作为 $C$ 直径的有效上界，并令

C_0=\max\{G(x_0),LR^2\}>0.

如果初始gap已经为零，直接结束。否则 $h_t\le h_0\le G(x_0)\le C_0$ ，因为每步目标不增。两种方向都有 $\|d\|\le R$ ，且所选下降量 $g\ge G\ge h_t$ 。

对于未触上限的步，式(4)给

h_t-h_{t+1}\ge\frac{g^2}{2L\|d\|^2} \ge\frac{h_t^2}{2LR^2}.

对FW分支若截到 $\gamma=1$ ，则 $g\ge L\|d\|^2$ ，式(4)给下降至少 $g/2\ge h_t/2$ 。因此每个good步都满足

h_{t+1}\le h_t-\frac{h_t^2}{2C_0}. \tag{6}

若尚未达到零误差，取倒数并用 $1/(1-u)\ge1+u$ 可得

\frac1{h_{t+1}}\ge\frac1{h_t}+\frac1{2C_0}.

drop期间 $h$ 不增，所以倒数也不减。若前 $t$ 次更新共有 $N_t$ 个good步，求和得到

h_t\le\frac{2C_0}{N_t+2}. \tag{7}

中途误差为零时后续结论自动成立。式(7)控制目标差，不是给每个末点的 $G(x_t)$ 同样大小的上界；实际停止仍重算gap。

drop次数为什么受控

记初始支持大小为 $s_0\ge1$ ，前 $t$ 步的away-drop数为 $D_t$ 。每次这样的drop恰删一个原子；只有FW步能加入新原子，且一次至多加一个，所以加入次数不超过 $N_t$ 。FW一步到顶点可能再删去其他原子，这只会减少可供未来删除的库存。由于支持始终非空，

D_t\le N_t+s_0-1, \qquad N_t\ge\max\left\{0,\left\lceil\frac{t-s_0+1}{2}\right\rceil\right\}. \tag{8}

从单个顶点启动才可直接说good至少占一半。若初始支持很大，前面可以连续删原子，必须保留 $s_0-1$ 这一项。

成本与更强结论的范围

每轮除梯度和线性oracle外，扫描 $s=|S|$ 个显式 $d$ 维原子需 $O(sd)$ 时间，更新点需 $O(d)$ 、权重需 $O(s)$ ；保存原子和权重需 $O(sd+s)$ 。若全部 $V$ 都显式扫描，线性oracle本身为 $O(|V|d)$ 。稀疏或结构化原子可降低成本，但应按其实际接口重计。

凸性与光滑性已足以给式(7)–(8)。在强凸目标和有限多面体上，还可以用金字塔宽度等几何常数证明更强的线性率；这需要额外的方向—误差比较，不从本页的 $g\ge h$ 自动得到。把“这次成功删掉原子”解释为“以后每轮都会几何加速”也没有依据。

参考资料

Simon Lacoste-Julien、Martin Jaggi，On the Global Linear Convergence of Frank–Wolfe Optimization Variants，NeurIPS2015，Algorithm1、§§1–2.2、Theorem1，PDF pp.2–6。本文明确选择短步长、允许一般初始支持，并独立给出相应次线性预算；不省略原文线性率的几何常数。

形式陈述 ​

输入、方向与权重更新 ​

可行性为什么依赖当前表示 ​

下降量怎样支付 ​

两轮到达一个边界最小点 ​

表示上限可能早于几何边界 ​

不能只看away gap停止 ​

good步的完整函数值界 ​

drop次数为什么受控 ​

成本与更强结论的范围 ​

反向链接