MLlib 中的优化技术

• 数学描述 Mathematical description
  • 梯度下降 Gradient descent
  • 随机梯度下降 Stochastic gradient descent (SGD)
  • 分布式随机梯度下降更新策略 Update schemes for distributed SGD
  • 受限内存的 BFGS Limited-memory BFGS (L-BFGS)
  • 选择优化技术 Choosing an Optimization Method
• MLib 中的实现 Implementation in MLlib
  • 梯度下降和随机梯度下降 Gradient descent and stochastic gradient descent
  • L-BFGS
• Developer’s notes

数学描述

梯度下降

解决形如 $\min_{w \in \mathbb{R}^d} \; f(w)$ 优化问题的最简单的一类方法就是梯度下降。这种一阶的优化技术（包含梯度下降及其随机化变体）尤其适用于大规模分布式计算。

梯度下降方法的目标是通过迭代式依照最深的下降的方向移动一定的步长最终找到函数的局部最小值，最深的下降是指函数在当前点的导数（或者梯度）的负值。如果目标函数在所有的参数处都是不可微分的，却是凸函数，那么可以使用梯度的推广——子梯度（sub-gradient），将其当做是移动的方向。所有情况下，计算函数的梯度或者子梯度代价都很昂贵——因为计算出所有的损失项就需要对所有的数据集遍历。

随机梯度下降（SGD）

目标函数为 $f$ 的优化问题通常被写成一种和式的形式，特别方便用随机梯度下降方法解决。在我们的例子中，对在监督学习中常用的优化公式，

$f(\mathbf{w}) := \lambda R(\mathbf{w}) + \frac{1}{n} \sum_{i=1}^n L(w;\mathbf{x}_i,y_i).$

这个表示相当自然，因为损失是写成每个数据点的损失的平均值。

随机子梯度是随机选一个向量，使得在期望上能够得到原始目标函数的真实的子梯度。