这篇笔记主要参考冯杨的五篇博客：在线最优化求解(Online Optimization)。因为对于在线学习方法，稀疏性问题需要特别关注：每次在线学习一个新 instance 的时候，优化方向并不一定是全局最优，不容易产生稀疏解，而简单截断又可能将从全局看不该稀疏掉的特征变为零。所以这里以 L1 正则为基础，比较几种在线学习算法。
0，预备
每个 instance 由特征向量和预测目标组成: \((\mathbf x,y)\)。其中 \(\mathbf x \in \mathbb R^N, y \in \{0,1\}\)。第 \(t\) 个新样本标记为 \((\mathbf x^{(t)}, y^{(t)})\)。
模型预测值:
\[ p = \sigma(\mathbf w\cdot \mathbf x) = \frac{1}{1+e^{-\mathbf w \cdot \mathbf x}} \]
经验损失函数采用交叉熵的形式：
\[ \ell_0(\mathbf w) = -y \log p - (1-y)\log(1-p) \]
经验损失对权重的梯度，后面用 \(\mathbf g\) 表示：
\[ \mathbf g \equiv \nabla\ell_0(\mathbf w) = (p-y)\mathbf x\]
1，L1 正则
基本的 L1 正则逻辑回归方法，在经验损失函数中直接加入 L1 正则项 \(\ell(\mathbf w) = \ell_0(\mathbf w) + \lambda \left|\mathbf w\right|\)，然后直接优化。在某一方向上的梯度为：
\[ \nabla \ell(\mathbf w) = \mathbf g + \lambda \ \nabla |\mathbf w^t|\]
迭代方式：
\[ \mathbf w^{t+1} = \mathbf w^t - \eta \nabla\ell \qquad \\
\qquad = \mathbf w^t - \eta \mathbf g^t -\eta \lambda \nabla \left| \mathbf w^t \right| \] 其中 \(\eta > 0\) 是学习率。\(\nabla|w_i|\) 在 0 处非光滑，故需要使用次梯度来代替，即使用一些截断方法。
截断方式：
简单截断法：
从上面的更新公式可以看出，L1 正则的作用是，如果 \(w_i^t > 0\)，将 \(w\) 在 沿梯度下降方向移动后，再减去一个常数； 如果 \(w_i^t < 0\)，则是加上一个常数。总之使其向 0 靠拢。下面就是一种简单的截断方法，使得如果经过 L1 正则修正后越过 0，则直接置为 0，从而实现有效稀疏性。
\[ w_i^{t+1} = T_0(w_i^t - \eta g^t_i,\ \eta \lambda)\\
T_0(x,y) = \begin{cases}
0, & if\ \left|x \right| \leq y \\
x & otherwise
\end{cases}\]截断梯度法(TG)
相比上面方法不那么粗暴，在两端接近被截断的小范围 \(\theta\) 内，向横轴移动一段，使其近 0 端达到 0。当 \(\theta = \eta \lambda\) 时，与上面的简单截断法相同。
\[ w_i^{t+1} = T_1 (w_i^t - \eta g^t_i,\ \eta\ \lambda, \ \theta)\\
T_1(x,y,z) = \begin{cases}
0, & if\ \left| x \right| \leq y \\
x-y, & if\ \left|x \right| \in (y,z) \\
x & if\ \left| x \right| > z
\end{cases}\]
这两种截断方法在更新时都会取窗口 \(k\)，每 \(k\) 步做一次截断。\(t\%k\neq 0\) 时不截断（令 \(\lambda = 0\)）。
2，L1-FOBOS
优化目标
Forward-Backward Splitting，是由 John Duchi 和 Yoram Singer 提出的。
FOBOS 中模型的更新分为如下两步，优先沿经验损失减小的方向优化，然后在尽量与上一步结果偏离不太远的情况下，最小化正则项 \(\Psi(\mathbf w)\)。这样不需要设定截断规则，就能得到类似的结果。
\[ \mathbf w^ {t+\frac 1 2} = \mathbf w^t - \eta^t \mathbf g^t \\
\mathbf w^{t+1} = arg\min_w \left\{ \frac 1 2 \| \mathbf w - \mathbf w^{t+\frac 1 2} \|^2 + \eta^\frac 1 2\ \Psi(\mathbf w) \right\} \]
把第一个式子代入第二个，由极小值时梯度为零易得：
\[ \mathbf w^{t+1} = \mathbf w^t - \eta^t\mathbf g^t - \eta^{t+\frac 1 2} \ \nabla\Psi(\mathbf w^{t+1}) \]
可以看出，这里与直接的 L1 正则损失的唯一区别是，这里有两个 \(\eta\)，而在前面这两个 \(\eta\) 是相等的。
L1 正则下的求解
L1-FOBOS 就是在上面取 L1 正则 \(\Psi(\mathbf w) = \lambda \ \left|\mathbf w \right|\)。引入记号 \(\mathbf v = \mathbf w - \eta \mathbf g\)，以及 $ \tilde \lambda = \eta^{t + \frac 1 2 } \lambda$，则前面的优化问题重新写为分量形式：
\[ w^{t+1}_i = arg\min_{w_i} \left\{\frac 1 2 (w_i - v_i)^2 + \tilde \lambda \left| w_i \right| \right\} \]
假设最优解是 \(w^*_i\)，后面省去下标 \(i\)，
\(w^* v \geq 0\)
证明：
因为 \(w^*\) 是最优解，所以有
\[ \frac 1 2 (w^*-v)^2 + \tilde \lambda \left|w^*\right| \geq \frac 1 2 v^2 \] 当 \(w^* = 0\) 时取等号。从而得到
\[ w^* v \geq w^{*2} + \tilde \lambda \left| w^* \right| \geq 0\]当 \(v \geq 0\) 时：
则 \(w^* \geq 0\)，引入拉格朗日乘子 \(\beta > 0\) 和约束条件 $\beta w^* = 0 $，优化目标
\[ \frac 1 2 (w^* - v)^2 + \tilde \lambda w^* - \beta w^* \] 易得极小值时的解 $ w^* = v-\tilde \lambda+\beta $。
- \(w^*>0\)， 此时有 \(\beta = 0\)，\(v>\tilde \lambda\)，$w^* = v-\tilde \lambda $
- \(w^* = 0\)，则有 \(v-\tilde\lambda +\beta=0\), \(\beta \geq 0\)，所以 $v \leq \tilde \lambda $
综合结果 \[w^* = \max(0, v-\tilde \lambda)\]
- 当 \(v <0\) 时：
类似上面的方法，得到
\[w^* = -\max(0, -v- \tilde\lambda)\]
综合以上结果，可得：
\[w^{t+1} = sgn(v_i)\max(0, \left|v_i\right| - \tilde\lambda ) = \begin{cases}
0, & if\ \left|v_i\right| \leq \tilde \lambda \\
v_i - \tilde\lambda, & if\ v_i > \tilde\lambda \\
v_i + \tilde\lambda, & if\ v_i < -\tilde\lambda \end{cases}\]
3，L1-RDA
RDA（Regularized Dual Averaging），由微软的 Lin Xiao 在 2010 年提出。优化目标是最小化 $\left{ \frac 1 2 \mathbf g^{1:t}\cdot \mathbf w + \Psi(\mathbf w) + \frac {\beta^t} t h(\mathbf w) \right} $，其中 \(\mathbf g^{1:t} = \sum_{s=1}^t \mathbf g^s\)，\(\Psi(\mathbf w)\) 是正则项，\(\beta^t\) 是非负非自减序列，\(h(\mathbf w)\) 是辅助的严格凸函数。
L1-RDA 具体的更新策略如下:
\[ \mathbf w^{t+1} = arg\min_w \left\{ \frac 1 2 \mathbf g^{1:t}\cdot \mathbf w + \lambda\left|\mathbf w\right|_1 + \frac {\gamma} {2\sqrt t} \lVert \mathbf w\rVert_2^2 \right\} \] 其中 \(\lambda > 0\), $\gamma > 0 $。为求解方便，令 \(\bar g_i^t = \frac 1 2 g_i^{1:t}\)， 写出最小化问题的分量形式：
\[ \min_{w_i} \left\{ \bar g_i^t w_i + \lambda \left| w_i \right| + \frac \gamma {2\sqrt t} w_i^2 \right\} \]
求上式梯度，并直接令梯度为零来寻找最优解 \(w_i^*\)：
\[ \bar g_i^t + \lambda \xi + \frac\gamma {\sqrt t} w_i^* = 0 \] 其中 \(\xi = \partial \left|w_i^*\right|\) 是正则项在最优点的次梯度，满足：
\[ \xi = \begin{cases}
1, & if\ w_i^* > 0 \\
-1, & if\ w_i^* < 0 \\
(-1,1) & if\ w_i^* = 0
\end{cases} \]
分情况分析：
- \(\left|\bar g_i^t\right| < \lambda\),
- \(w_i^* = 0\)， 则有 \(\xi = -\frac g \lambda \in (-1,0]\)， 满足条件。
- \(w_i^* > 0\)， 则 \(\xi = 1\)，$g + \lambda\xi + \frac \gamma {\sqrt t} w_i^* > g + \lambda \geq 0 $，条件相斥。
- \(w_i^* < 0\)，则 \(\xi = -1\)，\(g-\lambda + \frac \gamma {\sqrt t} w_i^* < 0\)，也不满足
所以此时 \(w_i^* = 0\)
2 . \(\bar g_i^t >\lambda\)
- \(w_i^* = 0\)，则有 \(\xi = -\frac g \lambda \in (-\infty,0)\)， 不满足
- $w_i^* > 0 $， 则有 \(\xi=1\)， $g + \lambda\xi + \frac \gamma {\sqrt t} w_i^* = -\frac {\sqrt t}\gamma g + \lambda \geq 0 $，不满足
- \(w_i^* < 0\)，则有 \(\xi = -1\)，\(w_i^* = -\frac{\sqrt t}\gamma(g-\lambda) < 0\)，满足条件
所以此时 \(w_i^* = -\frac{\sqrt t}\gamma(\bar g_i^*-\lambda)\)
3 . \(\bar g_i^t < -\lambda\)
- \(w_i^* = 0\)，则有 \(\xi = -\frac g \lambda \in (1, +\infty)\)， 不满足
- $w_i^* > 0 $， 则有 \(\xi=1\)， $w_i^* = - \frac {\sqrt t} \gamma (g + \lambda) > 0 $，与假设一致
- \(w_i^* < 0\)，则有 \(\xi = -1\)，\(w_i^* = -\frac{\sqrt t}\gamma(g-\lambda) > 0\)，与假设矛盾
所以此时 \(w_i^* = -\frac{\sqrt t}\gamma(\bar g_i^t+\lambda)\)
综上可得更新方式：
\[ w_i^{t+1} = \begin{cases}
0, & if \ \left|\bar g_i^t\right| < \lambda \\
-\frac{\sqrt t}\gamma \left(\bar g_i^t - \lambda \ sgn(\bar g_i^t) \right) &if\ \left|\bar g_i^t\right| > \lambda
\end{cases}\]
总结，RDA 主要计算每一维的累积平均梯度，与 \(\lambda\) 相比来做截断，更新权重。更新的幅度与迭代次数 \(t\) 直接相关，但在模型的构建中，并不需要指定学习步长。
Algorithms
- input \(\lambda\)，\(\gamma\)
- initial \(\mathbf w \in \mathbb R^N\)， \(\mathbf g \in \mathbb R^N\)
- for \(t = 1,2,3,\cdots\)， do
\(\quad \mathbf g \gets \frac{t-1}t\mathbf g + \frac 1 t \nabla \ell(\mathbf w)\)
refresh \(\mathbf w\) by
\(\quad w_i = \begin{cases} 0, & if \ \left|g_i\right| < \lambda \\ -\frac{\sqrt t}\gamma \left(g_i - \lambda \ sgn(g_i) \right) &if\ \left|g_i\right| > \lambda \end{cases}\)- end
- return \(\mathbf w\)
4，FTRL
L1-FOBOS 的优化目标分量形式可写为：
\[\min_w\left\{ \frac 1 2 (w_i - w_i^{t} - \eta^t g_i^t)^2 + \eta^t \lambda \left|w_i\right| \right\} \\
= \min_w\left\{ \frac 1 2 (w_i - w_i^t)^2 + w_i \eta^t g_i^t + \eta^t \lambda \left|w_i\right| + const \right\} \\
= \min_w\left\{ \frac 1 {2 \eta^t} (w_i - w_i^t)^2 + w_i g_i^t + \lambda \left|w_i\right| \right\} \]
由此重新写出更新公式：
\[ \mathbf w^{t+1} = arg\min_w \left\{ \mathbf g^t \cdot \mathbf w + \lambda \rVert\mathbf w\lVert_1 + \frac 1 {2\eta^t} \lVert \mathbf w - \mathbf w^t \rVert_2^2 \right\} \]
而 L1-RDA 的更新策略可以写为：
\[ \mathbf w^{t+1} = arg\min_w \left\{ \mathbf g^{1:t}\cdot \mathbf w + \lambda\lVert \mathbf w\rVert_1 + \frac 1 {2 \eta^t} \lVert \mathbf w - 0\rVert_2^2 \right\} \]
引入替代“更新步长“的量 \(\sigma^s = \frac 1 {\eta^s} - \frac 1 {\eta^{s-1}}\)，则有 \(\sigma^{1:t} \equiv \sum_{s=1}^t \sigma^s= \frac 1 {\eta^t}\)。上面两种模型，L1_FOBOS 和 L1-RDA 的更新策略重新写为：
\[ \begin{aligned}
\mathbf w^{t+1} = & arg\min_w \left\{ \mathbf g^t \cdot \mathbf w + \lambda \rVert\mathbf w\lVert_1 + \frac 1 2\sigma^{1:t} \lVert \mathbf w - \mathbf w^t \rVert_2^2 \right\} \\
\mathbf w^{t+1} = & arg\min_w \left\{ \mathbf g^{1:t}\cdot \mathbf w + \lambda\lVert \mathbf w\rVert_1 + \frac 1 2 \sigma^{1:t} \lVert \mathbf w - 0\rVert_2^2 \right\}
\end{aligned}\] 其区别于相似之处非常明显。
FTRL结合两种特点，更新策略为：
\[\mathbf w^{t+1} = arg\min_w \left\{ \mathbf g^{1:t}\cdot \mathbf w + \lambda_1\lVert \mathbf w\rVert_1 + \frac 1 2 \lambda_2 \lVert \mathbf w\rVert_2^2 + \frac 1 2 \sum_{s=0}^t \sigma^s \lVert \mathbf w - \mathbf w^s \rVert_2^2 \right\} \]
为了求解，将上式整理为：
\[ \begin{aligned}
\mathbf w^{t+1} = & arg\min_w \left\{ (\mathbf g^{1:t} - \sum_{s=1}^t \sigma^s \mathbf w^s)\cdot \mathbf w + \lambda_1\lVert \mathbf w\rVert_1 + \frac 1 2 (\lambda_2 + \sigma^{1:t}) \lVert \mathbf w\rVert_2^2 + const \right\} \\
= & arg\min_w \left\{\mathbf z^t \cdot \mathbf w + \lambda_1\lVert \mathbf w\rVert_1 + \frac 1 2 (\lambda_2 + \sigma^{1:t}) \lVert \mathbf w\rVert_2^2 \right\}
\end{aligned} \]
其中已引入 \(\mathbf z^t \equiv \sum_{s=1}^t(\mathbf g^s - \sigma^s \mathbf w^s)\)。
类似于之前的方法，首先将上式写成分量形式 $ \min_w \left{z_i^t w_i + \lambda_1 \left| w_i \right| + \frac 1 2 (\lambda_2 + \sigma^{1:t}) w_i^2 \right}$，分析即可得到结果：
\[ w_t^{t+1} =
\begin{cases}
0, & if \ \left| z_i \right| < \lambda_1 \\
- \frac 1 {\lambda_2 + \sigma^{1:t}} \left(z_i^t - \lambda_1\ sgn(z_i^t) \right), & if \ \left| z_i \right| > \lambda_1
\end{cases} \]
建议的学习步长的取值方式为：
\[ \sigma_i^{1:t} = \frac 1 {\eta_i^t} = \frac {\beta + \sqrt {\sum_{s=1}^t \left( g_i^s \right)^2 } } \alpha \] 即不同特征的权重的更新步长也不相同。
Algorithm
input \(\alpha\), \(\beta\), \(\lambda_1\), \(\lambda_2\)
initialize \(\mathbf w \in \mathbb R^N\), \(\mathbf z= \vec 0 \in \mathbb R^N\), \(\mathbf n = \vec 0 \in \mathbb R^N\)
for \(t = 1,2,3,...\), do
\(\quad \mathbf g = \nabla \ell(\mathbf w; \mathbf x^t, y^t)\)
\(\quad\)for \(i = 1,2,3,...,N\), do
\(\qquad \sigma_i = \frac 1 \alpha \left( \sqrt{n_i + g_i^2} - \sqrt{n_i} \right)\)
\(\qquad z_i \gets z_i + (g_i - \sigma_i w_i^t)\)
\(\qquad n_i \gets n_i + g_i^2\)
\(\qquad w_i = \begin{cases} 0, & if \ |z_i| \leq \lambda_1 \\ - \left(\frac{\beta + \sqrt{n_i} } \alpha + \lambda_2 \right)^{-1} (z_i - sgn(z_i) \lambda_1 ) & otherwise \end{cases}\)
\(\quad\) end for
end for