Lecture 4

Learning with Gradient Descent

回顾:经验风险最小化与梯度下降

为每个预测器分配一个dd维的参数向量,也即每一个dd维参数向量对应一个预测器。并将经验风险最小化视作一个优化问题:

minimize:R(hw)=1ni=1nL(hw(xi),yi)  over  wRd\text{minimize}:R(h_w)=\frac{1}{n}\sum_{i=1}^nL(h_w(x_i),y_i) \; \text{over} \; w \in \mathbb{R}^d

通常,我们将经验风险视作关于参数ww的函数:

f(w)=R(hw)=1ni=1nL(hw(xi),yi)=1ni=1nfi(w)f(w)=R(h_w)=\frac{1}{n}\sum_{i=1}^nL(h_w(x_i),y_i)=\frac{1}{n}\sum_{i=1}^nf_i(w)

依照下式的法则,迭代地降低经验风险损失的值。

wt+1=wtαtf(wt)=wtαt1ni=1nfi(w)w_{t+1}=w_t-\alpha_t \cdot \nabla f(w_t) = w_t - \alpha_t \cdot \frac{1}{n}\sum_{i=1}^n \nabla f_i(w)

其中, wtw_t 表示迭代tt轮时的参数向量, αt\alpha_t 是学习率, f\nabla f 表示 ff 的梯度(偏导数向量,具体的计算与损失函数的形式有关)。

牛顿迭代法

通常用于非线性函数的优化。

将参数初始化为 w0Rdw_0 \in \mathbb{R}^d ,按下式对经验风险进行迭代:

wt+1=wt(2f(wt))1f(wt)w_{t+1}=w_t-(\nabla^2f(w_t))^{-1}\nabla f(w_t)

其中, 2f\nabla^2f 表示 ff 的 Hessian 矩阵(二阶偏导数矩阵)。这一方法能够更快收敛,因为它是二阶优化方法(使用 ff 的二阶导数),而梯度下降只是一阶方法(使用 ff 的一阶导数)。

问题:梯度下降和牛顿法的计算成本是多少?不考虑训练数据集,需要多少内存?(假设计算样本损失的梯度能够在 O(d)O(d) 的时间复杂度内解决)

  • 梯度下降法

  • 计算梯度:由于计算样本损失的梯度能够在 O(d)O(d) 的时间复杂度内解决,则计算 nn 个样本损失梯度的时间复杂度为 O(nd)O(n \cdot d)

  • 更新参数:使用计算得到的梯度更新参数 ww,这一操作的时间复杂度为 O(d)O(d)

综上,梯度下降法每次迭代的计算成本为 O(nd)O(n \cdot d)

  • 空间复杂度

    (1)储存参数向量 ww ,需要 O(d)O(d) 的内存。

    (2)储存梯度 f(w)\nabla f(w) ,需要 O(d)O(d) 的内存。

综上,梯度下降法的内存需求为 O(d)O(d)

  • 牛顿法

  • 计算梯度:由于计算样本损失的梯度能够在 O(d)O(d) 的时间复杂度内解决,则计算 nn 个样本损失梯度的时间复杂度为 O(nd)O(n \cdot d)

  • 计算 Hessian 矩阵:因为每个样本的 Hessian 矩阵是一个 d×dd \times d 的矩阵,所以计算每个样本对 Hessian 矩阵的贡献的时间复杂度为 O(d2)O(d^2),计算所有样本的为 O(nd2)O(n \cdot d^2) 。实例见计算非线性函数的 Hessian 矩阵

  • 求解线性系统 (2f(w))1f(w)(\nabla ^2f(w))^{-1}\nabla f(w):通常需要进行矩阵求逆或使用其他方法(如 Cholesky 分解)来求解,时间复杂度一般为 O(d3)O(d^3)

综合以上分析,牛顿法每次迭代的计算成本为 O(nd2+d3)O(nd^2+d^3)

  • 空间复杂度

    (1)储存参数向量 ww ,需要 O(d)O(d) 的内存。

    (2)储存梯度 f(w)\nabla f(w) ,需要 O(d)O(d) 的内存。

    (3)储存 Hessian 矩阵 2f(w)\nabla ^2f(w) ,需要 O(d2)O(d^2) 的内存。

综上,牛顿法的内存需求为 O(d2)O(d^2)

因此,从计算成本和内存需求上看,梯度下降法适合于维度较高的情况( dd 比较大),而牛顿法适用于维度较低的情况( dd 比较小)。因为牛顿法在维度较高时计算成本和内存需求都较高,但在低维度时可以更快收敛。

梯度下降原理

直观地说,只要学习率足够小并且梯度值不为零,它就会在每次迭代时减小目标值。最终,这应该导致梯度下降接近梯度为零的点。我们可以证明梯度下降在目标的二阶导数有界的假设下起作用。

假设我们要最小化一个目标函数 f(w)f(w),,并且假设这个函数的 Hessian 矩阵(也就是二阶导数矩阵)是有界的。这意味着对于某个常数 L>0L > 0 ,以下条件成立:

uT2f(x)uLu2|u^T \nabla^2 f(x) u| \leq L ||u||^2

其中, xx 是空间中任意的向量, uRbu \in \mathbb{R}^b。上式中, uT2f(x)u|u^T \nabla^2 f(x) u| 表示向量 uu 在 Hessian 矩阵 2f(x)\nabla ^2 f(x) 作用下的二次型,反映了函数 ffxx 点沿 uu 方向上的曲率。换句话说,它是 ffuu 方向上的二阶导数的加权和。 Lu2L ||u||^2 是一个界限。上式等价于:

2f(x)2L|| \nabla ^2 f(x) ||_2 \leq L

这里的 2f(x)2|| \nabla ^2 f(x) ||_2 表示的是 Hessian 矩阵 2f(x)\nabla^2 f(x) 的谱范数(也叫做矩阵的 2-范数或诱导范数,谱范数的定义是矩阵 2f(x)\nabla ^2 f(x) 的最大特征值的绝对值)。

特征值的求法

谱范数

二次型

在上述条件下,目标值随着梯度下降是如何变化的?根据泰勒定理,存在一个 ξt\xi_t 使得下面的式子成立:

f(wt+1)=f(wtαf(wt))=f(wt)αf(wt)Tf(wt)+12(αf(wt))T2f(ξt)(αf(wt))Tf(wt)αf(wt)2+α2L2f(wt)2=f(wt)α(1αL2)f(wt)2f(w_{t+1})=f(w_t - \alpha \nabla f(w_t))\\ =f(w_t) - \alpha \nabla f(w_t)^T \nabla f(w_t) + \frac{1}{2}(\alpha \nabla f(w_t))^T \nabla^2 f(\xi_t)(\alpha \nabla f(w_t))^T \\ \leq f(w_t) - \alpha ||\nabla f(w_t)||^2 + \frac{\alpha^2 L}{2} ||\nabla f(w_t)||^2 \\ = f(w_t) - \alpha (1 - \frac{\alpha L}{2})||\nabla f(w_t)||^2

  • 一阶项

首先,考虑函数 ffwtw_t 处的一阶泰勒展开。在 wtw_t 为一维向量的情况下,泰勒展开的形式为:

f(wt+1)f(wt)+f(wt)T(wt+1wt)f(w_{t+1}) \approx f(w_t) + \nabla f(w_t)^T (w_{t+1} - w_t)

这里 f(wt)\nabla f(w_t) 是在 wtw_t 处的梯度。由于 f(wt)\nabla f(w_t)wt+1wtw_{t+1}-w_t 同为列向量/行向量,为了保证内积计算的正确性,需要进行转置,结果为一个标量。

  • 二阶项

接下来考虑二阶泰勒展开项:

f(wt+1)f(wt)+f(wt)T(wt+1wt)+12(wt+1wt)T2f(ξt)(wt+1wt)f(w_{t+1}) \approx f(w_t) + \nabla f(w_t)^T (w_{t+1} - w_t) + \frac{1}{2} (w_{t+1} - w_t)^T \nabla^2 f(\xi_t) (w_{t+1} - w_t)

二阶项为 Hessian 矩阵 2f(ξt)\nabla^2f(\xi_t) ,它是一个对称矩阵,表示在某个点 ξt\xi_t 处的二阶导数。为了保证矩阵乘法的合法性,需要将 wt+1wtw_{t+1} - w_t 进行转置,最后得到一个标量。

  • 放缩

f(wt)Tf(wt)\nabla f(w_t)^T \nabla f(w_t) 为一个标量,等同于 f(wt)2||\nabla f(w_t)||^2 ,因此,利用上述有关于谱范数的不等式,放缩得到最终结果。

泰勒定理

如果取一个足够小的学习率 α\alpha ,使得 1αL1 \geq \alpha L,则原式 f(wt+1)f(wt)α(1αL2)f(wt)2f(w_{t+1}) \leq f(w_t) - \alpha (1 - \frac{\alpha L}{2})||\nabla f(w_t)||^2 变化为:

12αf(wt)2f(wt)f(wt+1)\frac{1}{2} \alpha || \nabla f(w_t) ||^2 \leq f(w_t) - f(w_{t+1})

这样就保证了每一次迭代后,目标值都在减少。现在,如果将 TT 轮迭代的梯度结果累加,则:

12αt=0T1f(wt)2t=0T1(f(wt)f(t+1))=f(w0)f(wT)f(w0)f\frac{1}{2} \alpha \sum_{t=0}^{T-1} ||\nabla f(w_t)||^2 \leq \sum_{t=0}^{T-1}(f(w_t) - f(_{t+1})) = f(w_0) - f(w_T) \leq f(w_0) - f^*

其中, ff^* 为损失函数 ff 的目标最小值,由此得到:

mint{0,,T}f(wt)21Tt=0T1f(wt)22(f(w0)f)αT\text{min}_{t \in \{0, \dots, T\}} ||\nabla f(w_t)||^2 \leq \frac{1}{T} \sum_{t=0}^{T-1} ||\nabla f(w_t)||^2 \leq \frac{2(f(w_0) - f^*)}{\alpha T}

上面不等式的左半部分显然成立,因为最小值不大于平均值。

在梯度下降过程中,最小梯度的大小随着迭代次数的增加而减小,且这种减小是与 1T\frac{1}{\sqrt{T}} 成正比的。这说明了梯度下降算法在逐渐逼近目标函数的最优值,即使有时函数值减少的速度会变慢,只要我们看的是最小梯度,这个过程就是收敛的。

1
2
Q:这个不等式是否确保梯度下降收敛到全局最优?
A:梯度下降算法通过沿着负梯度方向更新参数来最小化目标函数。这个过程可以确保找到一个局部最优解,但不一定能保证找到全局最优解。如果目标函数是非凸的,它可能存在多个局部最优解。梯度下降算法可能会收敛到其中一个局部最优解,而不是全局最优解。

凸函数

首先了解凸函数在数学上的定义,若一个函数 f:RdRf: \mathbb{R}^d \rightarrow \mathbb{R} ,对于所有的 x,yRdx, y \in \mathbb{R}^d ,以及所有 η[0,1]\eta \in [0,1],有:

f(ηx+(1η)y)ηf(x)+(1η)f(y)f(\eta x + (1-\eta)y) \leq \eta f(x) + (1 - \eta)f(y)

这意味着 ffxxyy 之间的值,不会超过在 xxyy 处的值按权重 η\eta1η1 - \eta 的线性组合。

从图形上看,这意味着如果我们在函数图中的任意两点之间画一条线段,该线段将位于函数上方。就梯度来说,对于所有 x,yRdx, y \in \mathbb{R}^d

(xy)T(f(x)f(y))0(x - y)^T (\nabla f(x) - \nabla f(y)) \geq 0

这意味着两个点之间的梯度差与这两个点之间的向量的内积不为负数。这也是凸函数的一个特性。

对于 Hessian 矩阵来说,对于所有 x,uRdx, u \in \mathbb{R}^d

uT2f(x)u0u^T \nabla ^2 f(x) u \geq 0

也就是说, Hessian 矩阵是半正定的。即对于任意非零向量 uuuT2f(x)uu^T \nabla ^2 f(x) u 始终不为负数。

实例:线性回归

  1. 线性模型: h(x)=wTx+bh(x) = w^T x + b

  2. 损失函数:均方误差MSE

    L(y,y^)=12(yy^)2L(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2

  3. 目标函数

    J(w,b)=12mi=1m(h(x(i))y(i))2J(w, b) = \frac{1}{2m} \sum_{i=1}^m (h(x^{(i)}) - y^{(i)})^2

    线性回归模型的目标函数为凸函数。

强凸函数

如果存在一个正的参数 μ>0\mu > 0 ,使得对于所有的 x,yRdx, y \in \mathbb{R} ^ d ,函数 ff 满足下式:

f(y)f(x)+f(x)T(yx)+μ2xy2f(y) \geq f(x) + \nabla f(x) ^T (y-x) + \frac{\mu}{2} || x-y || ^2

强凸性还可以通过函数的 Hessian\text{Hessian} 矩阵(即二阶导数矩阵)来定义。对于任意 x,uRdx, u \in \mathbb{R} ^d ,函数 ff 满足下式:

uT2f(x)uμu2u^T \nabla ^2 f(x) u \geq \mu ||u|| ^2

强凸性隐含了下式信息:

f(x)22μ(f(x)f)||\nabla f(x)|| ^2 \geq 2 \mu (f(x) - f ^ *)

这一性质也称 Polyak–Lojasiewicz\text{Polyak–Lojasiewicz} 条件,此外,还可以通过添加 l2\mathcal{l}_2 正则化将凸函数转变为强凸函数。

强凸函数的梯度下降

沿用上文的情形,我们得到下式:

f(wt+1)f(wt)12αf(wt)2f(w_{t+1}) \leq f(w_t) - \frac{1}{2} \alpha || \nabla f(w_t) ||^2

由于强凸性,我们应用 Polyak–Lojasiewicz\text{Polyak–Lojasiewicz} 条件可以得到:

f(wt+1)f(wt)αμ(f(wt)f)f(w_{t+1}) \leq f(w_t) - \alpha \mu (f(w_{t}) - f ^ *)

在不等式两端减去损失函数 ff 的目标最小值 ff ^ *

f(wt+1)ff(wt)αμf(wt)f+αμf=(1αμ)(f(wt)f)f(w_{t+1}) - f ^ * \leq f(w_t) - \alpha \mu f(w_{t}) - f ^ * + \alpha \mu f ^ * = (1-\alpha \mu)(f(w_t) - f^*)

上式递归地应用T步,得到:

f(wt+T)f(1αμ)T(f(wt)f)f(w_{t+T}) - f^* \leq (1-\alpha \mu)^T(f(w_t)-f^*)

递推过程:

f(wt+1)f(1αμ)(f(wt)f)f(wt+2)f(1αμ)(f(wt+1)f)(1αμ)2(f(wt)f)f(wt+T)f(1αμ)T(f(wt)f)f(w_{t+1}) - f ^ * \leq (1-\alpha \mu)(f(w_t) - f^*) \\ f(w_{t+2}) - f ^ * \leq (1-\alpha \mu)(f(w_{t+1}) - f^*) \leq (1-\alpha \mu)^2(f(w_t) - f^*) \\ \dots \\ f(w_{t+T}) - f^* \leq (1-\alpha \mu)^T(f(w_t)-f^*)

t=0t=0 时,有:

f(wT)f(1αμ)T(f(w0)f)f(w_{T}) - f^* \leq (1-\alpha \mu)^T(f(w_0)-f^*)

又:

(1αμ)Texp(αμT)(1 - \alpha \mu) ^T \leq \text{exp} (- \alpha \mu T)

得到:

f(wT)fexp(αμT)(f(w0)f)f(w_{T}) - f^* \leq \text{exp} (- \alpha \mu T) \cdot (f(w_0)-f^*)

因此,对于强凸函数,使用常数学习率的梯度下降算法能够以指数级的速度收敛到最优解。如果我们使用满足 1αL1 \geq \alpha L 的最大学习率(比如设定 α=1L\alpha = \frac{1}{L}),则有:

f(wT)fexp(μTL)(f(w0)f)f(w_{T}) - f^* \leq \text{exp} (- \frac{\mu T}{L}) \cdot (f(w_0)-f^*)

同样地,为了保证 f(wT)ff(w_T) - f^* (即在 T 步后目标函数值和最优值之间的差距)小于某个目标误差 $ \epsilon > 0$,我们需要设置足够大的 T:

TLμlog(f(w0)fϵ)T \geq \frac{L}{\mu} \cdot \text{log} (\frac{f(w_0)-f^*}{\epsilon})

确定优化算法需要进行多少步 T 以达到某个目标误差的主要因素是 κ=Lμ\kappa = \frac{L}{\mu} ,这个比例是由问题本身的性质决定的,而与初始条件或所需解决方案的精度无关。这个比例通常被称为条件数(condition number)。条件数隐含了一个强凸问题的难度。当条件数非常大时,问题可能非常难以解决,并且可能需要很多次梯度下降的迭代才能接近最优解。

1
2
3
4
Q:What affects the condition number? What can we do to make the condition number smaller?
A:
影响条件数的因素有梯度的 Lipschitz 常数 L ,如果函数的梯度变化非常剧烈,即梯度的 Lipschitz 常数很大,那么条件数会较高。这通常意味着函数在不同点的梯度变化幅度很大;还有强凸性参数 μ ,如果函数的强凸性参数较小,即函数的下界不够紧凑,那么条件数也会较高。这通常表示函数的曲率较低,优化过程可能较为困难。此外,在数据规模增大或者特征数量增加时,可能会导致 L 增加,从而导致条件数变大。复杂的模型(例如深度神经网络)也可能导致较高的 L。
可以通过特征工程、数据预处理、正则化等来减小条件数。