这篇文章主要是对FOBOS这个方法的文献做一下简单的翻译，加深自己的理解，如有错误欢迎指出

这篇文章是John Duchi（加利福尼亚大学伯克利分校）和Yoram Singer（谷歌）在09年发表的一篇关于凸优化的文章。

Abstract

    在摘要里，作者就指明文章描述了一种最小化带正则化的经验损失的新框架，在新框架下，每次迭代分为两个阶段进行，首先是普通的梯度下降，之后构造了一个新的瞬时优化问题(instantaneous optimization problem)【这里我不太明白这个instantaneous指代的是什么意思】，这个新问题可以在保持结果与第一阶段没有太大差异的情况下，trades off minimization of a regularization term 【不知道该怎么翻译，平衡正则项的最小化？】。

Introduction

    文章使用 $||x|{|}_p$ 表示矢量$x$的p范数，而用$||x||$表示二范数$||x|{|}_2$的简写。文章要解决的问题的一般形式如下：$$f(\mathbf{w})+r(\mathbf{w})\text{\hspace{1em}(1)}$$ 其中两个函数 $f$ 和 $r$ 都是有下界的凸函数(convex bounded below functions)，一般的，前者是经验损失而后者是正则项，这在机器学习相关的问题中经常可以见到。
    有许多方法用来解决一般的凸函数的最小化问题，较为常见的就是次梯度方法，用 $\partial f(\mathbf{w})$ 表示函数 $f$ 在 $w$ 出的次微分，即 ∂ f ( w ) = { g ∣ ∀ v : f ( v ) ≥ f ( w ) + ⟨ g , v − w ⟩ } \partial f(\boldsymbol{w})=\{\boldsymbol{g} | \forall \boldsymbol{v}: f(\boldsymbol{v}) \geq f(\boldsymbol{w})+\langle\boldsymbol{g}, \boldsymbol{v}-\boldsymbol{w}\rangle\} ∂f(w)={g∣∀v:f(v)≥f(w)+⟨g,v−w⟩}次梯度方法的解决方法是根据更新规则迭代更新参数向量 $w$ ：${\mathbf{w}}_{t+1}={\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f$，其中 $\eta$ 是step size，而 $g_t^f$ 是次梯度集合中的任何一个。另一种方法是梯度投影：
$${\mathbf{w}}_{t+1}={\Pi }_{\Omega }\left({\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f\right)=\underset{\mathbf{w}\in \Omega }{\mathrm{argmin}}\left\{{\Vert \mathbf{w}-\left({\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f\right)\Vert }_2^2\right\}$$其中 ${\Pi }_{\Omega }(\mathbf{w})$ 表示 $w$ 在集合 $\Omega$ 上的欧几里得投影。使用次梯度方法解决公式（1）形式如下：$${\mathbf{w}}_{t+1}={\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f-{\eta }_t{\mathbf{g}}_t^r,\text{ where }{\mathbf{g}}_t^r\in \partial r\left({\mathbf{w}}_t\right)$$次梯度法中的一个常见问题是，如果 $r$ 或 $f$ 是不可微的，则次梯度法的迭代很少会落在不可微点处。然而有时候函数的最小值恰好就在这些不可微处，例如 $y=|x|$。
    文章指出有很多方法与最小化公式（1）相关，尤其是当 $r$ 是 稀疏提升正则项（sparsity-promoting regularizer） 时。作者称他们是基于一个叫做forward-backward splitting的方法进行的优化，然后是一堆综述，这里就不介绍了。

Forward-Looking Subgradients and Forward-Backward Splitting

    作者称他们最初用FOLOS作为“FOrward LOoking Subgradient”的缩写，考虑到他们的算法是对已有的凸优化方法的升华，特别是前向后向分裂方法（Forward-Backward Splitting），为了不让早期的读者感到困惑，他们尽量保持原名不变，改用首字母缩写Fobos而不是Fobas。FOBOS算法的初衷是为了能够将 $w_t$ 迭代至函数 $r$ 的不可微的点，通过采取与次梯度步骤交错的分析最小化步骤（analytical minimization steps）来缓解 ${\ell }_1$ -regularization 等情况下的不可微问题。非正式的说，FOBOS类似于次梯度投影，只不过是用一个瞬时最小化问题代替或增强了投影步骤，这样可能得到闭合形式的解。FOBOS的迭代公式如下：$$\begin{array}{rl}{\mathbf{w}}_{t+\frac{1}{2}}& ={\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f\\ {\mathbf{w}}_{t+1}& =\underset{\mathbf{w}}{\mathrm{argmin}}\left\{\frac{1}{2}{\Vert \mathbf{w}-{\mathbf{w}}_{t+\frac{1}{2}}\Vert }^2+{\eta }_{t+\frac{1}{2}}r(\mathbf{w})\right\}\end{array}\text{\hspace{1em}(2 ，3)}$$在第二步，文章找到了一个介于两个目标之间的向量：

1. stay close to the interim vector ${\mathbf{w}}_{t+\frac{1}{2}}$，就是与第一步不要差的太远。
2. attain a low complexity value as expressed by $r$，由r表示的低复杂度【难道说易于计算?】的值

方程（3）的一个重要性质是能够得到最优解的必要条件，同时也是命名为FOBOS的重要原因，即：$${0\in \partial \left\{\frac{1}{2}{\Vert \mathbf{w}-{\mathbf{w}}_{t+\frac{1}{2}}\Vert }^2+{\eta }_{t+\frac{1}{2}}r(\mathbf{w})\right\}|}_{\mathbf{w}={\mathbf{w}}_{t+1}}$$带入 ${\mathbf{w}}_{t+\frac{1}{2}}$ ，上式相当于$0\in {\mathbf{w}}_{t+1}-{\mathbf{w}}_t+{\eta }_t{\mathbf{g}}_t^f+{\eta }_{t+\frac{1}{2}}\partial r\left({\mathbf{w}}_{t+1}\right)$。这个性质意味着只要按照上面的迭代公式，就可以保证得到一个向量${\mathbf{g}}_{t+1}^r\in \partial r\left({\mathbf{w}}_{t+1}\right)$ 能够使得 $0={\mathbf{w}}_{t+1}-{\mathbf{w}}_t+{\eta }_t{\mathbf{g}}_t^f+{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r$【因为0属于这个集合，选择那个就是0的就可以了】可以这么理解更新规则：新的权重矢量 $w_{t+1}$ 是先前的权重矢量 $w_t$ 、函数 $f$ 在 $w_t$ 处的次梯度和函数 $r$ 在尚未确定的 $w_{t+1}$ 处的次梯度的线性组合。简而言之，可以得到：$${\mathbf{w}}_{t+1}={\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f-{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r\text{\hspace{1em}(4)}$$使用上式解决方程（3）有两个优点：

1. 从算法层面看，它可以在几乎不增加计算成本的情况下实现稀疏解方案。
2. forward-looking gradient允许方法建立在现有分析的基础之上，且能够表示所得到的框架具有许多现有的基于梯度的在线凸优化算法的形式收敛性。

引用知乎看到的一篇博客

其中Forward-Looking Subgradients指的正是$x^{(t)}-\eta \nabla l\left(x^{(t)}\right)$这⼀步仅基于损失函数的梯度（或次梯度）来更新参数，⽽Forward-Backward Splitting指的就是根据上⼀步的中间解的⼤⼩来做“裁剪”。

Convergence and Regret Analysis of FOBOS

    regret analysis可以参考知乎上这个说法，我觉得说的挺好滴。通过设计${\eta }_{t+\frac{1}{2}}$，可以得到不同的收敛速度，例如可以令${\eta }_{t+\frac{1}{2}}$为${\eta }_t$或者${\eta }_{t+1}$，这取决于是做在线还是批量优化。接下来用${\mathbf{w}}^{\ast }$表示$f(\mathbf{w})+r(\mathbf{w})$最小时的值。第一个界限是依赖于假设$\Vert {\mathbf{w}}^{\star }\Vert \le D$，尽管没有之后的界限的那么紧凑。
    定义$\Vert \partial f(\mathbf{w})\Vert \triangleq {\sup }_{\mathbf{g}\in \partial f(\mathbf{w})}\Vert \mathbf{g}\Vert$，首先在相当普遍的假设下【引用了两篇文章J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient. In Advances in Neural Information Processing Systems 22, 2008. 和S. Shalev-Shwartz and A. Tewari. Stochastic methods for ℓ1-regularized loss minimization. In Proceedings of the 26th International Conference on Machine Learning, 2009.】导出收敛结果，假设次梯度有界限：
$$\Vert \partial f(\mathbf{w}){\Vert }^2\le Af(\mathbf{w})+G^2,\Vert \partial r(\mathbf{w}){\Vert }^2\le Ar(\mathbf{w})+G^2\text{\hspace{1em}(5)}$$例如，任何Lipschitz损失(如Logistic或铰链/SVM)都满足上述条件，其中A=0，G等于Lipschitz常数；最小二乘满足G=0，A=4。

对于函数 y=f(x) 在定义域为D上，如果存在 L ∈R ,且L>0，对任意 x1,x2 ∈D，有：
|f(x1)-f(x2)|≤ L|x1-x2|；则称 L 为 f(x) 在D上的Lipschitz常数。从这里可以看出，Lipschitz常数并不是固定不变的，而是依据具体的函数而定。
原文链接：https://blog.csdn.net/Chaolei3/article/details/81202544

接下来文章给出了第一个理论：
Theorem 1. 假如下面的条件成立：

1. 来自 $\partial \mathbf{f}$ 的任何次梯度的范数和来自 $\partial \mathbf{r}$ 的任何次梯度的范数都是有界的，如方程（5）一样。
2. ${\mathbf{w}}^{\ast }$的范数小于等于 $D$
3. $\mathbf{r}(0)=0$
4. $\frac{1}{2}{\eta }_t\le {\eta }_{t+1}\le {\eta }_t$

那么对于常数 $c\le 4$，$w_1=0$ 和 ${\eta }_{t+\frac{1}{2}}={\eta }_{t+1}$， 有：
$$\sum _{t=1}^T\left[{\eta }_t\left(\left(1-cA{\eta }_t\right)f\left({\mathbf{w}}_t\right)-f\left({\mathbf{w}}^{\star }\right)\right)+{\eta }_t\left(\left(1-cA{\eta }_t\right)r\left({\mathbf{w}}_t\right)-r\left({\mathbf{w}}^{\star }\right)\right)\right]\le D^2+7G^2\sum _{t=1}^T{\eta }_t^2$$该理论在固定步进率情况下有一个推论。
Corollary 2 (Fixed step rate). 假如理论1的条件成立，在预先设定好迭代次数T后运行FOBOS，同时令 ${\eta }_t=\frac{D}{\sqrt{7T}G}$ 且 $\left(1-cA\frac{D}{\sqrt{7TG}}\right)>0$ 那么则有：
min ⁡ t ∈ { 1 , … , T } f ( w t ) ≤ 1 T ∑ t = 1 T f ( w t ) + r ( w t ) ≤ 3 D G T ( 1 − c A D G 7 T ) + f ( w ⋆ ) + r ( w ⋆ ) 1 − c A D G 7 T \min _{t \in\{1, \ldots, T\}} f\left(\boldsymbol{w}_{t}\right) \leq \frac{1}{T} \sum_{t=1}^{T} f\left(\boldsymbol{w}_{t}\right)+r\left(\boldsymbol{w}_{t}\right) \leq \frac{3 D G}{\sqrt{T}\left(1-\frac{c A D}{G \sqrt{7 T}}\right)}+\frac{f\left(\boldsymbol{w}^{\star}\right)+r\left(\boldsymbol{w}^{\star}\right)}{1-\frac{c A D}{G \sqrt{7 T}}} t∈{1,…,T}min​f(wt​)≤T1​t=1∑T​f(wt​)+r(wt​)≤T ​(1−G7T ​cAD​)3DG​+1−G7T ​cAD​f(w⋆)+r(w⋆)​上面的形式是标准的次梯度优化，而优化的终结点并非是最后一个向量参数$w_T$，因为次梯度的优化是没有方向的。
    接下来是FOBOS的regret bounds，其公式呢就是类似于前面链接里的一样，是一些列预测的向量与最优向量的差异和：
$$R_{f+r}(T)=\sum _{t=1}^T\left[f_t\left({\mathbf{w}}_t\right)+r\left({\mathbf{w}}_t\right)-\left(f_t\left({\mathbf{w}}^{\star }\right)+r\left({\mathbf{w}}^{\star }\right)\right)\right]$$理想情况下当然是对于任意长的序列，其regret bounds都是0。
    作者修改了M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Machine Learning, 2003.里的参数，对于 ${\eta }_{t+\frac{1}{2}}$ 设为 ${\eta }_t$，那么会有理论3：
Theorem 3. 假设所有迭代都满足$\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\star }\Vert \le D$，且$\partial f_t$和$\partial r$的次梯度集的范数都≤G(bounded above by G)。令 $c>0$ 是一个任一标量，在 ${\eta }_t=c/\sqrt{t}$ 时，FOBOS的regret bounds满足$$R_{f+r}(T)\le GD+(\frac{D^2}{2c}+7G^{2}c)\sqrt{T}$$
文章称出于技术上的原因，对于$w_t$和次梯度的界限的假设实际上不是限制性的。对于FOBOS算法，是有可能得到$O(logT)$的regret bound，只要loss function $f_r(\cdot )$或者 $r(\cdot )$具有强凸性质。

强凸性多用在优化中(Optimization)，特别是保证很多基于梯度下降方法的算法的线形收敛速率的条件之一。一个可微函数强凸的定义是：$$f(y)\ge f(x)+\nabla f(x{)}^T(y-x)+\frac{u}{2}||y-x|{|}^2$$强凸比一般的凸函数更严格在于其中的的二次项.直观从一维函数来说，一般凸函数只要求函数曲线在其切线之上，至于“上”多少没有要求，也就意味着曲线可以无限“贴着”切线，只要保持在其上就行了。毫无疑问，在优化特别是梯度优化中，这种微弱的梯度变化很难实现快速优化，有可能在有限次数还达不到收敛。如果我们取一个接近最小值的解，这也很难。“非常”接近只是一个定性理解，在这种情况下会出现最优解很近似但是决策变量相差巨大的糟糕情况。这时候，多加一个二次项的，保证有一个二次下界，那么不会出现“贴着”切线的情况，优化也变得更加简单。
有的情况下，没有强凸的条件，可以人为加上一个二次项，以获得强凸特性。
原文链接：https://blog.csdn.net/qq_41769289/article/details/87694955

对于在线学习，使用regret analysis 可以给出随机FOBOS的收敛速度为$O(\sqrt{T})$。

Derived Algorithms

衍生算法，也就是一些变种啦。为了简化推导，文章用 $\mathbf{v}$ 表示vector ${\mathbf{w}}_{t+\frac{1}{2}}={\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f$，用 $\tilde{\lambda }$ 表示 ${\mathbf{\eta }}_{t+\frac{1}{2}}\cdot \lambda$，此时公式(3)就可以重写为：${\min }_w\frac{1}{2}(w-v{)}^2+\tilde{\lambda }|w|$。最后，使用$[z{]}_{+}$ 表示 max ⁡ { 0 , z } \max \{0, z\} max{0,z}。

L1正则下的FOBOS(${\ell }_1$)

$r(\mathbf{w})=\lambda \Vert \mathbf{w}{\Vert }_1$，此时最优解 $w^{\star }=w_{t+1}$为：
$$w_{t+1,j}=\mathrm{sign}\left(w_{t+\frac{1}{2},j}\right){\left[\left|w_{t+\frac{1}{2},j}\right|-\tilde{\lambda }\right]}_{+}=\mathrm{sign}\left(w_{t,j}-{\eta }_t{g}_{t,j}^f\right){\left[\left|w_{t,j}-{\eta }_t{g}_{t,j}^f\right|-\lambda {\eta }_{t+\frac{1}{2}}\right]}_{+}\text{\hspace{1em}(6)}$$这个式子可以有稀疏解，只要 $w_{t+\frac{1}{2}}$的绝对值比 $\tilde{\lambda }$小，对应的新参数就变为了0，和“truncated gradient”很类似的。

L2正则下的FOBOS(${\ell }_2^2$)

当$r(\mathbf{w})=\frac{\lambda }{2}\Vert \mathbf{w}{\Vert }_2^2$，可以得到简单的优化问题${\min }_{\mathbf{w}}\frac{1}{2}\Vert \mathbf{w}-\mathbf{v}{\Vert }^2+\frac{1}{2}\tilde{\lambda }\Vert \mathbf{w}{\Vert }^2$，求导并令其等于0有${\mathbf{w}}^{\star }-\mathbf{v}+\tilde{\lambda }{\mathbf{w}}^{\star }=0$， 于是其更新规则为：
$${\mathbf{w}}_{t+1}=\frac{{\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f}{1+\tilde{\lambda }}\text{\hspace{1em}(7)}$$，此时只是简单的收缩第一步的结果。

不常用的L2正则(${\ell }_2$)

$r(\mathbf{w})=\lambda \Vert \mathbf{w}{\Vert }_2$，此时${\min }_w\frac{1}{2}(w-v{)}^2+\tilde{\lambda }||w||$，这种情况下的解必须和$\mathbf{v}$同向，即${\mathbf{w}}^{\ast }=s\mathbf{v},s\ge 0$。此时有：
$${\mathbf{w}}_{t+1}={\left[1-\frac{\tilde{\lambda }}{\Vert {\mathbf{w}}_{t+\frac{1}{2}}\Vert }\right]}_{+}={\left[1-\frac{\tilde{\lambda }}{\Vert {\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f\Vert }\right]}_{+}\left({\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f\right)$$【最后怎么多了一项小括号里的，我没看懂…】当$\Vert {\mathbf{w}}_t-{\eta }_t{\mathbf{g}}_t^f\Vert \le \tilde{\lambda }$时，变为稀疏项。对于稀疏性，此条件比${\ell }_1$的条件更为严格，因此在高维情况下不太可能成立。

后面的混合模式和无限范式完全看不懂啊…实验的话也略过啦

证明

为了证明理论1，先给出下面的：

Lemma 5 (Bounding Step Differences)

假如$\Vert \partial f(\mathbf{w}){\Vert }^2\le Af(\mathbf{w})+G^2,\Vert \partial r(\mathbf{w}){\Vert }^2\le Ar(\mathbf{w})+G^2$，并且令${\eta }_{t+1}\le {\eta }_{t+\frac{1}{2}}\le {\eta }_t$ ， ${\eta }_t\le 2{\eta }_{t+\frac{1}{2}}$，使用公式(2)和公式(3)进行更新，则对于任意的标量 $c\le 4$和 $w^{\ast }$，有：
$$\begin{array}{l}2{\eta }_t\left(1-cA{\eta }_t\right)f\left({\mathbf{w}}_t\right)+2{\eta }_{t+\frac{1}{2}}\left(1-cA{\eta }_{t+\frac{1}{2}}\right)r\left({\mathbf{w}}_{t+1}\right)\\ \le 2{\eta }_{t}f\left({\mathbf{w}}^{\star }\right)+2{\eta }_{t+\frac{1}{2}}r\left({\mathbf{w}}^{\star }\right)+{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\star }\Vert }^2-{\Vert {\mathbf{w}}_{t+1}-{\mathbf{w}}^{\star }\Vert }^2+7{\eta }_t{\eta }_{t+\frac{1}{2}}{G}^2\end{array}\text{\hspace{1em}(12)}$$
Proof of Lemma 5：根据公式(4)，有$${\mathbf{w}}_{t+1}-{\mathbf{w}}_t=-{\eta }_t{\mathbf{g}}_t^f-{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r\text{\hspace{1em}(13)}$$那么根据次梯度的定义，有$$r\left({\mathbf{w}}^{\star }\right)\ge r\left({\mathbf{w}}_{t+1}\right)+⟨{\mathbf{g}}_{t+1}^r,{\mathbf{w}}^{\star }-{\mathbf{w}}_{t+1}⟩\Rightarrow -⟨{\mathbf{g}}_{t+1}^r,{\mathbf{w}}_{t+1}-{\mathbf{w}}^{\star }⟩\le r\left({\mathbf{w}}^{\star }\right)-r\left({\mathbf{w}}_{t+1}\right)$$根据柯西不等式$|a|\cdot |b|\ge |a\cdot b|,a=\left(a_1,a_2,\cdots ,a_n\right),b=\left(b_1,b_2,\cdots ,b_n\right)$，可以得到：$$\begin{array}{l}⟨{\mathbf{g}}_{t+1}^r,\left({\mathbf{w}}_{t+1}-{\mathbf{w}}_t\right)⟩=⟨{\mathbf{g}}_{t+1}^r,\left(-{\eta }_t{\mathbf{g}}_t^f-{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r\right)⟩\\ \le \Vert {\mathbf{g}}_{t+1}^r\Vert \Vert {\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r+{\eta }_t{\mathbf{g}}_t^f\Vert \le {\eta }_{t+\frac{1}{2}}{\Vert {\mathbf{g}}_{t+1}^r\Vert }^2+{\eta }_t\Vert {\mathbf{g}}_{t+1}^r\Vert \Vert {\mathbf{g}}_t^f\Vert \\ \le {\eta }_{t+\frac{1}{2}}\left(Ar\left({\mathbf{w}}_{t+1}\right)+G^2\right)+{\eta }_t\max \left\{Af\left({\mathbf{w}}_t\right)+G^2,\mathrm{Ar}\left({\mathbf{w}}_{t+1}\right)+G^2\right\}\end{array}\text{\hspace{1em}(15)}$$而$w_{t+1}$和$w^{\ast }$之间的bound为：
$$\begin{array}{l}{\Vert {\mathbf{w}}_{t+1}-{\mathbf{w}}^{\star }\Vert }^2={\Vert {\mathbf{w}}_t-\left({\eta }_t{\mathbf{g}}_t^f+{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r\right)-{\mathbf{w}}^{\star }\Vert }^2\\ ={\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\star }\Vert }^2-2\left[{\eta }_t⟨{\mathbf{g}}_t^f,{\mathbf{w}}_t-{\mathbf{w}}^{\star }⟩+{\eta }_{t+\frac{1}{2}}⟨{\mathbf{g}}_{t+1}^r,{\mathbf{w}}_t-{\mathbf{w}}^{\star }⟩\right]+{\Vert {\eta }_t{\mathbf{g}}_t^f+{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r\Vert }^2\\ ={\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\star }\Vert }^2-2{\eta }_t⟨{\mathbf{g}}_t^f,{\mathbf{w}}_t-{\mathbf{w}}^{\star }⟩+{\Vert {\eta }_t{\mathbf{g}}_t^f+{\eta }_{t+\frac{1}{2}}{\mathbf{g}}_{t+1}^r\Vert }^2\\ -2{\eta }_{t+\frac{1}{2}}\left[⟨{\mathbf{g}}_{t+1}^r,{\mathbf{w}}_{t+1}-{\mathbf{w}}^{\star }⟩-⟨{\mathbf{g}}_{t+1}^r,{\mathbf{w}}_{t+1}-{\mathbf{w}}_t⟩\right]\end{array}\text{\hspace{1em}(16)}$$上面的式子的第三小项： ∥ η t g t f + η t + 1 2 g t + 1 r ∥ 2 = η t 2 ∥ g t f ∥ 2 + 2 η t η t + 1 2 ⟨ g t f , g t + 1 r ⟩ + η t + 1 2 2 ∥ g t + 1 r ∥ 2 ≤ η t 2 A f ( w t ) + 2 A η t η t + 1 2 max ⁡ { f ( w t ) , r ( w t + 1 ) } + η t + 1 2 2 Ar ⁡ ( w t + 1 ) + 4 η t 2 G 2 \begin{array}{l} {\left\|\eta_{t} \boldsymbol{g}_{t}^{f}+\eta_{t+\frac{1}{2}} \boldsymbol{g}_{t+1}^{r}\right\|^{2}} \\ {\quad=\eta_{t}^{2}\left\|\boldsymbol{g}_{t}^{f}\right\|^{2}+2 \eta_{t} \eta_{t+\frac{1}{2}}\left\langle\boldsymbol{g}_{t}^{f}, \boldsymbol{g}_{t+1}^{r}\right\rangle+\eta_{t+\frac{1}{2}}^{2}\left\|\boldsymbol{g}_{t+1}^{r}\right\|^{2}} \\ {\quad \leq \eta_{t}^{2} A f\left(\boldsymbol{w}_{t}\right)+2 A \eta_{t} \eta_{t+\frac{1}{2}} \max \left\{f\left(\boldsymbol{w}_{t}\right), r\left(\boldsymbol{w}_{t+1}\right)\right\}+\eta_{t+\frac{1}{2}}^{2} \operatorname{Ar}\left(\boldsymbol{w}_{t+1}\right)+4 \eta_{t}^{2} G^{2}} \end{array} ∥∥∥​ηt​gtf​+ηt+21​​gt+1r​∥∥∥​2=ηt2​∥∥∥​gtf​∥∥∥​2+2ηt​ηt+21​​⟨gtf​,gt+1r​⟩+ηt+21​2​∥∥​gt+1r​∥∥​2≤ηt2​Af(wt​)+2Aηt​ηt+21​​max{f(wt​),r(wt+1​)}+ηt+21​2​Ar(wt+1​)+4ηt2​G2​这里解释一下从第二行到第三行，第二行的第一项有一个$G^2$, 第三项有一个$G^2$，中间项的内积相乘可以看做大数和小数的内积，当然小于等于大数和本身自己的内积，替换后又产生两个$G^2$
将上面的结果和公式(15)带入公式(16)，有：
∥ w t + 1 − w ⋆ ∥ 2 ≤ ∥ w t − w ⋆ ∥ 2 − 2 η t ⟨ g t f , w t − w ⋆ ⟩ − 2 η t + 1 2 ⟨ g t + 1 r , w t + 1 − w ⋆ ⟩ + ∥ η t g t f + η t + 1 2 g t + 1 r ∥ 2 + 2 η t + 1 2 ( η t + 1 2 Ar ⁡ ( w t + 1 ) + 2 A η t max ⁡ { f ( w t ) , r ( w t + 1 ) } + 2 η t G 2 ) ≤ ∥ w t − w ⋆ ∥ 2 + 2 η t ( f ( w ⋆ ) − f ( w t ) ) + 2 η t + 1 2 ( r ( w ⋆ ) − r ( w t ) ) + 7 η t 2 G 2 + η t 2 A f ( w t ) + 3 A η t η t + 1 2 max ⁡ { f ( w t ) , r ( w t ) } + 2 η t + 1 2 2 Ar ⁡ ( w t + 1 ) ≤ ∥ w t − w ⋆ ∥ 2 + 7 η t 2 G 2 + 2 η t ( f ( w ⋆ ) − ( 1 − c A η t ) f ( w t ) ) + 2 η t + 1 2 ( r ( w ⋆ ) − ( 1 − c A η t + 1 2 ) r ( w t + 1 ) ) \begin{array}{l} {\left\|\boldsymbol{w}_{t+1}-\boldsymbol{w}^{\star}\right\|^{2}} \\ {\leq\left\|\boldsymbol{w}_{t}-\boldsymbol{w}^{\star}\right\|^{2}-2 \eta_{t}\left\langle\boldsymbol{g}_{t}^{f}, \boldsymbol{w}_{t}-\boldsymbol{w}^{\star}\right\rangle- 2 \eta_{t+\frac{1}{2}}\left\langle\boldsymbol{g}_{t+1}^{r}, \boldsymbol{w}_{t+1}-\boldsymbol{w}^{\star}\right\rangle+\left\|\eta_{t} \boldsymbol{g}_{t}^{f}+\eta_{t+\frac{1}{2}} \boldsymbol{g}_{t+1}^{r}\right\|^{2}} \\ {\quad+2 \eta_{t+\frac{1}{2}}\left(\eta_{t+\frac{1}{2}} \operatorname{Ar}\left(\boldsymbol{w}_{t+1}\right)+2 A \eta_{t} \max \left\{f\left(\boldsymbol{w}_{t}\right), r\left(\boldsymbol{w}_{t+1}\right)\right\}+2 \eta_{t} G^{2}\right)} \\ {\leq\left\|\boldsymbol{w}_{t}-\boldsymbol{w}^{\star}\right\|^{2}+2 \eta_{t}\left(f\left(\boldsymbol{w}^{\star}\right)-f\left(\boldsymbol{w}_{t}\right)\right)+2 \eta_{t+\frac{1}{2}}\left(r\left(\boldsymbol{w}^{\star}\right)-r\left(\boldsymbol{w}_{t}\right)\right)+7 \eta_{t}^{2} G^{2}} \\ {\quad+\eta_{t}^{2} A f\left(\boldsymbol{w}_{t}\right)+3 A \eta_{t} \eta_{t+\frac{1}{2}} \max \left\{f\left(\boldsymbol{w}_{t}\right), r\left(\boldsymbol{w}_{t}\right)\right\}+2 \eta_{t+\frac{1}{2}}^{2} \operatorname{Ar}\left(\boldsymbol{w}_{t+1}\right)} \\ {} \begin{aligned} \leq &\left\|\boldsymbol{w}_{t}-\boldsymbol{w}^{\star}\right\|^{2}+7 \eta_{t}^{2} G^{2} \\ &+2 \eta_{t}\left(f\left(\boldsymbol{w}^{\star}\right)-\left(1-c A \eta_{t}\right) f\left(\boldsymbol{w}_{t}\right)\right)+2 \eta_{t+\frac{1}{2}}\left(r\left(\boldsymbol{w}^{\star}\right)-\left(1-c A \eta_{t+\frac{1}{2}}\right) r\left(\boldsymbol{w}_{t+1}\right)\right) \end{aligned} \end{array} ∥wt+1​−w⋆∥2≤∥wt​−w⋆∥2−2ηt​⟨gtf​,wt​−w⋆⟩−2ηt+21​​⟨gt+1r​,wt+1​−w⋆⟩+∥∥∥​ηt​gtf​+ηt+21​​gt+1r​∥∥∥​2+2ηt+21​​(ηt+21​​Ar(wt+1​)+2Aηt​max{f(wt​),r(wt+1​)}+2ηt​G2)≤∥wt​−w⋆∥2+2ηt​(f(w⋆)−f(wt​))+2ηt+21​​(r(w⋆)−r(wt​))+7ηt2​G2+ηt2​Af(wt​)+3Aηt​ηt+21​​max{f(wt​),r(wt​)}+2ηt+21​2​Ar(wt+1​)≤​∥wt​−w⋆∥2+7ηt2​G2+2ηt​(f(w⋆)−(1−cAηt​)f(wt​))+2ηt+21​​(r(w⋆)−(1−cAηt+21​​)r(wt+1​))​​这里实在是没有看懂，一共是三个不等式，对于第一个不等式，完全就是将$⟨{\mathbf{g}}_{t+1}^r,{\mathbf{w}}_{t+1}-{\mathbf{w}}_t⟩$展开，根据公式(15)，为什么会有 2 A η t max ⁡ { f ( w t ) , r ( w t + 1 ) } 2 A \eta_{t} \max \left\{f\left(\boldsymbol{w}_{t}\right), r\left(\boldsymbol{w}_{t+1}\right)\right\} 2Aηt​max{f(wt​),r(wt+1​)}呢，这个 2 从哪里来呢；
然后就是第二个不等式，先不说那些奇怪的系数怎么对应的上，前面还是 max ⁡ { f ( w t ) , r ( w t + 1 ) } \max \left\{f\left(\boldsymbol{w}_{t}\right), r\left(\boldsymbol{w}_{t+1}\right)\right\} max{f(wt​),r(wt+1​)}，后面怎么变成 max ⁡ { f ( w t ) , r ( w t ) } \max \left\{f\left(\boldsymbol{w}_{t}\right), r\left(\boldsymbol{w}_{t}\right)\right\} max{f(wt​),r(wt​)}了呢，我估计是论文里写错了。此外，最后一个不等式的成立运用到了 $3A{\eta }_t{\eta }_{t+\frac{1}{2}}\le 6A{\eta }_t^2$ 和 max ⁡ { a , b } ≤ a + b \max \{a, b\} \leq a+b max{a,b}≤a+b，而我依然没发现怎么成立的，应该是第二个式子里${\eta }_t^{2}Af\left({\mathbf{w}}_t\right)$ 前面系数由1变为2 ，反正是小于等于，多加一个依然成立。但是你加一些有的没的又不说清楚的话，对于我这种笨脑子好难哦

有了上面的结果，theorem 1就很好证明了 ，这里就不叙述了。整篇文章数学性很高，我读起来很吃力，只能大致领会其中的关键意志：首先来个正常的，然后构造个式子，在距离原始结果不远的同时提高一下稀疏性。给大佬跪了~，很多地方自己也不是很清楚，希望以后再阅读的时候能够理解。