Universal Parameter-Free GD
Published:
Paper Reading: DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method.
本文研究优化中的基本问题：
\[\min_{x \in X} f(x).\]其中 $f$ 为凸函数, $X$ 为一个闭凸集。对于该问题的两个经典设定为，函数满足 $G$-Lipschitz,
\[\begin{align*} \vert f(x) - f(y) \vert \le G \Vert x - y \Vert. \end{align*}\]或者 $L$-smooth, 也即
\[\begin{align*} \Vert \nabla f(x) - \nabla f(y) \Vert \le L \Vert x - y \Vert. \end{align*}\]本文提出的算法，无需学习率的调整，并且在上述两个问题上都达到最优的收敛率，算法如
\[\begin{align*} \bar r_t &= \max \{ \bar r_{t-1}, \Vert x_t - x_0 \Vert \} \\ v_t &= v_{t-1} + \bar r_{t-1}^2 \Vert \nabla f(x_t) \Vert^2 \\ \eta_t &= \bar r_t^2 / \sqrt{v_t}. \\ x_{t+1} &= \Pi_X(x_t - \eta_t \nabla f(x_t)) \end{align*}\]其中 $\Pi_X$ 表示朝集合 $X$ 的投影。算法初始化 $r_{-1} = r_{\epsilon}$, $v_{-1} = 0$.
在给出主要证明之前，首先给出下面两个技术性的代数引理, 分别对应文章的引理1和引理2.
对于 $0 \le a_0 \le \cdots \le a_t$, 成立
\[\begin{align*} \sum_{k=1}^t \frac{a_k - a_{k-1}}{\sqrt{a_k}} \le 2 (\sqrt{a_t} - \sqrt{a_0}). \end{align*}\]以及
\[\begin{align*} \max_{t \le T} \sum_{i < t } \frac{a_i}{a_t} \ge \frac{1}{\rm e} \left( \frac{T}{\log_+(a_T/ a_0)} -1\right) \end{align*}\]其中 $\log_+ x = \log x +1$.
定义 $d_k = \Vert x_k - x^\ast \Vert$. 根据投影的性质，
\[\begin{align*} d_{k+1}^2 &= \Vert x_{k+1} - x^\ast \Vert^2 \\ &\le \Vert x_k - \eta_k \nabla f(x_k) - x^\ast \Vert^2 \\ &= d_k^2- 2 \eta_k \langle \nabla f(x_k), x_k - x^\ast \rangle + \eta_k^2 \Vert \nabla f(x_k) \Vert^2. \end{align*}\]上式的加权和为
\[\begin{align*} \sum_{k=0}^{t-1} \bar r_{k-1}^2 \langle \nabla f(x_k), x_k - x^\ast \rangle \le \frac{1}{2} \sum_{k=0}^{t-1} \frac{\bar r_k^2}{\eta_k} (d_k^2 - d_{k-1}^2) + \frac{1}{2} \sum_{k=0}^{t-1} \bar r_k^2 \eta_k \Vert \nabla f(x_k) \Vert^2. \end{align*}\]下面分别分析上述两项。定义 $\bar d_t = \max_{k \le t} d_k$.
\[\begin{align*} &\quad \sum_{k=0}^{t-1} \frac{\bar r_k^2}{\eta_k} (d_k^2 - d_{k-1}^2) \\ &= \sum_{k=0}^{t-1} \sqrt{v_k} (d_k^2 - d_{k+1}^2) \\ &= d_0^2 \sqrt{v_0} - d_t^2 \sqrt{v_{t-1}} + \sum_{k=1}^{t-1} d_k^2 (\sqrt{v_k} - \sqrt{v_{k-1}}) \\ &\le \bar d_t \sqrt{v_0} - d_t^2 \sqrt{v_{t-1}} + \bar d_t^2 \sum_{k=1}^{t-1} (\sqrt{v_k} - \sqrt{v_{k-1}}) \\ &= \sqrt{v_{t-1}} ( \bar d_t^2 - d_t^2) \\ &= \sqrt{v_{t-1}}(d_s - d_t) (d_s + d_s) ,\quad \text{for some } s \le t \\ &\le 2 \Vert x_s - x_t \Vert \bar d_t \sqrt{v_{t-1}} \\ &\le 4 \bar r_t \bar d_t \sqrt{v_{t-1}}. \end{align*}\]这就完成了第一项的bound，对于第二项，
\[\begin{align*} &\quad \sum_{k=0}^{t-1} \bar r_k^2 \eta_k \Vert \nabla f(x_k) \Vert^2 \\ &= \sum_{k=0}^{t-1} \frac{\bar r_k^4}{\sqrt{v_k}} \Vert \nabla f(x_k) \Vert^2 \\ &= r_0^2 \sqrt{v_0} + \sum_{k=1}^{t-1} \frac{\bar r_k^4}{\sqrt{v_k}} \Vert \nabla f(x_k) \Vert^2 \\ &\le r_0^2 \sqrt{v_0} + \bar r_t^2 \sum_{k=1}^{t-1} \frac{\bar r_k^2}{\sqrt{v_k}} \Vert \nabla f(x_k) \Vert^2 \\ &= r_0^2 \sqrt{v_0} + \bar r_t^2 \sum_{k=1}^{t-1} \frac{v_k - v_{k-1}}{\sqrt{v_k}} \\ &\le r_0^2 \sqrt{v_0} + 2 \bar r_t^2 (\sqrt{v_{t-1}} - \sqrt{v_0}) \\ &\le 2 \bar r_t^2 \sqrt{v_{t-1}}. \end{align*}\]合起来，并且利用函数的凸性，我们有
\[\begin{align*} \sum_{k=0}^{t-1} \bar r_k^2 (f(x_k ) - f^\ast) \le 2 \bar r_t (\bar d_t + \bar r_t) \sqrt{v_{t-1}}. \end{align*}\]下面我们根据上式给出关于两个不同设定下面的收敛率。
对于非光滑情况，我们知道梯度的上界为 $G$, 这意味着
\[\begin{align*} v_{t-1} \le \bar r_t^2 G^2 T. \end{align*}\]记 $S= \sum_{k=0}^{T-1} \bar r_k^2$, 我们有
\[\begin{align*} \frac{1}{S} \sum_{k=0}^{t-1} \bar r_k^2 (f(x_k) - f^\ast) \le \frac{4 D G \sqrt{T}}{\sum_{k=0}^{t-1} \bar r_k^2 / \bar r_t^2}. \end{align*}\]根据引理2我们知道存在某个 $t \in [T]$ 满足
\[\begin{align*} \frac{1}{S} \sum_{k=0}^{t-1} \bar r_k^2 (f(x_k) - f^\ast) = \mathcal{O} \left( \frac{G D }{\sqrt{T}} \log_+ \left( \frac{D}{\bar r_0} \right) \right). \end{align*}\]下面考虑光滑的情况，利用
\[\begin{align*} v_{t-1} = \sum_{k=0}^{t-1} \bar r_k^2 \Vert \nabla f(x_k) \Vert^2 \le 2 L \sum_{k=0}^{t-1} \bar r_k^2 (f(x_k) - f^\ast ). \end{align*}\]将非光滑情况的证明中的 $v_{t-1}$ 的上界替换为上式，得到关于 $f(x_k) - f^\ast$ 的方程，最终同样利用引理2就得到了
\[\begin{align*} \frac{1}{S} \sum_{k=0}^{t-1} \bar r_k^2 (f(x_k) - f^\ast) = \mathcal{O} \left( \frac{L D^2 }{T} \log_+ \left( \frac{D}{\bar r_0} \right) \right). \end{align*}\]这就完成了文章的证明。