总目录

一、 凸优化基础（Convex Optimization basics）

1. 凸优化基础（Convex Optimization basics）

二、 一阶梯度方法（First-order methods）

1. 梯度下降（Gradient Descent）
2. 次梯度（Subgradients）
3. 近端梯度法（Proximal Gradient Descent）
4. 随机梯度下降（Stochastic gradient descent）
   待更新。。。

Introduction

前面介绍过了多种梯度下降的方法，当数据规模比较小时，我们可以使用这些方法计算在所有数据上的梯度并进行更新迭代。而当数据规模比较大时，每次计算所有数据梯度的开销将会非常巨大。由于随机梯度下降可以大大减小计算开销，因此常用于大规模数据优化中。

随机梯度下降

考虑这样一个最优化问题
$\min_{x}\frac{1}{m}\sum^{m}_{i=1}f_i(x)$xmin​m1​i=1∑m​fi​(x)
即最小化一系列函数的平均值。该问题的梯度为$\nabla \sum^{m}_{i=1}f_i(x)=\sum^{m}_{i=1}\nabla f_i(x)$∇∑i=1m​fi​(x)=∑i=1m​∇fi​(x)。常规的梯度下降就是不断迭代：
$x^{(k)}=x^{(k-1)}-t_k\cdot \frac{1}{m}\sum^m_{i=1}\nabla f_i(x^{(k-1)}),\qquad k=1,2,3,...$x(k)=x(k−1)−tk​⋅m1​i=1∑m​∇fi​(x(k−1)),k=1,2,3,...

而随机梯度下降（SGD）则是迭代：
$x^{(k)}=x^{(k-1)}-t_k\cdot \nabla f_{i_k}(x^{(k-1)}),\qquad k=1,2,3,...$x(k)=x(k−1)−tk​⋅∇fik​​(x(k−1)),k=1,2,3,...

其中，$i_k\in \{1,...,m\}$ik​∈{1,...,m}是在第k次迭代中被选择的函数索引。

有两种方式选择$i_k$ik​:

• 随机方式：从取值范围中均匀随机选择$i_k\in \{1,...,m\}$ik​∈{1,...,m}
• 循环方式：依次选取$i_l=1,2,...,m,1,2,...,m,...$il​=1,2,...,m,1,2,...,m,...

其中，随机方式是实践中最常用的，对于随机方式来说：
$E[\nabla f_{i_k}(x)]=\nabla f(x)$E[∇fik​​(x)]=∇f(x)

因此我们可以把SGD的每一步看做是梯度的无偏估计。
SGD将每个函数看成是独立的，每次只优化部分函数，可以大大节省内存消耗。

例子：随机逻辑回归（stochastic logistic regression）
给定$(x_i,y_i)\in R^p\times \{0,1\},i=1,...,n$(xi​,yi​)∈Rp×{0,1},i=1,...,n，逻辑回归定义为：
$\min_\beta \frac{1}{n}\sum^n_{i=1}(-y_ix^T_i\beta+log(1+\exp(x^T_i\beta)))$βmin​n1​i=1∑n​(−yi​xiT​β+log(1+exp(xiT​β)))

其梯度为$\nabla f(\beta)=\frac{1}{n}\sum^n_{i=1}(y_i-p_i(\beta))x_i$∇f(β)=n1​∑i=1n​(yi​−pi​(β))xi​
对于完全梯度下降来说：每次batch迭代更新的花费为$O(np)$O(np)，而对于SGD来说，每次随机迭代更新的花费为$O(p)$O(p)。
我们取$n=10$n=10，$p=2$p=2来看一下两者收敛曲线的比较：

我们可以看到SGD在离最优点比较远时收敛得比较快，而在接近最优点时比较难收敛到最优点。

步长的选择

通常SGD使用递减的步长，比如$t_k=1/k$tk​=1/k。如果使用固定步长，则在接近最优点时会很难继续收敛。

收敛率

在以前的章节里提到，对于凸函数$f$f，使用递减步长的梯度下降方法的收敛率为$O(1/\sqrt{k})$O(1/k​)。当$f$f可微且有Lipshitz梯度时，对于合适的固定步长有$O(1/k)$O(1/k)的收敛率。那么对于SGD如何呢？对于凸函数$f$f，使用递减步长的SGD的期望收敛率为$O(1/\sqrt(k))$O(1/(​k))。然而，与梯度下降不同的是，SGD不会随着进一步假设$f$f有Lipshitz梯度而提升。甚至当$f$f是强凸时会变得更糟。
当$f$f是强凸且有Lipshitz梯度时，梯度下降有$O(\gamma^k)$O(γk)的收敛率，其中$0<\gamma<1$0<γ<1。但是相同条件下，SGD只有$O(1/k)$O(1/k)的期望收敛率。那么有没有什么方法可以提升SGD呢？

小批量随机梯度下降

常用的SGD是小批量随机梯度下降（mini-batch stochastic gradient descent）。我们随机选取一个子集$I_k\subseteq \{1,...,m\},\ |I_k|=b\ll m$Ik​⊆{1,...,m}, ∣Ik​∣=b≪m，然后重复迭代：
$x^{(k)}=x^{(k-1)}-t_k\cdot \frac{1}{b}\sum_{i\in I_k}\nabla f_i(x^{(k-1)}),\qquad k=1,2,3,...$x(k)=x(k−1)−tk​⋅b1​i∈Ik​∑​∇fi​(x(k−1)),k=1,2,3,...

使用小批量可以将方差减小$1/b$1/b，但同样要多花费$b$b倍时间。同时收敛率也有所提升。
再次考虑上面例子中的逻辑回归问题，当$n=10,000, p=20$n=10,000,p=20时，所有方法都用固定步长，可以得到：

但从总体结果来看，使用小批量随机梯度下降并不能显著提升总的开销和精度。

SGD在大规模机器学习中的应用

SGD被广泛应用于大规模机器学习（ML）中。

• 在许多ML问题中，我们往往不需要优化到很高的精度，因此固定步长常常应用于ML中
• 一个trick是在整个数据集上运行SGD之前，先在一小部分上进行训练，从而选取合适的步长。
• 动量（mometum），自适应步长等许多SGD的变体都是实践中常用的方法（如Adagrad，Adam等）
• SGD尤其流行于大规模、连续的非凸优化问题中

参考资料

CMU：Convex Optimization