Question

1. 常见的梯度下降法、牛顿法、拟牛顿法属于批学习batch 方法，每次迭代都需要对全量训练样本重新学习一遍。

   当面临搜索、推荐等高维度（数十亿甚至上百亿维度）、大尺度（百亿规模甚至千亿规模）数据的场景时，传统的批学习方法效率太低。

   解决该问题的方法是：在线学习 online learning 。

2. 最简单的在线学习策略是在线梯度下降Oneline Gradient Descent:OGD 。它是当 batch size = 1 的 mini-batch 随机梯度下降法的特殊情形。

   该算法每次迭代仅训练最新的样本，每个样本只被训练一次。

3. 不同于 mini-batch随机梯度下降，在 OGD 中，算法每次梯度更新并不是沿着全局梯度的负方向进行前进，而是带有非常大的随机性。

   这样即使采用 L1 正则化，模型也很难产生稀疏解。而在线学习过程中，稀疏性是一个主要追求目标，因为稀疏解有以下优点：

   • 可以降低有效特征数量，起到特征选择作用
   • 降低模型大小
   • 线上预测时，降低计算量

11.1 梯度截断法 TG

1. 为得到稀疏解，最简单的方式是进行梯度截断：每隔 $ k $ 步，当权重低于阈值 $ \tau $ 时截断为 0 。

   $ \vec\theta^{(t+1)} = \begin{cases} \vec\theta^{(t)} - \epsilon^{(t)} \mathbf{\vec g}^{(t)},& t\%k \ne 0\\ T_0(\vec\theta^{(t)} - \epsilon^{(t)} \mathbf{\vec g}^{(t)};\tau),&t\%k = 0 \end{cases} $

   其中：

   $ T_0(z;\tau) = \begin{cases} 0,& |z| \le \tau\\ z, & |z| \gt \tau \end{cases} $

   该方法容易理解、实现简单，但是实际中很少应用。因为权重系数较小的原因，很可能是因为该维度训练不足（如出现该特征的样本太少）引起的，并不是因为该特征不重要引起的。简单的截断可能造成该部分特征丢失。

2. 梯度截断法 Truncated Gradient:TG 是对简单截断的一种改进。当权重低于阈值 $ \tau $ 时，它不是直接降低到 0 ，而是慢慢降低到 0 。

   $ \vec\theta^{(t+1)} = \begin{cases} \vec\theta^{(t)} - \epsilon^{(t)} \mathbf{\vec g}^{(t)},& t\%k \ne 0\\ T_1(\vec\theta^{(t)} - \epsilon^{(t)} \mathbf{\vec g}^{(t)};\lambda k\epsilon^{(t)};\tau),&t\%k = 0 \end{cases} $

   其中：

   $ T_1(z;\alpha,\tau) = \begin{cases} \max(0,z-\alpha) ,& 0\le z\le \tau\\ \min(0,z+\alpha),& -\tau \le z \le 0\\ z ,& z \gt |\tau| \end{cases} $
   • $ \lambda,\tau $ 决定了参数的稀疏程度。这两个值越大，则模型的稀疏性越强。
   • 当 $ \lambda k \epsilon^{(t)} = \tau $ 时，即 $ \alpha = \tau $ ，则有 $ T_1(z;\alpha;\tau) = T_0(z;\tau) $ 。此时 TG 法退化到简单截断法。

   下图中，x 表示 z， $ \theta $ 表示 $ \tau $

   

11.2 FOBOS

1. 前向后向切分FOBOS:Forward-Backward Splitting 将权重更新分为两个步骤：

   $ \vec\theta^{(t+1/2)} = \vec\theta^{(t)} - \epsilon^{(t)}\mathbf{\vec g}^{(t)}\\ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} \left(\frac 12 ||\vec\theta - \vec\theta^{(t+1/2)}||^2 + \epsilon^{(t+1/2)} \Psi(\vec\theta)\right) $

   其中 $ \Psi(\vec\theta) $ 用于对参数进行正则化。

   该更新过程分为两步：

   • 第一步为标准的梯度下降

   • 第二步对梯度下降的结果进行微调。其中：

     • $ \frac 12 ||\vec\theta - \vec\theta^{(t+1/2)}||^2 $ 为距离约束，用于保证微调发生在梯度下降结果的附近
     • $ \epsilon^{(t+1/2)} \Psi(\vec\theta) $ 为正则化，用于产生稀疏性。 $ \epsilon^{(t+1/2)} $ 是正则化的学习率。

2. 将第一步方程代入第二步，有：

   $ J(\vec\theta) = \frac 12 ||\vec\theta-\vec\theta^{(t)} + \epsilon^{(t)}\mathbf{\vec g}^{(t)}||^2 + \epsilon^{(t+1/2)}\Psi(\vec\theta)\\ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} J(\vec\theta) $

   为求得最优解，根据梯度为零有：

   $ \nabla_{\vec\theta} J = \mathbf{\vec 0} \rightarrow \vec\theta-\vec\theta^{(t)} + \epsilon^{(t)} \mathbf{\vec g}^{(t)} + \epsilon^{(t+1/2)} \nabla_{\vec\theta}\Psi(\vec\theta) = \mathbf{\vec 0} $

   因此有：

   $ \vec\theta^{(t+1)} = \vec\theta^{(t)} - \epsilon^{(t)}\mathbf{\vec g}^{(t)} - \epsilon^{(t+1/2)}\nabla_{\vec\theta}\Psi(\vec\theta^{(t+1)}) $

   可以看到：

   • $ \vec\theta^{(t+1)} $ 不仅与迭代期的状态 $ \vec\theta^{(t)} $ 有关，还和迭代后的状态 $ \vec \theta^{(t+1)} $ 有关。这就是 “前向”、“后向” 的由来。
   • FOBOS 与常规梯度下降在于 FOBOS 多了一项： $ - \epsilon^{(t+1/2)}\nabla_{\vec\theta}\Psi(\vec\theta^{(t+1)}) $ 。

3. 当在 L1 正则化下， $ \Psi(\vec\theta) = \lambda ||\vec\theta||_1 $ 。令 $ \vec\theta = (\theta_1,\cdots,\theta_d)^T $ ，记 $ \tilde \lambda = \lambda \epsilon ^{(t+1/2)} $ 则有：

   $ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} \sum_{i=1}^d\left(\frac 12 ( \theta_i - \theta_i^{(t+1/2)})^2 + \tilde\lambda |\theta_i|\right) $

   由于求和项中每一项都是非负的，因此当每一项都最小时，整体最小。即：

   $ \theta_i^{(t+1)} = \arg\min_{\theta_i}\left(\frac 12 ( \theta_i - \theta_i^{(t+1/2)})^2 + \tilde\lambda |\theta_i|\right) $

   设 $ \theta_i^* $ 是最优解，则必有 $ \theta_i^* \times \theta_i^{(t+1/2)} \ge 0 $ 。如果 $ \theta_i^* \times \theta_i^{(t+1/2)} \lt 0 $ ，则有：

   $ \left(\frac 12 ( \theta_i - \theta_i^{(t+1/2)})^2 + \tilde\lambda |\theta_i|\right)\mid_{\theta_i = 0} = \frac 12 \left(\theta_i^{(t+1/2)}\right)^2\\ \lt \frac 12 \left(\theta_i^{(t+1/2)}\right)^2 - \theta_i^*\times \theta_i^{(t+1/2)} + \frac 12 \left(\theta_i^*\right)^2 \\ \lt \frac 12\left(\theta_i^* -\theta_i^{(t+1/2)} \right)^2 + \tilde \lambda |\theta_i^*| = \left(\frac 12 ( \theta_i - \theta_i^{(t+1/2)})^2 + \tilde\lambda |\theta_i|\right)\mid_{\theta_i = \theta_i^*} $

   因此 $ \theta_i^* $ 必然不是最优解，矛盾。

   既然有 $ \theta_i^* \times \theta_i^{(t+1/2)} \ge 0 $ ，则分情况讨论：

   • 当 $ \theta_i^{(t+1/2)} \ge 0 $ 时，则有 $ \theta_i^{*} \ge 0 $ ，则原始问题转化为：

     $ \arg\min_{\theta_i}\left(\frac 12 ( \theta_i - \theta_i^{(t+1/2)})^2 + \tilde\lambda \theta_i \right)\\ s.t.\quad \theta_i\ge 0 $

     解得： $ \theta^{(t+1)}_i = \theta^*_i = \max(0,\theta_i^{(t+1/2)}-\tilde \lambda) $

   • 当 $ \theta_i^{(t + 1/2)}\lt 0 $ 时，有 $ \theta_i^*\lt 0 $ ，则原始问题转化为：

     $ \arg\min_{\theta_i}\left(\frac 12 ( \theta_i - \theta_i^{(t+1/2)})^2 - \tilde\lambda \theta_i \right)\\ s.t.\quad \theta_i\lt 0 $

     解得： $ \theta^{(t+1)}_i = \theta^*_i = - \max(0,-\theta_i^{(t+1/2)}-\tilde \lambda) $

   因此得到 FOBOS 在 L1 正则化条件下的更新方程：

   $ \theta_i^{(t+1)} = \text{sgn}(\theta_i^{(t + 1/2)}) \times \max(0,|\theta_i^{(t + 1/2)}| - \tilde\lambda)\\ = \text{sgn}\left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right)\times \max\left(0, \left|\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right|-\epsilon^{(t+1/2)}\lambda\right) $

   其中 $ \text{sgn}(z) $ 为符号函数：当 $ z \lt 0 $ 时取值为 -1；当 $ z\gt 0 $ 时取值为 1；当 $ z=0 $ 时取值为 0 。

4. 重新调整更新公式：

   $ \theta_i^{(t+1)} = \begin{cases} 0,&\text{if}\; \left|\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right|\le \epsilon^{(t+1/2)}\lambda\\ \left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right) - \epsilon^{(t+1/2)}\lambda \times \text{sgn}(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}),&\text{else} \end{cases} $

   • 当一条样本产生的梯度 $ g^{(t)}_i $ 不足以对维度 $ i $ 的权重产生足够大的变化时，权重 $ \theta_i $ 被截断为 0 。

   • 当 $ k=1 $ ， $ \tau = +\infty $ ，TG 更新方程退化为：

     $ \theta^{(t+1)}_i = \begin{cases} \max(0,\left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right)-\lambda_{TG}\epsilon^{(t)}) ,& 0\le \left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right) \\ \min(0,\left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right)+\lambda_{TG}\epsilon^{(t)}),& \left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right) \le 0 \end{cases}\\ = \begin{cases} 0 ,& \text{if}\quad \left|\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right| \le \lambda_{TG}\epsilon^{(t)})\\ \left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right) - \lambda_{TG}\epsilon^{(t)}\times \text{sgn}\left(\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right)，&\text{else} \end{cases} $

     因此当 $ \epsilon^{(t)} \lambda_{TG} = \epsilon^{(t+1/2)}\lambda $ 时 ，TG 退化为 L1-FOBOS 。

11.3 RDA

1. TG,FOBOS 等算法都是基于随机梯度下降 SGD 算法而来，而正则对偶平均 Regularized Dual Averaging: RDA 算法是基于简单对偶平均法 Simple Dual Averaging Scheme 而来。

   RDA 的权重特新方程为：

   $ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} \left(\frac 1t\sum_{s=1}^t \mathbf{\vec g}^{(s)}\cdot \vec\theta +\Psi(\vec\theta) + \frac{\beta^{(t)}}{t}h(\vec\theta) \right) $

   其中：

   • $ \frac 1t\sum_{s=1}^t \mathbf{\vec g}^{(s)}\cdot \vec\theta $ 表示梯度 $ \mathbf{\vec g} $ 对 $ \vec\theta $ 的积分中值（积分平均值）
   • $ \Psi(\vec\theta) $ 为正则化项
   • $ h(\vec\theta) $ 是一个辅助的严格凸函数
   • $ \{\beta^{(t)} \mid t\ge 1\} $ 是一个非负的非递减序列

2. 在 L1 正则化的情况下， $ \Psi(\vec\theta) = \lambda||\vec\theta||_1 $ 。设 $ h(\vec\theta) = \frac 12 ||\vec\theta||_2^2 $ ，它满足严格凸函数的条件。设 $ \beta^{(t)} = \gamma \sqrt t $ ，它满足非负非递减。则有：

   $ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} \left(\frac 1t\sum_{s=1}^t \mathbf{\vec g}^{(s)}\cdot \vec\theta +\lambda ||\vec\theta||_1 + \frac{\gamma}{2\sqrt t}||\vec\theta||_2^2 \right) $

   将其拆解为各维度的最小化问题，则有：

   $ \theta_{i}^{(t+1)} = \arg\min_{\theta_i} \left(\bar g_i^{(t)}\theta_i +\lambda | \theta_i| + \frac{\gamma}{2\sqrt t} \theta_i^2 \right) $

   其中 $ \bar g_i^{(t)} = \frac 1t\sum_{s=1}^t g_i^{(s)} $ 为所有梯度的均值。

   求解该方程，得到权重更新公式：

   $ \theta_i^{(t+1)} = \begin{cases} 0,& \text{if}\quad |\bar g_i^{(t)}| \lt \lambda\\ -\frac{\sqrt t}{\gamma}\left(\bar g_i^{(t)} - \lambda\times\text{sgn}(\bar g_{i}^{(t)})\right),&\text{else} \end{cases} $

   因此当维度 $ i $ 上的累积梯度均值的绝对值小于 $ \lambda $ 时，发生阈值截断。

3. L1-RDA 和 L1-FOBOS 的比较：

   • 对于L1-FOBOS ，当 $ \left|\theta_i^{(t)} - \epsilon^{(t)}g_i^{(t)}\right| \le \epsilon^{(t+1/2)}\lambda $ 时执行梯度截断。通常选择 $ \epsilon^{(t+1/2)} $ 时随着时间 $ t $ 下降的，因此 L1-FOBOS 的截断阈值是随着时间变化的。

     而 L1-RDA 的截断阈值 $ \lambda $ 是固定的常数，因此相比 L1-FOBOS 更激进，也更容易产生稀疏性。

   • L1-RDA 基于梯度的累积均值 $ \bar g_i^{(t)} $ 来判断，而 L1-FOBOS 基于最近的单次梯度 $ g_i^{(t)} $ 来判断。

     而梯度累积均值比单次梯度更稳定。

   • L1-RDA 的更新过程中， $ \theta_i^{(t+1)} $ 与前一时刻的 $ \theta_i^{(t)} $ 无关，仅仅由梯度累积均值 $ \bar g_i^{(t)} $ 来决定。

     而 L1-FOBOS 的更新过程中， $ \theta_i^{(t+1)} $ 由前一时刻的 $ \theta_i^{(t)} $ 、 $ g_i^{(t)} $ 共同决定。

11.4 FTRL

1. 实验证明：L1-FOBOS 这类基于梯度下降的方法具有较高的精度，但是 L1-RDA 却具有更好的稀疏性。Follow the Regularized Leader : FTRL 结合了两者的优点：即具有较好的稀疏性，又具有较高的精度。

2. FTRL 综合考虑了 FOBOS 和 RDA ，其特征权重更新公式为：

   $ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} \left(\sum_{s=1}^t\mathbf{\vec g}^{(s)}\cdot \vec\theta + \lambda_1||\vec\theta||_1 + \lambda_2\frac 12 ||\vec\theta||_2^2+\frac 12 \sum_{s=1}^t\sigma^{(s)}||\vec\theta-\vec\theta^{(s)}||_2^2\right) $

   其中 $ \lambda_1,\lambda_2,\sigma^{(s)}\gt 0 $ 为超参数。

   重新调整最优化目标为：

   $ \left( \sum_{s=1}^t\left(\mathbf{\vec g}^{(s)} - \vec\theta^{(s)}\right)\cdot \vec\theta + \lambda_1||\vec\theta||_1 + \frac 12\left(\lambda_2 +\sum_{s=1}^t\sigma^{(s)}\right) ||\vec\theta||_2^2 + \frac 12 \sum_{s=1}^t\sigma^{(s)}||\vec\theta^{(s)}||_2^2 \right) $

   令 $ \mathbf{\vec z}^{(t)} = \sum_{s=1}^t\left(\mathbf{\vec g}^{(s)} - \vec\theta^{(s)}\right) $ ，考虑到最后一项与 $ \vec\theta $ 无关，因此有：

   $ \vec\theta^{(t+1)} = \arg\min_{\vec\theta} \left(\mathbf{\vec z}^{(t)}\cdot \vec\theta+\lambda_1||\vec\theta||_1 + \frac 12\left(\lambda_2 +\sum_{s=1}^t\sigma^{(s)}\right) ||\vec\theta||_2^2 \right) $

   将其拆解为各维度的最小化问题，则有：

   $ \theta_{i}^{(t+1)} = \arg\min_{\theta_i} \left(z_i^{(t)} \theta_i + \lambda_1 |\theta_i| + \frac{\lambda_2 + \sum_{s=1}^t\sigma^{(s)}}{2}\theta_i^2\right) $

   求解该最优化问题，得到 FTRL 的参数更新方程：

   $ \theta_i^{(t+1)} = \begin{cases} 0,& \text{if}\quad |z_i^{(t)}|\lt \lambda_1\\ - \left(z_i^{(t)}-\lambda_1 \times\text{sgn}\left(z_i^{(t)}\right)\right)/\left(\lambda_2 + \sum_{s=1}^t\sigma^{(s)}\right),&\text{else} \end{cases} $

   因此 L1 正则化项引入稀疏性，L2 正则化项平滑求解结果。

3. 对于TG,FOBOS 等基于随机梯度下降的算法，学习率通常是全局的：每个维度的学习率都是相同的。如： $ \epsilon^{(t)} = \frac {1}{\sqrt t} $ 。

   RDA 算法没有学习率的概率，该算法未用到学习率。

   在 FTRL 算法中，不同维度的学习率是单独考虑的 Per-Coordinate Learning Rates 。

   $ \epsilon^{(t)}_i = \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^t\left(g_i^{(s)}\right)^2}} $

   这是由于：

   • 如果某个特征的变化更快（梯度更大），说明损失函数在这一带变化比较剧烈，则我们学习的步伐减缓（学习率更小）。
   • 如果某个特征变化更慢（梯度更小），说明损失函数在这一带非常平缓，则我们学习的步伐可以加快（学习率更大）。

   同时 $ \sigma^{(t)} $ 也是每个维度不同。令：

   $ \sigma^{(t)}_i = \frac{1}{\epsilon_i^{(t)}} - \frac{1}{\epsilon_i^{(t-1)}}\gt 0 $

   则有：

   $ \sum_{s=1}^t\sigma_i^{(t)} = \frac{1}{\epsilon_i^{(t)}}= \frac{\beta + \sqrt{\sum_{s=1}^t\left(g_i^{(s)}\right)^2}}{\alpha} $

   .