UniXGrad
Published:
Paper Reading: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization
我们在上一篇文章中介绍了用于变分不等式的外梯度算法，可以在 $O(\epsilon^{-1})$ 的复杂度内寻找到一个 $\epsilon$-近似解。本文介绍在凸优化中，可以进一步加速得到 $O(\epsilon^{-1/2})$ 的复杂度。
我们考虑如下经典的凸优化问题：
\[\begin{align*} \min_{x \in X} f(x). \end{align*}\]外梯度法可以最小化遗憾上界，但我们需要一个conversion，将遗憾上界以及函数值的下降联系起来。给定算法访问的点 $w_1,\cdots, w_t$, 我们会定义一个加权平均 $x_t = \sum_{i=0}^{t} a_i w_i / A_t$, 其中 $A_t = \sum_{i=0}^{t} a_t$. 下面我们给出这个加权后的序列 $x_t,\dots,x_T$ 的收敛与加权后的Regret具有如下的关系：
\[\begin{align*} f(x_T) - f(x^\ast) \le \frac{\langle a_t \nabla f(x_t), w_t - x^\ast \rangle}{A_T} := \frac{R_T(x^\ast) }{A_T}. \end{align*}\]这被称为anytime online-to-batch conversion。有了这个关系，我们的问题就转化使得加权后的遗憾值有界的前提下，序列 $a_0,\cdots,a_t$ 增长最快是多少，而这个增长速率就决定了算法的收敛率。下面我们首先证明上面这个关系式：我们从函数的凸性开始出发：
\[\begin{align*} &\sum_{t=0}^{T-1} a_t (f(x_t) - f(x^\ast)) \\ \le& \sum_{t=0}^{T-1} a_t \langle \nabla f(x_t), x_t - x^\ast \rangle \\ =& \sum_{t=0}^{T-1} a_t \langle \nabla f(x_t), x_t - w_t \rangle + \sum_{t=0}^{T-1} a_t \langle \nabla f(x_t), w_t - x^\ast \rangle \\ =& \sum_{t=0}^{T-1} A_{t-1} \langle \nabla f(x_t), x_{t-1} -x_t \rangle + R_T(x^\ast), \end{align*}\]其中最后一步使用了恒等式 $a_t (x_t- w_t)=A_{t-1}(x_{t-1} -x_t)$, 这是由于 $A_t x_t= A_{t-1} x_{t-1} + a_t w_t$. 下面我们再次利用函数的凸性，进一步得到
\[\begin{align*} \sum_{t=0}^{T-1} a_t (f(x_t) - f(x^\ast)) \le \sum_{t=0}^{T-1} A_{t-1} ( f(x_{t-1}) - f(x_t)) + R_T(x^\ast), \end{align*}\]重新排列，我们发现
\[\begin{align*} \sum_{t=0}^{T-1} A_t (f(x_t) - f(x^\ast)) \le \sum_{t=0}^{T-1} A_{t-1} (f(x_{t-1}) - f(x^\ast)) + R_T(x^\ast). \end{align*}\]出现一个裂项相消数列的形式，我们使得 $A_0 = a_t = 0$, 就可以得到想要证明的式子
\[\begin{align*} f(x_T) - f(x^\ast) \le \frac{R_T(x^\ast) }{A_T}. \end{align*}\]下面我们考虑如何设计算法最小化遗憾界。这可以看作一个在线学习问题，算法每次访问一个点 $w_t$, 然后环境计算出加权平均点 $x_t = \sum_{i=0}^{t} a_i w_i / A_t$， 据此计算得到 $w_t$的损失 $\langle a_t \nabla f(x_t), w_t \rangle$. 回顾上一篇文章中正好介绍的外梯度算法，只要构造出一个hint满足条件
\[\begin{align*} a_t \eta \Vert h_t - g_t \Vert \le \Vert w_t - v_t \Vert /2, \quad {\rm where} \quad g_t = \nabla f(x_t) \end{align*}\]那么迭代
\[\begin{align*} w_{t} &= \Pi_Z (v_t - \eta a_t h_t) \\ v_{t+1} &= \Pi_Z (v_t - \eta a_t g_t), \end{align*}\]就可以给出一个 $O(1)$ 的遗憾界，其中 $v_t$ 可以看作是 $w_t$的一个逼近序列。 Hint的目标是最好地预测未来的梯度值 $\nabla f(x_t)$, 注意到 $x_t = \sum_{i=0}^{t} a_i w_i / A_t$ 依赖于还没有访问的 $w_t$，我们考虑将其用 $v_t$ 来代替，得到如下的hint设计：
\[\begin{align*} z_t = \frac{\sum_{i=0}^{t-1} a_i w_i + a_t v_t}{A_t}, \quad h_t = \nabla f(z_t). \end{align*}\]那么我们知道
\[\begin{align*} a_t \eta \Vert h_t -g_t \Vert \le a_t^2 L \eta \Vert w_t - v_t \Vert / A_t. \end{align*}\]我们选取数列 $a_t = t$, 那么只需要选择 $\eta \le 1/(2L)$ 就可以满足条件。最后我们知道 $A_t = \Omega(t^2)$, 这意味着最后的收敛率为
\[\begin{align*} f(x_T) - f(x^\ast) \le \frac{R_T(x^\ast) }{A_T} = O(1/T^2). \end{align*}\]换句话说，找到一个 $\epsilon$-近似解的复杂度为 $O(\epsilon^{-1/2})$, 这与 加速梯度法 的结果相匹配，达到最优。