外梯度法求解变分不等式简证
Published:
本文给出对于外梯度法求解变分不等式问题的简要证明。
Problem Setup
给定一个算子 $F$, 文章关注于求解如下的变分不等式问题, 关注于寻找解 $z^\ast$ 满足
\[\begin{align*} \langle F(z), z^\ast - z \rangle \le 0, \quad, \forall z \in Z. \end{align*}\]我们假设算子是单调的，也即满足
\[\begin{align*} \langle F(z) - F(z'), z-z' \rangle \ge 0, \quad \forall z, z' \in Z. \end{align*}\]变分不等式推广了优化问题地最优一阶条件（取算子为梯度算子），而算子的单调性则推广了函数的凸性。
Algorithm
考虑如下的外梯度法，
\[\begin{align*} z_{t} &= \Pi_Z (v_t - \eta h_t) \\ v_{t+1} &= \Pi_Z (v_t - \eta g_t), \end{align*}\]我们会选取 $h_t =F(v_t)$ 以及 $g_t = F(z_t)$.
我们假设 $F$ 为 $L$-Lipschitz 算子，也即
\[\begin{align*} \Vert F(z) - F(z') \Vert \le L \Vert z - z' \Vert, \quad z,z' \in Z. \end{align*}\]上面的条件意味着 $\Vert h_t -g_t \Vert \le L \Vert z_t - v_t \Vert$. 在很多文献中，也会将 $h_t$ 称为一个hint，我们会证明只要 $h_t$ 以及 $g_t = F(z_t)$ 满足上式, 也即hint和真实梯度比较接近，算法可以在 $\mathcal{O}(\epsilon^{-1})$ 次迭代内寻找到一个 $\epsilon$-近似解。注意到虽然这里我们简单地选取 $h_t =F(v_t)$, 在很多其他的应用中，我们也会精心地设计hint，达到好的收敛。
我们算法的目标是最小化下面的Regret:
\[\begin{align*} {\rm Reg} (u):= \sum_{t=0}^{T-1} \langle g_t, z_t - u \rangle \end{align*}\]如果对于任意的 $u \in Z$, 我们可以给出这个遗憾界的上界，那么这意味着我们只要输出平均点 $\bar z_T = \sum_{t=0}^{T-1} z_t / T$, 就是一个近似最优解，这是因为
\[\begin{align*} \langle F(u), \bar z_t - u \rangle = \frac{\sum_{t=0}^{T-1} \langle F(u), z_t - u \rangle}{T} \le \frac{ {\rm Reg}(u) }{T} \end{align*}\]下面我们分析算法所产生的遗憾界。
Analysis
首先根据迭代中第二步的最优条件，有
\[\begin{align*} 0 \le& \langle \eta g_t +v_{t+1}- v_t, u - v_{t+1} \rangle, \quad \forall u \in Z \end{align*}\]同样地，根据迭代中第一步的最优条件，有
\[\begin{align*} 0 \le& \langle \eta h_t + z_{t}- v_t, u' - z_t \rangle, \quad \forall u' \in Z. \end{align*}\]因此，对于任意的 $u \in Z$, 有
\[\begin{align*} & \eta \langle g_t, z_{t} - u \rangle \\ = & \eta \langle g_t, v_{t+1} - u \rangle + \eta \langle g_t, z_{t} - v_{t+1} \rangle \\ =& \eta \langle g_t, v_{t+1} - u \rangle + \eta \langle h_t, z_{t} - v_{t+1} \rangle + \eta \langle g_t - h_t, z_{t} - v_{t+1} \rangle \\ \le & \langle v_{t+1} - v_t , u - v_{t+1} \rangle + \langle z_{t} - v_t , v_{t+1} - z_{t} \rangle + \eta \langle g_t - h_t, z_{t} - v_{t+1} \rangle \end{align*}\]下面，利用恒等式 $\langle a, b \rangle = \frac{1}{2} \Vert a+b \Vert^2- \frac{1}{2} \Vert a \Vert^2 - \frac{1}{2} \Vert b \Vert^2$ 以及Young不等式 $\eta \langle a, b\rangle \le\frac{\eta^2}{2} \Vert a\Vert^2 + \frac{1}{2} \Vert b \Vert^2$, 我们可以进一步得到
\[\begin{align*} &\eta \langle g_t, z_{t} - u \rangle \\ \le & \frac{1}{2} \Vert u-v_t \Vert^2 - \frac{1}{2} \Vert v_{t+1} - v_t \Vert^2 - \frac{1}{2} \Vert u-v_{t+1} \Vert^2 \\ &+ \frac{1}{2} \Vert v_{t+1}-v_t \Vert^2 - \frac{1}{2} \Vert z_t - v_t \Vert^2 - \frac{1}{2} \Vert v_{t+1} - z_t \Vert^2 \\ &+ \eta^2 \Vert g_t - h_t \Vert^2 + \frac{1}{2} \Vert v_{t+1} - z_t \Vert^2. \end{align*}\]事实上可以发现很多项都会正好被抵消掉，然后再利用光滑性条件 $\Vert h_t -g_t \Vert \le L \Vert z_t - v_t \Vert$ 并且选择步长 $\eta \le 1/ (\sqrt{2}L)$, 整理后可以得到
\[\begin{align*} \eta \langle g_t, z_{t} - u \rangle \le \frac{1}{2} \Vert u-v_t \Vert^2 - \frac{1}{2} \Vert u-v_{t+1} \Vert^2 \end{align*}\]求和后就说明了遗憾界是 $O(1)$, 那么根据之前的分析，取平均点后收敛率就是 $O(1/T)$。 换句话说，找到一个 $\epsilon$-近似解的复杂度为 $O(\epsilon^{-1})$.
之前也写过关于外梯度法的一些推广结果，例如 方差缩减变种 以及 自适应变种，作为本文推导的一个进阶。
最后，我们给一个remark。上面的证明中其实还有一些负项被直接丢弃掉了，容易看出hint的近似性放松为如下条件时相同的结果仍然成立
\[\begin{align*} \eta^2 \Vert g_t - h_t \Vert^2 \le \frac{1}{2} \Vert z_t - v_t \Vert^2 + \frac{1}{4} \Vert v_{t+1} - z_t \Vert^2. \end{align*}\]这个放松的条件在很多时候最近的工作里面也经常派上用场。