1. 优化知识预备

1.1目标函数

首先我们的目标是最小化一个损失函数：

L ( W , Z ) L(W,Z) L(W,Z)

其中 W = ( w 1 , w 2 , . . . , w k ) W=(w_1,w_2,...,w_k) W=(w1​,w2​,...,wk​)是参数， Z = { ( X i , y i , y ^ i ∣ i = 1 , 2 , . . . , n ) } Z=\{(X_i,y_i,\hat y_i|i=1,2,...,n)\} Z={(Xi​,yi​,y^​i​∣i=1,2,...,n)}， y ^ i = f ( W , X i ) \hat y_i=f(W,X_i) y^​i​=f(W,Xi​)是预测的结果。损失函数通常可以写成各个样本损失函数的累加，即 L ( W , Z ) = ∑ i = 1 n L ( W , Z i ) L(W,Z)=\sum_{i=1}^nL(W,Z_i) L(W,Z)=∑i=1n​L(W,Zi​)，在我们们确定函数 f f f的形式下 W W W 就是我们求解的目标，而求解的方式就是寻找能使损失函数最小的 W W W。

W = arg min ⁡ W L ( W , Z ) W=\argmin_WL(W,Z) W=Wargmin​L(W,Z)

1.2求解方法

对于这样的问题，在问题形式较为简单，我们可以得到问题的解析解，而得到解析解的方法例如拉格朗日乘数法，KKT条件等，但更多的我们还是需要使用数值计算的方式去求解，而梯度下降就是一类经典的数值求解方法，GD算法如下：

其中Z是全体的数据，而在数据量大的情况下出现了SGD：

每次迭代仅仅根据单个样本更新权重?，这种算法称作随机梯度下降法。

1.3算法的评价

什么样的算法是一个好的算法？

对于一个数值求解算法，我们总是希望在能接受的时间内得到一个满足要求的解，在当今大数据的时代背景下，我们还应考虑算法对机器的考验。

综上适用条件，收敛性和收敛速度和可实现性，我认为从这三个方面对一个算法进行评价是比较完整的。

1.3.1 适用条件

算法能够使用的场合往往是有要求的，比如可微，比如强凸等等，使用算法之前要注意使用的环境的配套。

1.3.2 收敛性和收敛速度

为什么要和算法适用的环境配套就是因为在一些极端情况下算法可能求不到最优值（比如陷入局部最优），这个问题可以通过将目标函数改为强凸函数，或者多设几个初始点去解决。除此以外还有一个问题就是算法的收敛性和收敛速度的问题。

收敛性：

算法产生的迭代点列 { x i } \{x_i\} {xi​}在某种范数的意义下满足：

lim ⁡ n → ∞ ∥ x n − x ∗ ∥ = 0 \lim_{n\rightarrow\infty}\|x_n-x^*\|=0 n→∞lim​∥xn​−x∗∥=0

才称算法是收敛的，如果从任意初始点出发都可以收敛到 x ∗ x^* x∗称为是全局收敛，如果仅初始点与 x ∗ x^* x∗足够近的时候才能收敛到 x ∗ x^* x∗称为是局部收敛的。

收敛速度：

在已知收敛的情况下，收敛速度是：

lim ⁡ n → ∞ ∥ x n + 1 − x ∗ ∥ ∥ x n − x ∗ ∥ k = α \lim_{n\rightarrow\infty}\frac{\|x_{n+1}-x^*\|}{\|x_{n}-x^*\|^k}=\alpha n→∞lim​∥xn​−x∗∥k∥xn+1​−x∗∥​=α

如果 α ≥ 1 , k = 1 \alpha\geq1,k=1 α≥1,k=1称为次线性收敛

如果 0 < α < 1 , k = 1 0<\alpha<1,k=1 0<α<1,k=1称为线性收敛

如果 α = 0 , k = 1 \alpha=0,k=1 α=0,k=1称为超线性收敛

如果 0 < α < 1 , k = 2 0<\alpha<1,k=2 0<α<1,k=2称为二阶收敛

2. SGD、SAG、SVRG

SGD类算法的一个问题就是收敛速度不够快，SAG和SVRG是提出的，作为SGD类算法在收敛速度上的重大突破，下面来介绍这两个算法：

2.1 SAG

在步长为 α k \alpha_k αk​的情况下最小化 1 n ∑ i = 1 n f i ( x ) \frac{1}{n}\sum_{i=1}^nf_i(x) n1​∑i=1n​fi​(x)

d = 0 , y i = 0 d=0,y_i=0 d=0,yi​=0，对所有的n ∈ { 1 , 2 , . . . , n } \in\{1,2,...,n\} ∈{1,2,...,n} for k=0,1,…do 从 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n}中随机抽取一个 i i i出来 d = d − y i + f i ′ ( x ) d=d-y_i+f'_i(x) d=d−yi​+fi′​(x) y i = f i ′ ( x ) y_i=f'_i(x) yi​=fi′​(x) x = x − α n d x=x-\frac{\alpha}{n}d x=x−nα​d end for convergence

2.2 SVRG

最小化 1 n ∑ i = 1 n ψ i ( x ) \frac{1}{n}\sum_{i=1}^n\psi_i(x) n1​∑i=1n​ψi​(x)，更新率 m m m和学习率 η \eta η

给定迭代初始值 w ^ 0 \hat w_0 w^0​开始迭代： for s=0,1,…do w ~ = w ^ s − 1 \tilde w=\hat w_{s-1} w~=w^s−1​ μ ~ = 1 n ∑ i = 1 n ∇ ψ i ( w ~ ) \tilde\mu=\frac{1}{n}\sum_{i=1}^n\nabla\psi_i(\tilde w) μ~​=n1​∑i=1n​∇ψi​(w~) w 0 = w ~ w_0=\tilde w w0​=w~迭代: for t = 1,2,…,m随机从 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n}中选一个 i t i_t it​然后更新权重 w t = w t − 1 − η ( ∇ ψ i t ( w t − 1 ) − ∇ ψ i t ( w ~ ) + μ ~ ) w_t=w_{t-1}-\eta(\nabla\psi_{i_t}(w_{t-1})-\nabla\psi_{i_t} (\tilde w)+\tilde \mu) wt​=wt−1​−η(∇ψit​​(wt−1​)−∇ψit​​(w~)+μ~​)end 选项1：令 w ~ s = w m \tilde w_s=w_m w~s​=wm​选项2：令 w ~ s = w t \tilde w_s=w_t w~s​=wt​， t t t是从 { 1 , . . . , m − 1 } \{1,...,m-1\} {1,...,m−1}中随机选出的。 end for convergence

3. OGD

3.1问题背景

优化问题大数据量并且存在增量学习

3.2 OGD沿着稀疏性主线的发展

3.2.2 简单截断法

3.2.3 TG

3.2.4 FOBOS

3.2.5 RDA

给定一个初始的参数 W 0 W^0 W0，下面开始迭代， W ( t ) W^{(t)} W(t)的更新方式是：

W ( t + 1 ) = arg min ⁡ W { 1 t ∑ r = 1 t ⟨ G ( r ) , W ⟩ + Ψ ( W ) + β ( t ) t h ( W ) } W^{(t+1)}=\argmin_W\{\frac{1}{t}\sum_{r=1}^t\langle G^{(r)},W\rangle+\Psi(W)+\frac{\beta^{(t)}}{t}h(W)\} W(t+1)=Wargmin​{t1​r=1∑t​⟨G(r),W⟩+Ψ(W)+tβ(t)​h(W)}

其中 G ( r ) G^{(r)} G(r)是第 r r r次迭代中损失函数的梯度（取法是SGD的取法，不是全局的梯度）， ⟨ G ( r ) , W ⟩ \langle G^{(r)},W\rangle ⟨G(r),W⟩表示 G ( r ) G^{(r)} G(r)的一个线性函数（对 W W W求一个均值）, Ψ ( W ) \Psi(W) Ψ(W)是一个正则项， h ( W ) h(W) h(W)是一个强凸函数（保证迭代的全局最优解唯一）， β ( t ) \beta^{(t)} β(t)是一个非负不减的序列决定了收敛速率。

3.2.5.1 L1-RDA

取 Ψ ( x ) \Psi(x) Ψ(x)是L1范数 Ψ ( x ) = λ ∥ W ∥ 1 \Psi(x)=\lambda\|W\|_1 Ψ(x)=λ∥W∥1​，在此情况下我们来看看RDA方法的具体步骤：

不妨取 h ( W ) = 1 2 ∥ W ∥ 2 2 h(W)=\frac{1}{2}\|W\|^2_2 h(W)=21​∥W∥22​， β ( t ) = γ t \beta^{(t)}=\gamma\sqrt{t} β(t)=γt ​，现在对每个标量进行研究，问题转化为：

arg min ⁡ W { 1 t ∑ i = 1 t g i ( t ) w i + λ ∣ w i ∣ + γ 2 t ∥ w i ∥ 2 2 } \argmin_W\{\frac{1}{t}\sum_{i=1}^tg_i^{(t)}w_i+\lambda|w_i|+\frac{\gamma}{2\sqrt{t}}\|w_i\|^2_2\} Wargmin​{t1​i=1∑t​gi(t)​wi​+λ∣wi​∣+2t ​γ​∥wi​∥22​}

即

arg min ⁡ W { g ˉ t ( t ) w i + λ ∣ w i ∣ + γ 2 t w i 2 } \argmin_W\{\bar g_t^{(t)}w_i+\lambda|w_i|+\frac{\gamma}{2\sqrt{t}}w_i^2\} Wargmin​{gˉ​t(t)​wi​+λ∣wi​∣+2t ​γ​wi2​}

其中第二项 ∣ w i ∣ |w_i| ∣wi​∣在0处不可导。假设最优解是 w i ∗ w_i^* wi∗​，那么定义 ξ ∈ ∂ ∣ w i ∗ ∣ \xi\in\partial|w^*_i| ξ∈∂∣wi∗​∣是 ∣ w i ∣ |w_i| ∣wi​∣在 w i ∗ w_i^* wi∗​处的导数（次导数），那么有：

∂ ∣ w i ∗ ∣ = { { − 1 < ξ < 1 } i f w i ∗ = 0 { 1 } i f w i ∗ > 0 { − 1 } i f w i ∗ < 0 \partial|w^*_i| = \begin{cases} \{-1<\xi<1\} & if\ w^*_i=0 \\ \{1\}&if\ w^*_i>0 \\ \{-1\}&if\ w^*_i<0 \end{cases} ∂∣wi∗​∣=⎩⎪⎨⎪⎧​{−1<ξ<1}{1}{−1}​ifwi∗​=0ifwi∗​>0ifwi∗​<0​

如果对上面的目标函数求导（求次导数）并令其为0则有：

g ˉ i ( t ) + λ ξ + γ t w i = 0 \bar g_i^{(t)}+\lambda\xi+\frac{\gamma}{\sqrt{t}}w_i=0 gˉ​i(t)​+λξ+t ​γ​wi​=0

由于 λ > 0 \lambda>0 λ>0，下面分情况进行讨论：

（1）当 ∣ g ˉ i ( t ) ∣ < λ |\bar g_i^{(t)}|<\lambda ∣gˉ​i(t)​∣<λ，还可以分三种情况 如果 w i ∗ = 0 w^*_i=0 wi∗​=0， ξ = − g ˉ i ( t ) / λ ∈ ∂ ∣ 0 ∣ \xi=-\bar g_i^{(t)}/\lambda\in\partial|0| ξ=−gˉ​i(t)​/λ∈∂∣0∣满足 如果 w i ∗ > 0 w^*_i>0 wi∗​>0， ξ = 1 \xi=1 ξ=1， g ˉ i ( t ) + λ + γ t w i > g ˉ i ( t ) + λ > 0 \bar g_i^{(t)}+\lambda+\frac{\gamma}{\sqrt{t}}w_i>\bar g_i^{(t)}+\lambda>0 gˉ​i(t)​+λ+t ​γ​wi​>gˉ​i(t)​+λ>0，不满足 如果 w i ∗ < 0 w^*_i<0 wi∗​<0， ξ = − 1 \xi=-1 ξ=−1， g ˉ i ( t ) − λ + γ t w i < g ˉ i ( t ) − λ < 0 \bar g_i^{(t)}-\lambda+\frac{\gamma}{\sqrt{t}}w_i<\bar g_i^{(t)}-\lambda<0 gˉ​i(t)​−λ+t ​γ​wi​<gˉ​i(t)​−λ<0，不满足 （2）当 g ˉ i ( t ) < − λ \bar g_i^{(t)}<-\lambda gˉ​i(t)​<−λ，还可以分三种情况 如果 w i ∗ = 0 w^*_i=0 wi∗​=0， ξ = − g ˉ i ( t ) / λ ∉ ∂ ∣ 0 ∣ \xi=-\bar g_i^{(t)}/\lambda\notin\partial|0| ξ=−gˉ​i(t)​/λ∈/​∂∣0∣不满足 如果 w i ∗ > 0 w^*_i>0 wi∗​>0， ξ = 1 \xi=1 ξ=1， g ˉ i ( t ) + λ + γ t w i = 0 \bar g_i^{(t)}+\lambda+\frac{\gamma}{\sqrt{t}}w_i=0 gˉ​i(t)​+λ+t ​γ​wi​=0， w i ∗ = − t γ ( g ˉ i ( t ) + λ ) > 0 w_i^*=-\frac{\sqrt{t}}{\gamma}(\bar g^{(t)}_i+\lambda)>0 wi∗​=−γt ​​(gˉ​i(t)​+λ)>0满足 如果 w i ∗ < 0 w^*_i<0 wi∗​<0， ξ = − 1 \xi=-1 ξ=−1， g ˉ i ( t ) − λ + γ t w i = 0 \bar g_i^{(t)}-\lambda+\frac{\gamma}{\sqrt{t}}w_i=0 gˉ​i(t)​−λ+t ​γ​wi​=0， w i ∗ = t γ ( − g ˉ i ( t ) + λ ) > 0 w_i^*=\frac{\sqrt{t}}{\gamma}(-\bar g^{(t)}_i+\lambda)>0 wi∗​=γt ​​(−gˉ​i(t)​+λ)>0不满足 （3）当 g ˉ i ( t ) > λ \bar g_i^{(t)}>\lambda gˉ​i(t)​>λ，还可以分三种情况 如果 w i ∗ = 0 w^*_i=0 wi∗​=0， ξ = − g ˉ i ( t ) / λ ∉ ∂ ∣ 0 ∣ \xi=-\bar g_i^{(t)}/\lambda\notin\partial|0| ξ=−gˉ​i(t)​/λ∈/​∂∣0∣不满足 如果 w i ∗ > 0 w^*_i>0 wi∗​>0， ξ = 1 \xi=1 ξ=1， g ˉ i ( t ) + λ + γ t w i = 0 \bar g_i^{(t)}+\lambda+\frac{\gamma}{\sqrt{t}}w_i=0 gˉ​i(t)​+λ+t ​γ​wi​=0， w i ∗ = − t γ ( g ˉ i ( t ) + λ ) < 0 w_i^*=-\frac{\sqrt{t}}{\gamma}(\bar g^{(t)}_i+\lambda)<0 wi∗​=−γt ​​(gˉ​i(t)​+λ)<0不满足 如果 w i ∗ < 0 w^*_i<0 wi∗​<0， ξ = − 1 \xi=-1 ξ=−1， g ˉ i ( t ) − λ + γ t w i = 0 \bar g_i^{(t)}-\lambda+\frac{\gamma}{\sqrt{t}}w_i=0 gˉ​i(t)​−λ+t ​γ​wi​=0， w i ∗ = t γ ( − g ˉ i ( t ) + λ ) < 0 w_i^*=\frac{\sqrt{t}}{\gamma}(-\bar g^{(t)}_i+\lambda)<0 wi∗​=γt ​​(−gˉ​i(t)​+λ)<0满足。

综上我们得到了L1-RDA特征权重各个维度的更新方式：

w i ( t = 1 ) = { 0 if ∣ g ˉ t ( t ) ∣ < λ − t γ ( g ˉ t ( t ) − λ s g n ( g ˉ t ( t ) ) ) otherwise w_i^{(t=1)}= \begin{cases} 0&\text{if}\ |\bar g_t^{(t)}|<\lambda \\ -\frac{\sqrt{t}}{\gamma}(\bar g_t^{(t)}-\lambda sgn(\bar g_t^{(t)}))&\text{otherwise} \end{cases} wi(t=1)​={0−γt ​​(gˉ​t(t)​−λsgn(gˉ​t(t)​))​if∣gˉ​t(t)​∣<λotherwise​

观察到对某个维度而言，累积梯度平均值的绝对值 ∣ g ˉ t ( t ) ∣ |\bar g_t^{(t)}| ∣gˉ​t(t)​∣小于阈值 λ \lambda λ的时候，该维度的权重被置为0，特征权重的稀疏性由此产生。

伪代码如下：

3.2.6 FTRL

L1-FOBOS基于梯度下降，精度高，L1-RDA损失一定精度但是稀疏性更好，FTRL是二者的结合，我们首先在形式上统一L1-FOBOS和L1-RDA：

L1-FOBOS，每次迭代可以表示为（在这里令 η ( t + 1 2 ) = η ( t ) = Θ ( 1 t ) \eta^{(t+\frac{1}{2})}=\eta^{(t)}=\Theta(\frac{1}{\sqrt{t}}) η(t+21​)=η(t)=Θ(t ​1​)是一个随 t t t变化的非增正序列）：

W ( t + 1 2 ) = W ( t ) − η ( t ) G ( t ) W^{(t+\frac{1}{2})}=W^{(t)}-\eta^{(t)}G^{(t)} W(t+21​)=W(t)−η(t)G(t)

W ( t = 1 ) = arg min ⁡ W { 1 2 ∥ W − W ( t + 1 2 ) ∥ 2 2 + η ( t ) λ ∥ W ∥ 1 } W^{(t=1)}=\argmin_W\{\frac{1}{2}\|W-W^{(t+\frac{1}{2})}\|^2_2+\eta^{(t)}\lambda\|W\|_1\} W(t=1)=Wargmin​{21​∥W−W(t+21​)∥22​+η(t)λ∥W∥1​}

两个公式合并在一起有：

W ( t + 1 ) = arg min ⁡ W { 1 2 ∥ W − W ( t ) + η ( t ) G ( t ) ∥ 2 2 + η ( t ) λ ∥ W ∥ 1 } W^{(t+1)}=\argmin_W\{\frac{1}{2}\|W-W^{(t)}+\eta^{(t)}G^{(t)}\|_2^2+\eta^{(t)}\lambda\|W\|_1\} W(t+1)=Wargmin​{21​∥W−W(t)+η(t)G(t)∥22​+η(t)λ∥W∥1​}

写成每个维度上的分量的形式即等价于在每个维度上求：

arg min ⁡ w i ∈ R { 1 2 ( w i − w i ( t ) + η ( t ) g i ( t ) ) 2 + η ( t ) λ ∣ w i ∣ } = arg min ⁡ w i ∈ R { 1 2 ( w i − w i ( t ) ) 2 + 1 2 ( η ( t ) g i ( t ) ) 2 + η ( t ) λ ∣ w i ∣ + w i η ( t ) g i ( t ) } = arg min ⁡ w i ∈ R { 1 2 η ( t ) ( w i − w i ( t ) ) 2 + λ ∣ w i ∣ + w i g i ( t ) } \argmin_{w_i\in \mathbb R}\{\frac{1}{2}(w_i-w_i^{(t)}+\eta^{(t)}g^{(t)}_i)^2+\eta^{(t)}\lambda|w_i|\} \\ =\argmin_{w_i\in \mathbb R}\{\frac{1}{2}(w_i-w_i^{(t)})^2+\frac{1}{2}(\eta^{(t)}g^{(t)}_i)^2+\eta^{(t)}\lambda|w_i|+w_i\eta^{(t)}g_i^{(t)}\} \\ =\argmin_{w_i\in \mathbb R}\{\frac{1}{2\eta^{(t)}}(w_i-w_i^{(t)})^2+\lambda|w_i|+w_ig_i^{(t)}\} wi​∈Rargmin​{21​(wi​−wi(t)​+η(t)gi(t)​)2+η(t)λ∣wi​∣}=wi​∈Rargmin​{21​(wi​−wi(t)​)2+21​(η(t)gi(t)​)2+η(t)λ∣wi​∣+wi​η(t)gi(t)​}=wi​∈Rargmin​{2η(t)1​(wi​−wi(t)​)2+λ∣wi​∣+wi​gi(t)​}

化简的依据就是把和 w i w_i wi​无关的项去掉，再将这N个独立最优化步骤合并得到：

W ( t + 1 ) = arg min ⁡ W { G ( t ) ⋅ W + λ ∥ W ∥ 1 + 1 2 η ( t ) ∥ W − W ( t ) ∥ 2 2 } W^{(t+1)}=\argmin_W\{G^{(t)}\cdot W+\lambda\|W\|_1+\frac{1}{2\eta^{(t)}}\|W-W^{(t)}\|^2_2\} W(t+1)=Wargmin​{G(t)⋅W+λ∥W∥1​+2η(t)1​∥W−W(t)∥22​}

而L1-RDA的权重更新方式是：

W ( t + 1 ) = arg min ⁡ W { G ( 1 : t ) ⋅ W + t λ ∥ W ∥ 1 + 1 2 η ( t ) ∥ W − 0 ∥ 2 2 } W^{(t+1)}=\argmin_W\{G^{(1:t)}\cdot W+t\lambda\|W\|_1+\frac{1}{2\eta^{(t)}}\|W-0\|^2_2\} W(t+1)=Wargmin​{G(1:t)⋅W+tλ∥W∥1​+2η(t)1​∥W−0∥22​}

其中 G ( 1 : t ) = ∑ i = 1 t G ( s ) G^{(1:t)}=\sum^t_{i=1}G^{(s)} G(1:t)=∑i=1t​G(s)，如果令 σ ( t ) = 1 η ( t ) − 1 η ( t − 1 ) \sigma^{(t)}=\frac{1}{\eta^{(t)}}-\frac{1}{\eta^{(t-1)}} σ(t)=η(t)1​−η(t−1)1​，那么有 σ ( 1 : t ) = 1 η ( t ) \sigma^{(1:t)}=\frac{1}{\eta^{(t)}} σ(1:t)=η(t)1​上面两个式子可以写作：

L1-FOBOS: W ( t + 1 ) = arg min ⁡ W { G ( t ) ⋅ W + λ ∥ W ∥ 1 + 1 2 σ ( 1 : t ) ∥ W − W ( t ) ∥ 2 2 } L1-RDA: W ( t + 1 ) = arg min ⁡ W { G ( 1 : t ) ⋅ W + t λ ∥ W ∥ 1 + 1 2 σ ( 1 : t ) ∥ W − 0 ∥ 2 2 } \text{L1-FOBOS: } \ W^{(t+1)}=\argmin_W\{G^{(t)}\cdot W+\lambda\|W\|_1+\frac{1}{2}\sigma^{(1:t)}\|W-W^{(t)}\|^2_2\} \\ \text{L1-RDA: } \ W^{(t+1)}=\argmin_W\{G^{(1:t)}\cdot W+t\lambda\|W\|_1+\frac{1}{2}\sigma^{(1:t)}\|W-0\|^2_2\} L1-FOBOS:W(t+1)=Wargmin​{G(t)⋅W+λ∥W∥1​+21​σ(1:t)∥W−W(t)∥22​}L1-RDA:W(t+1)=Wargmin​{G(1:t)⋅W+tλ∥W∥1​+21​σ(1:t)∥W−0∥22​}

比较这两个公式显然我们可以看到L1-FOBOS和L1-RDA的区别在于

（1）前者计算的是当前的梯度以及L1正则项只考虑当前模的贡献，后者采取了累加的处理方式

（2）前者第三项限制 W W W的变化不能离上一步太远，后者限制不能离原点太远。

在FOBOS和RDA方法取L1范数下统一形式的基础上我们来看FTRL的特征权重的更新方式：

W ( t + 1 ) = arg min ⁡ W { G ( 1 : t ) ⋅ W + λ 1 ∥ W ∥ 1 + λ 2 ∥ W ∥ 2 2 + 1 2 ∑ s = 1 t σ s ∥ W − W ( s ) ∥ 2 2 } W^{(t+1)}=\argmin_W\{G^{(1:t)}\cdot W+\lambda_1\|W\|_1+\lambda_2\|W\|_2^2+\frac{1}{2}\sum_{s=1}^t\sigma^{s}\|W-W^{(s)}\|_2^2\} W(t+1)=Wargmin​{G(1:t)⋅W+λ1​∥W∥1​+λ2​∥W∥22​+21​s=1∑t​σs∥W−W(s)∥22​}

在这里L2正则项的引入是为了让求解结果更加“平滑”。

对于上面的公式进行改写，将最后一项展开等价于：

W ( t + 1 ) = arg min ⁡ W { ( G ( 1 : t ) − ∑ s = 1 t σ ( s ) W ( s ) ) ⋅ W + λ 1 ∥ W ∥ 1 + 1 2 ( λ 2 + ∑ s = 1 t σ ( s ) W ( s ) ) ∥ W ∥ 2 2 + 1 2 ∑ s = 1 t σ s ∥ W ( s ) ∥ 2 2 } W^{(t+1)}=\argmin_W\{(G^{(1:t)}-\sum_{s=1}^t\sigma^{(s)}W^{(s)})\cdot W+\lambda_1\|W\|_1 \\ +\frac{1}{2}(\lambda_2+\sum_{s=1}^t\sigma^{(s)}W^{(s)})\|W\|_2^2+\frac{1}{2}\sum_{s=1}^t\sigma^{s}\|W^{(s)}\|_2^2\} W(t+1)=Wargmin​{(G(1:t)−s=1∑t​σ(s)W(s))⋅W+λ1​∥W∥1​+21​(λ2​+s=1∑t​σ(s)W(s))∥W∥22​+21​s=1∑t​σs∥W(s)∥22​}

把与 W W W无关的常数去掉之后，并且令 Z ( t ) = G ( 1 : t ) − ∑ s = 1 t σ ( s ) W ( s ) Z^{(t)}=G^{(1:t)}-\sum_{s=1}^t\sigma^{(s)}W^{(s)} Z(t)=G(1:t)−∑s=1t​σ(s)W(s)，上面的式子可以化为：

W ( t + 1 ) = arg min ⁡ W { Z ( t ) + λ 1 ∥ W ∥ 1 + 1 2 ( λ 2 + σ ( 1 : t ) W ( s ) ) ∥ W ∥ 2 2 } W^{(t+1)}=\argmin_W\{Z^{(t)}+\lambda_1\|W\|_1+\frac{1}{2}(\lambda_2+\sigma^{(1:t)}W^{(s)})\|W\|_2^2\} W(t+1)=Wargmin​{Z(t)+λ1​∥W∥1​+21​(λ2​+σ(1:t)W(s))∥W∥22​}

针对特征权重的各个维度将其拆解为N个独立的标量最小化的问题：

w i ( t + 1 ) = arg min ⁡ w i ∈ R { z i ( t ) w i + λ 1 ∣ w i ∣ + 1 2 ( λ 2 + σ ( 1 : t ) ) w i 2 } w_i^{(t+1)}=\argmin_{w_i\in\mathbb R}\{z_i^{(t)}w_i+\lambda_1|w_i|+\frac{1}{2}(\lambda_2+\sigma^{(1:t)})w_i^2\} wi(t+1)​=wi​∈Rargmin​{zi(t)​wi​+λ1​∣wi​∣+21​(λ2​+σ(1:t))wi2​}

和对L1-RDA的做法一样，设最优解是 w i ∗ w_i^* wi∗​，那么在最优解出的导数（次导数）为0：

z i ( t ) + λ 1 ∂ ∣ w i ∗ ∣ + ( λ 2 + σ ( 1 : t ) ) w i ∗ = 0 z_i^{(t)}+\lambda_1\partial|w_i^*|+(\lambda_2+\sigma^{(1:t)})w_i^*=0 zi(t)​+λ1​∂∣wi∗​∣+(λ2​+σ(1:t))wi∗​=0

其中 σ ( 1 : t ) = η ( t ) \sigma^{(1:t)}=\eta^{(t)} σ(1:t)=η(t)，并且这个问题与当时L1-RDA也是形式一致的，定义 ξ ∈ ∂ ∣ w i ∗ ∣ \xi\in\partial|w^*_i| ξ∈∂∣wi∗​∣是 ∣ w i ∣ |w_i| ∣wi​∣在 w i ∗ w_i^* wi∗​处的导数（次导数），那么有：

∂ ∣ w i ∗ ∣ = { { − 1 < ξ < 1 } i f w i ∗ = 0 { 1 } i f w i ∗ > 0 { − 1 } i f w i ∗ < 0 \partial|w^*_i| = \begin{cases} \{-1<\xi<1\} & if\ w^*_i=0 \\ \{1\}&if\ w^*_i>0 \\ \{-1\}&if\ w^*_i<0 \end{cases} ∂∣wi∗​∣=⎩⎪⎨⎪⎧​{−1<ξ<1}{1}{−1}​ifwi∗​=0ifwi∗​>0ifwi∗​<0​

由于 λ > 0 \lambda>0 λ>0，下面分情况进行讨论：

（1）当 ∣ z i ( t ) ∣ < λ 1 |z_i^{(t)}|<\lambda_1 ∣zi(t)​∣<λ1​，还可以分三种情况 如果 w i ∗ = 0 w^*_i=0 wi∗​=0， ξ = − z t ( t ) / λ ∈ ∂ ∣ 0 ∣ \xi=-z_t^{(t)}/\lambda\in\partial|0| ξ=−zt(t)​/λ∈∂∣0∣满足 如果 w i ∗ > 0 w^*_i>0 wi∗​>0， ξ = 1 \xi=1 ξ=1， z i ( t ) + λ + ( λ 2 + η ( t ) ) w i > z i ( t ) + λ > 0 z_i^{(t)}+\lambda+(\lambda_2+\eta^{(t)})w_i>z_i^{(t)}+\lambda>0 zi(t)​+λ+(λ2​+η(t))wi​>zi(t)​+λ>0，不满足 如果 w i ∗ < 0 w^*_i<0 wi∗​<0， ξ = − 1 \xi=-1 ξ=−1， z i ( t ) − λ + ( λ 2 + η ( t ) ) w i < z i ( t ) − λ < 0 z_i^{(t)}-\lambda+(\lambda_2+\eta^{(t)})w_i<z_i^{(t)}-\lambda<0 zi(t)​−λ+(λ2​+η(t))wi​<zi(t)​−λ<0，不满足 （2）当 z t ( t ) < − λ 1 z_t^{(t)}<-\lambda_1 zt(t)​<−λ1​，还可以分三种情况 如果 w i ∗ = 0 w^*_i=0 wi∗​=0， ξ = − z i ( t ) / λ ∉ ∂ ∣ 0 ∣ \xi=-z_i^{(t)}/\lambda\notin\partial|0| ξ=−zi(t)​/λ∈/​∂∣0∣不满足 如果 w i ∗ > 0 w^*_i>0 wi∗​>0， ξ = 1 \xi=1 ξ=1， z i ( t ) + λ + ( λ 2 + η ( t ) ) w i = 0 z_i^{(t)}+\lambda+(\lambda_2+\eta^{(t)})w_i=0 zi(t)​+λ+(λ2​+η(t))wi​=0， w i ∗ = − 1 ( λ 2 + η ( t ) ) ( z i ( t ) + λ ) > 0 w_i^*=-\frac{1}{(\lambda_2+\eta^{(t)})}(z^{(t)}_i+\lambda)>0 wi∗​=−(λ2​+η(t))1​(zi(t)​+λ)>0满足 如果 w i ∗ < 0 w^*_i<0 wi∗​<0， ξ = − 1 \xi=-1 ξ=−1， z i ( t ) − λ + γ t w i = 0 z_i^{(t)}-\lambda+\frac{\gamma}{\sqrt{t}}w_i=0 zi(t)​−λ+t ​γ​wi​=0， w i ∗ = 1 ( λ 2 + η ( t ) ) ( − z i ( t ) + λ ) > 0 w_i^*=\frac{1}{(\lambda_2+\eta^{(t)})}( -z^{(t)}_i+\lambda)>0 wi∗​=(λ2​+η(t))1​(−zi(t)​+λ)>0不满足 （3）当 z t ( t ) > λ 1 z_t^{(t)}>\lambda_1 zt(t)​>λ1​，还可以分三种情况 如果 w i ∗ = 0 w^*_i=0 wi∗​=0， ξ = − z t ( t ) / λ ∉ ∂ ∣ 0 ∣ \xi=-z_t^{(t)}/\lambda\notin\partial|0| ξ=−zt(t)​/λ∈/​∂∣0∣不满足 如果 w i ∗ > 0 w^*_i>0 wi∗​>0， ξ = 1 \xi=1 ξ=1， z i ( t ) + λ + ( λ 2 + η ( t ) ) w i = 0 z_i^{(t)}+\lambda+(\lambda_2+\eta^{(t)})w_i=0 zi(t)​+λ+(λ2​+η(t))wi​=0， w i ∗ = − 1 ( λ 2 + η ( t ) ) ( g ˉ i ( t ) + λ ) < 0 w_i^*=-\frac{1}{(\lambda_2+\eta^{(t)})}(\bar g^{(t)}_i+\lambda)<0 wi∗​=−(λ2​+η(t))1​(gˉ​i(t)​+λ)<0不满足 如果 w i ∗ < 0 w^*_i<0 wi∗​<0， ξ = − 1 \xi=-1 ξ=−1， g ˉ i ( t ) − λ + γ t w i = 0 \bar g_i^{(t)}-\lambda+\frac{\gamma}{\sqrt{t}}w_i=0 gˉ​i(t)​−λ+t ​γ​wi​=0， w i ∗ = 1 ( λ 2 + η ( t ) ) ( − g ˉ i ( t ) + λ ) < 0 w_i^*=\frac{1}{(\lambda_2+\eta^{(t)})}(-\bar g^{(t)}_i+\lambda)<0 wi∗​=(λ2​+η(t))1​(−gˉ​i(t)​+λ)<0满足。

因此我们得到

w i ( t + 1 ) = { 0 if ∣ z i ( t ) ∣ < λ 1 − ( λ 2 + η ( t ) ) − 1 ( z i ( t ) − λ 1 s g n ( z i ( t ) ) ) otherwise w_i^{(t+1)}= \begin{cases} 0 &\text{if}\ |z_i^{(t)}|<\lambda_1\\ -(\lambda_2+\eta^{(t)})^{-1}(z_i^{(t)}-\lambda_1sgn(z_i^{(t)}))&\text{otherwise} \end{cases} wi(t+1)​={0−(λ2​+η(t))−1(zi(t)​−λ1​sgn(zi(t)​))​if∣zi(t)​∣<λ1​otherwise​

由此可看出引入的L2范数并没有对解的稀疏性造成影响。

Reference

[1] 在线最优化求解(Online Optimization)冯扬 (@fengyoung) 新浪微博-商业平台及产品部-推荐引擎

[2]线性收敛的随机优化算法 之 SAG、SVRG /p/22402784

[3]Roux N L , Schmidt M , Bach F . A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets[J]. Advances in Neural Information Processing Systems, , 4:2663-2671.

[4]Zhang J, Hu F, Xu X, et al. Stochastic gradient descent with variance reduction technique[J]. Web Intelligence, , 16(3):187-194.

[5]Jia X , Zhao L , Zhang L , et al. Modified Regularized Dual Averaging Method for Training Sparse Convolutional Neural Networks[J]. .

如果觉得《SGD与OGD》对你有帮助，请点赞、收藏，并留下你的观点哦！