Stochastic Variance Reduced Extra Gradient
Published:
Paper Reading: Stochastic Variance Reduction for Variational Inequality Methods.
本文考虑求解所谓的变分不等式问题, 也即寻找 $z^\ast$ 满足
\[\begin{align*} \langle F(z^\ast), z - z^\ast \rangle \ge 0, \quad \forall z. \end{align*}\]其中 $F(z)$ 为一个单调算子。选取算子为一个凸函数的梯度场，那么上述问题等价于凸优化问题；选取算子为一个凸-凹函数的梯度下降-上升场，上述问题等价于凸-凹函数的鞍点问题。
假设 $F(z)$ 具有有限和结构，
\[\begin{align*} F(z) = \sum_{i=1}^n F_i(z). \end{align*}\]并且假设每一个分量满足期望下的平均Lipschitz性质
\[\begin{align*} \mathbb{E} \Vert F_i(z) - F_i(z') \Vert^2 \le L^2 \Vert z - z' \Vert^2. \end{align*}\]本文提出如下算法，结合了外梯度法以及方差缩减算法，
\[\begin{align*} \bar z_k &= \alpha z_k + (1- \alpha) w_k \\ z_{k+1/2} &= \bar z_k - \tau F(w_k) \\ \hat F(z_{k+1/2}) &=F(w_k) + F_i(z_{k+1/2}) - F_i(w_k) \\ z_{k+1} &= \bar z_k - \tau \hat F(z_{k+1/2}) \\ w_{k+1} &= \begin{cases} z_{k+1}, & \text{with prob. } 1-\alpha \\ w_k , & \text{with prob. } \alpha. \end{cases} \end{align*}\]在外梯度法的分析框架下，我们知道 对于任意的 $z$, 我们有如下的不等式
\[\begin{align*} &\quad \tau \langle \hat F(z_{k+1/2}), z_{k+1/2} - z \rangle \\ &= \langle \bar z_k - z_{k+1}, z_{k+1/2} - z \rangle \\ &= \langle \bar z_k - z_{k+1}, z_{k+1} - z \rangle + \langle \bar z_k - z_{k+1} , z_{k+1/2} - z_{k+1} \rangle \\ &= \langle \bar z_k - z_{k+1}, z_{k+1} - z \rangle + \langle \bar z_k - z_{k+1/2}, z_{k+1/2} - z_{k+1} \rangle + \langle z_{k+1/2} - z_{k+1}, z_{k+1/2} - z_{k+1} \rangle. \end{align*}\]取期望后得到
\[\begin{align*} &\quad \tau \langle F(z_{k+1/2}), z_{k+1/2} - z \rangle \\ &= \frac{\alpha}{2} \Vert z_k - z \Vert^2 + \frac{1-\alpha}{2} \Vert w_k - z \Vert^2 - {\frac{\alpha}{2} \Vert z_k - z_{k+1} \Vert^2} - {\frac{1-\alpha}{2} \Vert w_k - z_{k+1} \Vert^2} - \frac{1}{2} \Vert z_{k+1} - z \Vert^2 \\ &\quad + {\frac{\alpha}{2} \Vert z_k - z_{k+1} \Vert^2} + {\frac{1-\alpha}{2} \Vert w_k - z_{k+1} \Vert^2} - \frac{\alpha}{2} \Vert z_k - z_{k+1/2} \Vert^2 - \frac{1-\alpha}{2} \Vert w_k - z_{k+1/2} \Vert^2 - \frac{1}{2} \Vert z_{k+1/2} - z_{k+1} \Vert^2 \\ &\quad + \tau^2 \mathbb{E} \Vert \hat F(z_{k+1/2}) - F(w_k) \Vert^2 \\ &\le \frac{\alpha}{2} \Vert z_k - z \Vert^2 + \frac{1-\alpha}{2} \Vert w_k - z \Vert^2 - \frac{1}{2} \Vert z_{k+1} - z \Vert^2 \\ &\quad - \frac{\alpha}{2} \Vert z_k - z_{k+1/2} \Vert^2 - \frac{1-\alpha}{2} \Vert w_k - z_{k+1/2} \Vert^2 - \frac{1}{2} \Vert z_{k+1/2} - z_{k+1} \Vert^2 + \tau^2 L^2 \Vert w_k - z_{k+1/2} \Vert^2 \end{align*}\]根据更新公式，我们又有
\[\begin{align*} \mathbb{E} \Vert w_{k+1} - z \Vert^2 = (1-\alpha) \Vert z_{k+1} - z \Vert^2 + \alpha \Vert w_k - z \Vert^2. \end{align*}\]综合起来我们知道
\[\begin{align*} &\quad \tau \langle F(z_{k+1/2}), z_{k+1/2} - z \rangle \\ &\le \frac{1}{2}(\alpha \Vert z_{k} - z \Vert^2 + \Vert w_{k} - z \Vert^2) - \frac{1}{2}(\alpha \Vert z_{k+1} - z \Vert^2 + \Vert w_{k+1} - z \Vert^2) \\ &\quad - \frac{\alpha}{2} \Vert z_k - z_{k+1/2} \Vert^2 - \left(\frac{1-\alpha}{2} - \tau^2 L^2 \right) \Vert w_k - z_{k+1/2} \Vert^2 - \frac{1}{2} \Vert z_{k+1/2} - z_{k+1} \Vert^2. \end{align*}\]其中左端为Gap 函数。上式收敛需要步长足够小，满足
\[\begin{align*} \tau \le \frac{1}{L }\sqrt{\frac{1-\alpha}{2}}. \end{align*}\]选取 $w_0 = z_0 $, 这蕴含着Gap函数具有如下的收敛率
\[\begin{align*} \frac{1}{K} \sum_{k=0}^{K-1} \langle F(z_{k+1/2}), z_{k+1/2} - z \rangle \le \frac{\Vert z_0 - z \Vert^2}{\tau K} = \frac{\sqrt{2} ~L \Vert z_0 - z \Vert^2}{\sqrt{1-\alpha}} \end{align*}\]考虑到每次的复杂度为 $ (1-\alpha) n +1$. 最终的复杂度为
\[\begin{align*} \mathcal{O} \left( L \Vert z_0 - z \Vert^2 \left( n \sqrt{1-\alpha} + \frac{1}{\sqrt{1-\alpha}} \right) \right) \end{align*}\]选取最优的 $\alpha$ ，也即 $\alpha = 1- 1/n$, 加上初始的复杂度为 $n$, 最终得到 $\epsilon$-最优解需要如下的复杂度
\[\begin{align*} \mathcal{O} \left( n + \frac{\sqrt{n} L}{\epsilon} \right). \end{align*}\]后续的工作也证明了上述的复杂度对于随机一阶算法是最优的。