外梯度法对于非凸优化的加速
Published:
Paper Reading: Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism.
在近期的系列blog中，我们介绍了 外梯度法 作为求解general变分不等式的一个poweful的框架，以及该算法 在凸优化中的最优加速。 而本文将阅读一篇新的文章，给出关于非凸优化中的加速结果。
正式地，我们考虑如下问题：
\[\begin{align*} \min_{x \in \mathbb{R}^d} f(x). \end{align*}\]我们假设函数具有Lipschitz连续的梯度和Hesisan，也即：
\[\begin{align*} \Vert \nabla f(x) - \nabla f(x') \Vert \le& L_1 \Vert x - x' \Vert, \quad x,x' \in \mathbb{R}^d.\\ \Vert \nabla^2 f(x) - \nabla^2 f(x') \Vert \le& L_2 \Vert x - x' \Vert, \quad x,x' \in \mathbb{R}^d. \end{align*}\]但与上一篇blog所不同，我们并不假设函数的凸性。此时由于凸性的缺失，全局极小值将不能在多项式时间内找到。我们遵循前人的工作，退而求其次寻找一个 $\epsilon$-驻点，也即满足 $\Vert \nabla f(x) \Vert \le \epsilon$ 的点 $x$.
Online-to-Nonconvex Conversion (Smooth Setting)
我们曾经在介绍 非光滑非凸优化的最优随机算法 的时候，介绍过一个称为 Online-to-Nonconvex Conversion 的技术，这里我们使用一个类似的技术用于光滑优化，但是需要一些微小的改动。
在这个框架中，算法每次需要选则一个方向 $\Delta_n$, 然后环境会更新 $x_n = x_{n-1} + \Delta_n$ 并且计算 $w_n = \frac{1}{2} (x_n + x_{n-1})$, 然后返回损失 $\ell_n(\Delta_n) = \langle \nabla f(w_n) , \Delta_n\rangle$. 下面我们会证明，如果这个在线优化问题的遗憾界比较小，那么算法可以识别出一个驻点。
首先，使用代数基本定义以及Taylor展开，我们可以得到
\[\begin{align*} &f(x_n) - f(x_{n-1})\\ =& \left \langle \int_0^1 \nabla f(x_{n-1} + s \Delta_n) {\rm d} s, \Delta_n \right \rangle \\ =& \langle \nabla f(w_n), \Delta_n \rangle + \left \langle \int_0^1 \nabla f(x_{n-1} + s \Delta_n) {\rm d} s - \nabla f(w_n), \Delta_n \right \rangle \\ \le& \langle \nabla f(w_n), \Delta_n \rangle + \left \Vert \int_0^1 \nabla f(x_{n-1} + s \Delta_n) {\rm d} s - \nabla f(w_n) \right \Vert \Vert \Delta_n \Vert \\ =& \langle \nabla f(w_n), \Delta_n \rangle + \left \Vert \int_0^1 (\nabla f(x_{n-1} + s \Delta_n) {\rm d} s - \nabla f(w_n) - \nabla^2 f(w_n) (s -1/2) \Delta_n) {\rm d} s \right \Vert \Vert \Delta_n \Vert \\ \le& \int_0^1 \frac{L_2}{2} \Vert \Delta_n \Vert^2 (s-1/2)^2 {\rm d} s = \frac{L_2 D^2}{48}, \end{align*}\]其中我们假设 $\Vert \Delta_n \Vert \le D$ 对任意的 $n$ 成立。这也将在算法中通过投影强制保证。
对于任意的向量 $u$, 我们使用上面的不等式，并且递推 $T$ 个迭代，可以得到
\[\begin{align*} f(x_T) - f(x_0) \le \sum_{n=1}^T \langle \nabla f(w_n), \Delta_n - u \rangle + \sum_{n=1}^T \langle \nabla f(w_n),u \rangle + \frac{L_2 T D^2}{48}. \end{align*}\]那么，选取 $u = -D (\sum_{n=1}^T \nabla f(w_n)) / \Vert \sum_{n=1}^T \nabla f(w_n) \Vert$, 就可以进一步得到
\[\begin{align*} \left \Vert \frac{1}{T} \sum_{n=1}^T \nabla f(w_n) \right \Vert \le \frac{f(x_0) - f(x_T)}{DT} + \frac{1}{DT} \sum_{n=1}^T \langle g_n, \Delta_n - u \rangle + \frac{L_2 D^2}{48}. \end{align*}\]这可以认为是一个二阶光滑下的梯度法的下降引理。值得注意的是，事实上左端项并不是可以一个点的梯度的形式，但是我们可以进一步证明，这与平均点的梯度相差很小。我们定义 $\bar w = \sum_{n=1}^T w_n / T$. 那么，可以证明
\[\begin{align*} & \left \Vert \frac{1}{T} \sum_{n=1}^T \nabla f(w_n) - \nabla f(\bar w) \right \Vert \\ =& \left \Vert \frac{1}{T} \sum_{n=1}^T (\nabla f(w_n) - \nabla f(\bar w) - \nabla^2 f(\bar w) (w_n - \bar w) ) \right \Vert \\ \le& \frac{L_2}{2T} \sum_{n=1}^T \Vert w_n - \bar w \Vert^2 \le \frac{L_2 T^2 D^2}{2}, \end{align*}\]最后一步使用了 $\Vert w_n - \bar w \Vert \le TD$, 这可以通过 $w_n$ 定义以及每部的更新量小于等于 $D$ 得到。合起来，我们就得到了下面的不等式
\[\begin{align*} \Vert \nabla f(\bar w) \Vert \le \frac{f(x_0) - f(x_T)}{DT} + \frac{1}{DT} \sum_{n=1}^T \langle \nabla f(w_n), \Delta_n - u \rangle + \frac{L_2 D^2}{48} + \frac{L_2 T^2 D^2}{2}. \end{align*}\]Hint Construction
上式中唯一还没有被很好的控制住的只有内积项，其正好也是一个遗憾界 ${\rm Reg}(u) := \langle \nabla f(w_n), \Delta_n - u \rangle$. 根据之前关于 外梯度法 的分析，为了得到一个对于外梯度法好的遗憾界，只需要选择合适的hint满足条件：
\[\begin{align*} \eta^2 \Vert \nabla f(w_n) - h_n \Vert^2 \le \frac{1}{2} \Vert \Delta_n - v_n \Vert^2 + \frac{1}{4} \Vert v_{n+1} - \Delta_n \Vert^2, \end{align*}\]其中 $v_n$ 为外梯度法中引入的对偶变量。由此启发，我们设计如下的hint函数
\[\begin{align*} h_n = \nabla f(x_n + \Delta_{n-1}/2). \end{align*}\]那么可以证明这个函数有如下的近似条件
\[\begin{align*} \Vert \nabla f(w_n) - h_n \Vert \le \frac{L_1}{2} \Vert \Delta_{n} - \Delta_{n-1} \Vert \le L_1 (\Vert \Delta_n - v_n \Vert + \Vert v_n - \Delta_{n-1} \Vert). \end{align*}\]可以观察到，如果选择 $\eta = 1/(2\sqrt{2} L_1)$, 那么这已经非常接近于我们所需要的松弛条件，除了第二项的下标偏移了1. 但这并不会造成太大的影响，因为我们可以用类似裂项相消的方式处理，最终会得到遗憾界有如下保证：
\[\begin{align*} {\rm Reg}(u) = \mathcal{O}( L_1 D^2). \end{align*}\]我们将这个遗憾界回代进入之前的不等式，就可以得到
\[\begin{align*} \Vert \nabla f(\bar w) \Vert \le \frac{f(x_0) - f(x_T)}{DT} + \mathcal{O}(L_1 D / T + L_2 T^2 D^2). \end{align*}\]最后，我们使用相同的流程进行 $K$ 个epoch，然后求和起来，并且定义 $N =KT$，就可以得到
\[\begin{align*} \frac{1}{K}\Vert \nabla f(\bar w^k) \Vert \le \frac{f(x_0) - f(x_N)}{DN} + \mathcal{O}(L_1 D / T + L_2 T^2 D^2). \end{align*}\]选择最优的 $T$, 可以得到
\[\begin{align*} \frac{1}{K}\Vert \nabla f(\bar w^k) \Vert \le \frac{f(x_0) - f(x_N)}{DN} + \mathcal{O}(L_1^{2/3} L_2^{1/3} D^{4/3}). \end{align*}\]接着选择最优的 $D$, 可以得到
\[\begin{align*} \frac{1}{K}\Vert \nabla f(\bar w^k) \Vert= \mathcal{O}\left( \left( \frac{f(x_0) - f(x_N)}{N} \right)^{4/7} L_1^{2/7} L_2^{1/7} \right). \end{align*}\]换句话说，想要找到一个 $\epsilon$-驻点，算法需要的复杂度为 $N = \mathcal{O}(L_1^{1/2} L_2^{1/4} \epsilon^{-7/4})$. 相较于朴素的梯度下降的 $\mathcal{O}(L_1 \epsilon^{-2})$， 我们在本文所推出的加速外梯度法具有更快的收敛率。
最后，注意到原文并没有采用外梯度法，而是采用了其一个被称为乐观梯度法的变种，但最后的收敛率是一样的。