Gradient-Variation Online Adaptivity for Accelerated Optimization with Holder Smoothness - 技巧浅析

发表于 本文字数： 11k 阅读时长 ≈ 10 分钟
https://arxiv.org/abs/2511.02276

这篇论文的核心在于“利用负项，减少讨论”。

Online-to-Batch Conversion

老生常谈的东西，约等于加权Jensen不等式。

L(xˉT)−L(x⋆)=L(1α1:T∑t=1Tαtxt)−L(x⋆)≤1α1:T∑t=1Tαt(L(xt)−L(x⋆))≤1α1:TE[∑t=1Tαt⟨∇ℓt(xt),xt−x⋆⟩]. \begin{align*} \mathcal{L} (\bar{\mathbf{x}}_T) - \mathcal{L} (\mathbf{x}_\star) =& \mathcal{L} \left(\frac{1}{\alpha_{1 : T}} \sum_{t=1}^T \alpha_t \mathbf{x}_t \right) - \mathcal{L} (\mathbf{x}_\star) \\ \le& \frac{1}{\alpha_{1 : T}} \sum_{t=1}^T \alpha_t \left( \mathcal{L}(\mathbf{x}_t) - \mathcal{L}(\mathbf{x}_\star) \right) \\ \le& \frac{1}{\alpha_{1 : T}} \mathbb{E} \left[ \sum_{t=1}^T \alpha_t \langle \nabla \ell_t(\mathbf{x}_t), \mathbf{x}_t - \mathbf{x}_\star \rangle \right]. \end{align*}

目前更多的是采用 Ashock Cutkosky, 2019 的 Stabilized Online-to-Batch Conversion 。

online-to-batch

这里不采用图中的符号，记 xˉt=∑s=1tαsxsα1:t\bar{\mathbf{x}}_t = \frac{\sum_{s=1}^t \alpha_s \mathbf{x}_s}{\alpha_{1 : t}} 。这种方法的核心在于发现

α1:txˉt=α1:t−1xˉt−1+αtxt,αt(xˉt−xt)=α1:t−1(xˉt−1−xˉt). \begin{align*} \alpha_{1:t} \bar{\mathbf{x}}_t =& \alpha_{1:t-1} \bar{\mathbf{x}}_{t-1} + \alpha_t \mathbf{x}_t, \\ \alpha_t (\bar{\mathbf{x}}_t - \mathbf{x}_t) =& \alpha_{1:t-1} (\bar{\mathbf{x}}_{t-1} - \bar{\mathbf{x}}_t). \end{align*}

结合Jensen不等式

α1:tL(xˉt)≤α1:t−1L(xˉt−1)+αtL(xt),αt(L(xˉt)−L(xt))≤α1:t−1(L(xˉt−1)−L(xˉt)). \begin{align*} \alpha_{1:t} \mathcal{L}(\bar{\mathbf{x}}_t) \le& \alpha_{1:t-1} \mathcal{L}(\bar{\mathbf{x}}_{t-1}) + \alpha_t \mathcal{L}(\mathbf{x}_t), \\ \alpha_t (\mathcal{L}(\bar{\mathbf{x}}_t) - \mathcal{L}(\mathbf{x}_t)) \le& \alpha_{1:t-1} (\mathcal{L}(\bar{\mathbf{x}}_{t-1}) - \mathcal{L}(\bar{\mathbf{x}}_t)). \end{align*} ∑t=1Tαt(L(xˉt)−L(x⋆))=∑t=1Tαt(L(xˉt)−L(xt))+∑t=1Tαt(L(xt)−L(x⋆))=∑t=1Tαt(L(xˉt)−L(xt))+E[RTα]≤∑t=1Tα1:t−1(L(xˉt−1)−L(xˉt))+E[RTα]=∑t=1T−1αtL(xˉt)−α1:T−1L(xˉT)+E[RTα],L(xˉT)−L(x⋆)≤E[RTα]α1:T. \begin{align*} \sum_{t=1}^T \alpha_t \left( \mathcal{L}(\bar{\mathbf{x}}_t) - \mathcal{L}(\mathbf{x}_\star) \right) =& \sum_{t=1}^T \alpha_t \left( \mathcal{L}(\bar{\mathbf{x}}_t) - \mathcal{L}(\mathbf{x}_t) \right) + \sum_{t=1}^T \alpha_t \left( \mathcal{L}(\mathbf{x}_t) - \mathcal{L}(\mathbf{x}_\star) \right) \\ =& \sum_{t=1}^T \alpha_t \left( \mathcal{L}(\bar{\mathbf{x}}_t) - \mathcal{L}(\mathbf{x}_t) \right) + \mathbb{E} \left[ R_T^\alpha \right] \\ \le& \sum_{t=1}^T \alpha_{1:t-1} \left( \mathcal{L} \left(\bar{\mathbf{x}}_{t-1} \right) - \mathcal{L}(\bar{\mathbf{x}}_t) \right) + \mathbb{E} \left[ R_T^\alpha \right] \\ =& \sum_{t=1}^{T-1} \alpha_t \mathcal{L} \left(\bar{\mathbf{x}}_{t} \right) - \alpha_{1:T-1} \mathcal{L} \left(\bar{\mathbf{x}}_{T} \right) + \mathbb{E} \left[ R_T^\alpha \right], \\ \mathcal{L} \left(\bar{\mathbf{x}}_{T} \right) - \mathcal{L} \left(\mathbf{x}_\star \right) \le& \frac{\mathbb{E} \left[ R_T^\alpha \right]}{\alpha_{1:T}}. \end{align*}

在这种情况下可以利用 L\mathcal{L} 的特殊性质。比如，如果 L\mathcal{L} 是λ\lambda-strongly convex 的，有

α1:tL(xˉt)≤α1:t−1L(xˉt−1)+αtL(xt)−λ2α1:t−1αtα1:t∥xˉt−xt∥2,αt(L(xˉt)−L(xt))≤α1:t−1(L(xˉt−1)−L(xˉt))−λ2α1:t−1αtα1:t∥xˉt−xt∥2,αt(L(xˉt)−L(xt))≤α1:t−1(L(xˉt−1)−L(xˉt))−λ2α1:t−13α1:tαt∥xˉt−xˉt−1∥2. \begin{align*} \alpha_{1:t} \mathcal{L}(\bar{\mathbf{x}}_t) \le& \alpha_{1:t-1} \mathcal{L}(\bar{\mathbf{x}}_{t-1}) + \alpha_t \mathcal{L}(\mathbf{x}_t) - \frac{\lambda}{2} \frac{\alpha_{1:t-1} \alpha_t}{\alpha_{1:t}} \| \bar{\mathbf{x}}_t - \mathbf{x}_t \|^2, \\ \alpha_t (\mathcal{L}(\bar{\mathbf{x}}_t) - \mathcal{L}(\mathbf{x}_t)) \le& \alpha_{1:t-1} (\mathcal{L}(\bar{\mathbf{x}}_{t-1}) - \mathcal{L}(\bar{\mathbf{x}}_t)) - \frac{\lambda}{2} \frac{\alpha_{1:t-1} \alpha_t}{\alpha_{1:t}} \| \bar{\mathbf{x}}_t - \mathbf{x}_t \|^2, \\ \alpha_t (\mathcal{L}(\bar{\mathbf{x}}_t) - \mathcal{L}(\mathbf{x}_t)) \le& \alpha_{1:t-1} (\mathcal{L}(\bar{\mathbf{x}}_{t-1}) - \mathcal{L}(\bar{\mathbf{x}}_t)) - \frac{\lambda}{2} \frac{\alpha_{1:t-1}^3}{\alpha_{1:t} \alpha_t} \| \bar{\mathbf{x}}_t - \bar{\mathbf{x}}_{t-1} \|^2. \end{align*}

因此

L(xˉT)−L(x⋆)≤E[RTα]α1:T−1α1:T∑t=1Tλ2α1:t−13α1:tαt∥xˉt−xˉt−1∥2. \mathcal{L} \left(\bar{\mathbf{x}}_{T} \right) - \mathcal{L} \left(\mathbf{x}_\star \right) \le \frac{\mathbb{E} \left[ R_T^\alpha \right]}{\alpha_{1:T}} - \frac{1}{\alpha_{1:T}} \sum_{t=1}^T \frac{\lambda}{2} \frac{\alpha_{1:t-1}^3}{\alpha_{1:t} \alpha_t} \| \bar{\mathbf{x}}_t - \bar{\mathbf{x}}_{t-1} \|^2.

Reduce smooth parameter with adaptive learning rate

完整流程详见 Theorem 1 及其证明。在算 RTR_T 时会遇到

ηt=DAt,AT=∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt−1)∥2,RT≲DAT−∑t=2T1ηt+1∥xt−xt−1∥2=DAT−∑t=2TAtD∥xt−xt−1∥2. \begin{align*} \eta_t =& \frac{D}{\sqrt{A_t}}, \\ A_T =& \| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2, \\ R_T \lesssim& D \sqrt{A_T} - \sum_{t=2}^T \frac{1}{\eta_{t+1}} \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2 \\ =& D \sqrt{A_T} - \sum_{t=2}^T \frac{\sqrt{A_t}}{D} \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2. \end{align*}

简单假设 ftf_t 是 LL-smooth 的。那么

AT=∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt−1)∥2=∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt)+∇ft−1(xt)−∇ft−1(xt−1)∥2≲∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt)∥2+∑t=2T∥∇ft−1(xt)−∇ft−1(xt−1)∥2≲∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt)∥2+L2∑t=2T∥xt−xt−1∥2,AT≲∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt)∥2+L2∑t=2T∥xt−xt−1∥2≲∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt)∥2+L∑t=2T∥xt−xt−1∥2≲∥∇f1(x1)∥2+∑t=2T∥∇ft(xt)−∇ft−1(xt)∥2+LD+LD∑t=2T∥xt−xt−1∥2≲VT+LD+LD∑t=2T∥xt−xt−1∥2. \begin{align*} A_T =& \| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2 \\ =& \| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_t) + \nabla f_{t-1}(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2 \\ \lesssim& \| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_t) \|^2 + \sum_{t=2}^T \| \nabla f_{t-1}(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2 \\ \lesssim& \| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_t) \|^2 + L^2 \sum_{t=2}^T \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2, \\ \sqrt{A_T} \lesssim& \sqrt{\| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_t) \|^2 + L^2 \sum_{t=2}^T \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2} \\ \lesssim& \sqrt{\| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_t) \|^2} + L \sqrt{\sum_{t=2}^T \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2} \\ \lesssim& \sqrt{\| \nabla f_1(\mathbf{x}_1) \|^2 + \sum_{t=2}^T \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_t) \|^2} + L D + \frac{L}{D} \sum_{t=2}^T \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2 \\ \lesssim& \sqrt{V_T} + L D + \frac{L}{D} \sum_{t=2}^T \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2. \end{align*}

代入 RTR_T

RT≲DVT+LD2+∑t=2T(L−AtD)∥xt−xt−1∥2⏟TODO. R_T \lesssim D \sqrt{V_T} + LD^2 + \underbrace{\sum_{t=2}^T \left( L - \frac{\sqrt{A_t}}{D} \right) \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2}_{\text{TODO}}.

目的是使 TODO 项为负项，并使得 AtA_t 不依赖于 L 的取值。当 At≥LD\sqrt{A_t} \ge LD 时， TODO 项显然为负，问题是 At<LD\sqrt{A_t} < LD 。此时直接代入 RTR_T 原本的表达式

RT≲DAT−∑t=2TAtD∥xt−xt−1∥2≲LD2. \begin{align*} R_T \lesssim& D\sqrt{A_T} - \sum_{t=2}^T \frac{\sqrt{A_t}}{D} \| \mathbf{x}_t - \mathbf{x}_{t-1} \|^2 \\ \lesssim& LD^2. \end{align*}

比刚才推导的 bound 还要小。所以 AtA_t 不需要做约束。

Methods on Proof of Theorem 3

相对于普通的Smooth、Lipschitz情况做法有些区别。

Utilizing Bregman Divergence

∑t=1Tft(xt)−ft(x⋆)=∑t=1T⟨ft(xt),xt−x⋆⟩−∑t=1TDft(x⋆,xt). \sum_{t=1}^T f_t(\mathbf{x}_t) - f_t(\mathbf{x}_\star) = \sum_{t=1}^T \langle f_t(\mathbf{x}_t), \mathbf{x}_t - \mathbf{x}_\star \rangle - \sum_{t=1}^T \mathcal{D}_{f_t}(\mathbf{x}_\star, \mathbf{x}_t).

首先 ftf_t 得是凸函数，其次在 ftf_t 是 λ\lambda-strongly convex 的情况下，会有一些 bonus：

Dft(x,y)≥λ2∥x−y∥2. \mathcal{D}_{f_t}(\mathbf{x}, \mathbf{y}) \ge \frac{\lambda}{2} \| \mathbf{x} - \mathbf{y} \|^2.

这一步被用到证明原文中 TERM-A 小于 TERM-B 。此外

TERM-B≲∑t=1T1λt∥∇ft(xt)−∇ft−1(xt−1)∥2≲∑t=1T1λt∥∇ft(xt)−∇ft(x⋆)+∇ft(x⋆)−∇ft−1(x⋆)+∇ft−1(x⋆)−∇ft−1(xt−1)∥2≲∑t=1T1λt(∥∇ft(xt)−∇ft(x⋆)∥2+∥∇ft(x⋆)−∇ft−1(x⋆)∥2+∥∇ft−1(x⋆)−∇ft−1(xt−1)∥2)≲∑t=1T1λt∥∇ft(xt)−∇ft(x⋆)∥2+∑t=1T1λt∥∇ft(x⋆)−∇ft−1(x⋆)∥2≲∑t=1TLλtDft(x⋆,xt)+∑t=1T1λtsup⁡x∈X∥∇ft(x)−∇ft−1(x)∥2 \begin{align*} \text{TERM-B} \lesssim& \sum_{t=1}^T \frac{1}{\lambda t} \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2 \\ \lesssim& \sum_{t=1}^T \frac{1}{\lambda t} \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t}(\mathbf{x}_\star) + \nabla f_{t}(\mathbf{x}_\star) - \nabla f_{t-1}(\mathbf{x}_\star) \\ &\quad\quad\quad+ \nabla f_{t-1}(\mathbf{x}_\star) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2 \\ \lesssim& \sum_{t=1}^T \frac{1}{\lambda t} \Big( \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t}(\mathbf{x}_\star) \|^2 + \| \nabla f_{t}(\mathbf{x}_\star) - \nabla f_{t-1}(\mathbf{x}_\star) \|^2 \\ &\quad\quad\quad+ \| \nabla f_{t-1}(\mathbf{x}_\star) - \nabla f_{t-1}(\mathbf{x}_{t-1}) \|^2 \Big) \\ \lesssim& \sum_{t=1}^T \frac{1}{\lambda t} \| \nabla f_t(\mathbf{x}_t) - \nabla f_{t}(\mathbf{x}_\star) \|^2 + \sum_{t=1}^T \frac{1}{\lambda t} \| \nabla f_{t}(\mathbf{x}_\star) - \nabla f_{t-1}(\mathbf{x}_\star) \|^2 \\ \lesssim& \sum_{t=1}^T \frac{L}{\lambda t} \mathcal{D}_{f_t}(\mathbf{x}_\star, \mathbf{x}_t) + \sum_{t=1}^T \frac{1}{\lambda t} \sup_{\mathbf{x} \in \mathcal{X}}\| \nabla f_{t}(\mathbf{x}) - \nabla f_{t-1}(\mathbf{x}) \|^2 \\ \end{align*}

代入 RTR_T 会收获

∑t=1T(Lλt−12)Dft(x⋆,xt) \sum_{t=1}^T \left( \frac{L}{\lambda t} - \frac{1}{2} \right) \mathcal{D}_{f_t}(\mathbf{x}_\star, \mathbf{x}_t)

还有两个关于积分的不等式，用于放缩得到闭式上界，看原论文就行。

Methods on Lemma 6

Utilizing Strongly Convex Setting

见 Online-to-Batch Conversion 。和论文中方法不太一样，应该也能用？

最终结果是构造出 Lemma 6 的形式

(4Ltβt2λ(1+βt)−1)α1:t−1D(xˉt−xˉt−1) \left( \frac{4 L_t \beta_t^2}{\lambda (1 + \beta_t)} - 1 \right) \alpha_{1:t-1} \mathcal{D}(\bar{\mathcal{x}}_t - \bar{\mathcal{x}}_{t-1})

这个玩意在 βt≤λ4Lt\beta_t \le \sqrt{\frac{\lambda}{4 L_t}} 时为负，可以直接舍弃。

不懂为什么 βt=βˉ\beta_t = \bar{\beta} 的情况不用负项消除。