首页 计算机 机器学习 主文献阅读

# Outline

  • First-order optimization
  • SGD and its variants

# 机器学习回顾

  • A set of data: X={xn}n=1N⊂XX = \{x_n\}_{n=1}^N \subset \mathcal{X}, optionally, with labels Y={y}n=1N⊂YY = \{y\}_{n=1}^N \subset \mathcal{Y}.
  • A loss function L:Y×Y↦RL : \mathcal{Y} \times \mathcal{Y} \mapsto \mathbb{R}.
  • A model with parameter Mθ:X↦YM_{\theta}: \mathcal{X} \mapsto \mathcal{Y}.
  • A training task:

    min⁡θ∈Ω∑n=1NL(Mθ(xn),yn)⏟f(θ)\min_{\theta \in \Omega} \underbrace{\sum_{n=1}^N L(M_θ(\bm{x}_n), \bm{y}_n)}_{f(\theta)}

    • f(θ)f(\theta): the objective function of the variable θ\theta.
    • Ω\Omega: the feasible domain of θ\theta.

# Case 1 - 简单的股价预测问题

问题的输入是：

  • xn∈R2\bm{x}_n \in \mathbb{R}^2: 代表第 nn 个公司的营业额和利润；
  • yn∈R\bm{y}_n \in \mathbb{R}: 代表第 nn 个公司的股价。

一个使用 MSE 的线性回归是一个平滑的 (smooth)、凸的 (complex) 优化问题，是最简单的优化问题。

# 优化问题的难度

因此，一个优化问题的难度取决于以下三点：

  1. 凸性
  2. 平滑性
  3. 是否有约束

# 凸性

# 定义

一个（下）凸函数 f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} 定义在凸集 Ω⊂Rn\Omega \subset \mathbb{R}^n 上，如果对于任意的 x1,x2∈Ω\bm{x}_1, \bm{x}_2 \in \Omega 和任意的 λ∈[0,1]\lambda \in [0, 1]，都有

f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2).f(\lambda \bm{x}_1 + (1 - \lambda) \bm{x}_2) \leq \lambda f(\bm{x}_1) + (1 - \lambda) f(\bm{x}_2).

一般地，满足 Jenson 不等式

f(E(X))≤E(f(X))f(\mathbb{E}(X)) \leq \mathbb{E}(f(X))

的函数称为凸函数。

另一种凸函数的定义是

f(x′)−f(x)≥⟨∇f(x),x′−x⟩.f(\bm{x}') - f(\bm{x}) \geq \langle \nabla f(\bm{x}), \bm{x}' - \bm{x}\rangle.

其几何含义是，函数始终位于其切线上方。

这一等式可能不那么显然，但是其一阶情况为

f(x′)−f(x)≥f′(x)(x′−x).f(x') - f(x) \geq f'(x)(x'-x).

基于凸函数定义

f(x+t(x′−x))≤(1−t)f(x)+tf(x′),f(x + t(x'-x)) \leq (1-t)f(x) + tf(x'),

即

f(x′)≥f(x)+f(x+t(x′−x))−f(x)t.f(x') \geq f(x) + \frac{f(x + t(x'-x)) - f(x)}{t}.

令 t→0t \to 0, 即得上述定义。

# 一阶优化

光滑函数的梯度下降过程为

θ(k+1)=θ(k)−τk∇f(θ(k)).\theta^{(k+1)} = \theta^{(k)} - \tau_k \nabla f(\theta^{(k)}).

非光滑函数的次梯度下降过程为

θ(k+1)=θ(k)−τkg(k),g(k)∈∂f(θ(k)).\theta^{(k+1)} = \theta^{(k)} - \tau_k \bm{g}^{(k)}, \bm{g}^{(k)} \in \partial f(\theta^{(k)}).

于是显然有

∥θ(k+1)−θ∥2=∥θ(k)−θ∥2−2τk⟨g(k),θ(k)−θ⟩+τk2∥g(k)∥2.\|\theta^{(k+1)} - \theta\|^2 = \|\theta^{(k)} - \theta\|^2 - 2\tau_k \langle \bm{g}^{(k)}, \theta^{(k)} - \theta \rangle + \tau_k^2 \|\bm{g}^{(k)}\|^2.

# 一阶优化收敛速度的衡量

对于一个收敛序列 {θ(k)∣k=1,2,…}\{\theta^{(k)}|k=1,2,\dots\} 以及其极限 lim⁡k→∞θ(k)=θ\lim_{k \to \infty} \theta^{(k)} = \theta, 有：

lim⁡k→∞∥θ(k+1)−θ∥∥θ(k)−θ∥={1,Sublinear Convergence.r∈(0,1),Linear Convergence.0,Superlinear Convergence.\lim_{k \to \infty} \frac{\|\theta^{(k+1)} - \theta\|}{\|\theta^{(k)} - \theta\|} = \left\{ \begin{matrix} 1, & \text{Sublinear Convergence}. \\ r \in (0, 1), & \text{Linear Convergence}. \\ 0, & \text{Superlinear Convergence}. \\ \end{matrix} \right.

# 渐近收敛速度和非渐近收敛速度

渐近收敛速度用来刻画问题，非渐近收敛速度用来刻画算法。