梯度下降（Gradient Descent）

本讲我们将介绍最基础，也是最经典的优化方法——梯度下降。在阐述梯度下降之前，我们首先给出两个比凸性更强的性质：

强凸性与光滑性

  • 首先定义强凸性：设μ≥0\mu\geq 0，f:Rn→Rf:\R^n\to\R为可微函数，若ff的定义域Ω\Omega为凸集，且对任意x⃗,y⃗∈Ω\vec{x},\vec{y}\in\Omega，有 f(y⃗)≥f(x⃗)+[∇f(x⃗)]⊤(y⃗−x⃗)+μ2∥y⃗−x⃗∥22.f(\vec{y}) \geq f(\vec{x}) + [\nabla f(\vec{x})]^\top (\vec{y} - \vec{x}) + \frac{\mu}{2} \|\vec{y} - \vec{x}\|_2^2. 那么称函数ff满足μ\mu-强凸性。（相应地，−f-f也满足μ\mu-强凹性）
    • 这在原有一阶凸性条件的基础上增加了一个二次型μ2∥y⃗−x⃗∥22=(y⃗−x⃗)⊤(μ2I)(y⃗−x⃗)\dfrac{\mu}{2} \|\vec{y} - \vec{x}\|_2^2=(\vec{y} - \vec{x})^\top\left(\dfrac{\mu}{2}I\right)(\vec{y} - \vec{x})。
    • 从几何角度上看，上述条件可以理解为函数必须位于过其任意一点，二次项系数为μ2\dfrac{\mu}{2}的抛物线之上。显然这比切线要求更加严格。
    • 与二阶凸性条件的关系：如果ff二阶可微，那么上述条件也可表述为对任意x⃗∈Ω\vec{x}\in\Omega， ∇2f(x⃗)−μI⪰0\nabla^2 f(\vec{x})-\mu I\succeq 0 即∇2f(x⃗)−μI\nabla^2 f(\vec{x})-\mu I为半正定矩阵。
    • 实际上，满足μ\mu-强凸性的函数也满足严格凸性，从而有且仅有一个全局最小值。
  • 然后定义光滑性：设L≥0L\geq 0，Ω⊆Rn\Omega\subseteq\R^n为一集合，f:Ω→Rf:\Omega\to\R为一可微函数。那么如果对任意x⃗,y⃗∈Ω\vec{x},\vec{y}\in\Omega，有 f(y⃗)≤f(x⃗)+[∇f(x⃗)]⊤(y⃗−x⃗)+L2∥y⃗−x⃗∥22.f(\vec{y}) \leq f(\vec{x}) + [\nabla f(\vec{x})]^\top (\vec{y} - \vec{x}) + \frac{L}{2} \|\vec{y} - \vec{x}\|_2^2. 那么称函数ff满足LL-光滑性。
    • 与μ\mu-强凸性类似，这一条件也可以理解为函数必须位于过其任意一点，二次项系数为L2\dfrac{L}{2}的抛物线之下。
    • 实际上，对于凸函数而言，LL-光滑性与LL-利普希茨连续性是等价的。【证明略】
  • 上述两个性质相当于对函数的曲率（Hessian矩阵）做了约束，这对后续的梯度下降会有很大作用。

梯度下降法

  • 梯度下降本质是一种迭代方法。具体而言，设f:Rn→Rf:\R^n\to\R为可微函数，对于最优化问题 min⁡x⃗∈Rnf(x⃗)\min_{\vec{x}\in\R^n}f(\vec{x}) 梯度下降的想法是先设定一个初值x⃗0∈Rn\vec{x}_0\in\R^n，再通过迭代产生序列x⃗1,x⃗2,⋯\vec{x}_1,\vec{x}_2,\cdots，迭代公式为 x⃗t+1=x⃗t+ηv⃗t\vec{x}_{t+1}=\vec{x}_t+\eta\vec{v}_t 其中：
    • v⃗t\vec{v}_t为搜索方向，一般会指向更优的解；【在梯度下降法中与梯度∇f(x⃗)\nabla f(\vec{x})有关】
    • η\eta为步长，表示在搜索方向上的移动量。【一般视作超参数，需要根据具体问题调试】
  • 那么如何具体确定搜索方向呢？我们希望迭代后的解比原来的解更优，即f(x⃗t+ηv⃗t)≤f(x⃗t)f(\vec{x}_t+\eta\vec{v}_t)\leq f(\vec{x}_t)。
    • 特别地，我们希望目标函数下降的速度最快，而目标函数下降的速度由方向导数Df(x⃗)[v⃗]=v⃗⊤∇f(x⃗)Df(\vec{x})[\vec{v}]=\vec{v}^\top\nabla f(\vec{x})决定。由微积分的知识可知，当v⃗\vec{v}方向与梯度方向相反时，函数下降的速度最快，即 −∇f(x⃗)∥∇f(x⃗)∥2∈arg min⁡v⃗∈Rn∥v⃗∥2=1Df(x⃗)[v⃗].-\frac{\nabla f(\vec{x})}{\|\nabla f(\vec{x})\|_2} \in \argmin_{\substack{\vec{v} \in \mathbb{R}^n\\\|\vec{v}\|_2=1}} Df(\vec{x})[\vec{v}].
    • 另一方面，我们也希望利用目标函数的梯度范数信息（一般梯度越大，离最优解就越远）。因此，我们最终选择v⃗t=−∇f(x⃗t)\vec{v}_t=-\nabla f(\vec{x}_t)。
  • 由此我们便得到著名的梯度下降表达式： x⃗t+1=x⃗t−η∇f(x⃗t),t=0,1,2,⋯\vec{x}_{t+1}=\vec{x}_t-\eta\nabla f(\vec{x}_t),\quad t=0,1,2,\cdots 一般会经过指定迭代次数TT后停止。
  • 然而，如果步长η\eta固定，还是不能保证迭代后的解一定比原始解更优。实际上，我们只能说对于任意tt，存在ηt>0\eta_t>0使得 f(x⃗t−ηt∇f(x⃗t))≤f(x⃗t)f(\vec{x}_t-\eta_t\nabla f(\vec{x}_t))\leq f(\vec{x}_t) 这个ηt\eta_t与ff在x⃗t\vec{x}_t附近的形状（如曲率）有关。当然，在下述讨论中，我们只考虑固定步长以简化推导。

收敛性分析

  • 下面我们会说明，对于特定类型的函数f:Rn→Rf:\R^n\to\R与特定的步长η>0\eta>0，梯度下降法可以保证迭代收敛到最优解。
  • 首先以最小二乘问题作为例子：设A∈Rm×nA\in\R^{m\times n}列满秩，y⃗∈Rm\vec{y}\in\R^m，之前我们已经知道 min⁡x⃗∈Rn∥Ax⃗−y⃗∥22\min_{\vec{x}\in\R^n}\|A\vec{x}-\vec{y}\|_2^2 存在最优解 x⃗∗=(A⊤A)−1A⊤y⃗\vec{x}^*=(A^\top A)^{-1}A^\top\vec{y} 下面我们分析梯度下降法能否收敛到这个解。设初值x⃗0∈Rn\vec{x}_0\in\R^n，由于函数梯度 ∇f(x⃗)=2A⊤(Ax⃗−y⃗)\nabla f(\vec{x})=2A^\top(A\vec{x}-\vec{y}) 因此迭代表达式为 x⃗t+1=x⃗t−2ηA⊤(Ax⃗t−y⃗)=(I−2ηA⊤A)x⃗t+2ηA⊤y⃗\vec{x}_{t+1}=\vec{x}_t-2\eta A^\top(A\vec{x}_t-\vec{y})=(I-2\eta A^\top A)\vec{x}_t+2\eta A^\top\vec{y} 下面我们证明存在η>0\eta>0使得∥x⃗t+1−x⃗∗∥≤∥x⃗t−x⃗∗∥\|\vec{x}_{t+1}-\vec{x}^*\|\leq\|\vec{x}_{t}-\vec{x}^*\|且lim⁡t→∞∥x⃗t−x⃗∗∥=0\displaystyle\lim_{t\to\infty}\|\vec{x}_{t}-\vec{x}^*\|=0： x⃗t+1−x⃗∗=(I−2ηA⊤A)x⃗t+2ηA⊤y⃗−x⃗∗=(I−2ηA⊤A)x⃗t+2ηA⊤y⃗−(A⊤A)−1A⊤y⃗=(I−2ηA⊤A)x⃗t+2η(A⊤A)(A⊤A)−1A⊤y⃗−(A⊤A)−1A⊤y⃗=(I−2ηA⊤A)x⃗t−(I−2ηA⊤A)x⃗∗=(I−2ηA⊤A)(x⃗t−x⃗∗).\begin{align*} \vec{x}_{t+1} - \vec{x}^* &= (I - 2\eta A^\top A)\vec{x}_t + 2\eta A^\top \vec{y} - \vec{x}^* \\ &= (I - 2\eta A^\top A)\vec{x}_t + 2\eta A^\top \vec{y} - (A^\top A)^{-1} A^\top \vec{y} \\ &= (I - 2\eta A^\top A)\vec{x}_t + 2\eta (A^\top A)(A^\top A)^{-1} A^\top \vec{y} - (A^\top A)^{-1} A^\top \vec{y} \\ &= (I - 2\eta A^\top A)\vec{x}_t - (I - 2\eta A^\top A)\vec{x}^* \\ &= (I - 2\eta A^\top A)(\vec{x}_t - \vec{x}^*). \end{align*} 于是 ∥x⃗t+1−x⃗∗∥22=∥(I−2ηA⊤A)(x⃗t−x⃗∗)∥22=∥I−2ηA⊤A∥22⋅∥x⃗t−x⃗∗∥22=σmax⁡{I−2ηA⊤A}⋅∥x⃗t−x⃗∗∥22\begin{aligned} \|\vec{x}_{t+1} - \vec{x}^*\|_2^2&=\|(I - 2\eta A^\top A)(\vec{x}_t - \vec{x}^*)\|_2^2\\ &=\|I - 2\eta A^\top A\|_2^2\cdot\|\vec{x}_t - \vec{x}^*\|_2^2\\ &=\sigma_{\max}\{I - 2\eta A^\top A\}\cdot\|\vec{x}_t - \vec{x}^*\|_2^2 \end{aligned} 因此只要σmax⁡{I−2ηA⊤A}<1\sigma_{\max}\{I - 2\eta A^\top A\}< 1，那么上述结论就成立了。
  • 接下来我们基于这个例子对满足收敛性的函数类进行推广。这里我们主要考虑同时满足μ\mu-强凸性与LL-光滑性的函数。在对它们的收敛性进行推导之前，我们首先给出LL-光滑函数的一个性质：
    • 设f:Rn→Rf:\R^n\to\R为一LL-光滑函数，那么对任意x⃗∈Rn\vec{x}\in\R^n，有 ∥∇f(x⃗)∥22≤2L(f(x⃗)−min⁡x⃗′∈Rnf(x⃗′)).\|\nabla f(\vec{x})\|_2^2 \leq 2L \left( f(\vec{x}) - \min_{\vec{x}' \in \mathbb{R}^n} f(\vec{x}') \right). 即当x⃗\vec{x}离最优解最近，那么它对应的梯度就越小。简单证明如下：
      • 在上述LL-光滑性条件中令y⃗=x⃗−∇f(x⃗)L\vec{y}=\vec{x}-\dfrac{\nabla f(\vec{x})}{L}，可得 f(x⃗−∇f(x⃗)L)≤f(x⃗)+[∇f(x⃗)]⊤(−∇f(x⃗)L)+L2∥−∇f(x⃗)L∥22=f(x⃗)−1L∥∇f(x⃗)∥22+12L∥∇f(x⃗)∥22=f(x⃗)−12L∥∇f(x⃗)∥22.\begin{aligned} f\left(\vec{x} - \frac{\nabla f(\vec{x})}{L}\right) &\leq f(\vec{x}) + [\nabla f(\vec{x})]^\top \left( -\frac{\nabla f(\vec{x})}{L} \right) + \frac{L}{2} \left\| -\frac{\nabla f(\vec{x})}{L} \right\|_2^2 \\ &= f(\vec{x}) - \frac{1}{L} \|\nabla f(\vec{x})\|_2^2 + \frac{1}{2L} \|\nabla f(\vec{x})\|_2^2 \\ &= f(\vec{x}) - \frac{1}{2L} \|\nabla f(\vec{x})\|_2^2. \end{aligned} 因此 min⁡x⃗′∈Rnf(x⃗′)≤f(x⃗−∇f(x⃗)L)≤f(x⃗)−12L∥∇f(x⃗)∥22\min_{\vec{x}' \in \mathbb{R}^n} f(\vec{x}')\leq f\left(\vec{x} - \frac{\nabla f(\vec{x})}{L}\right)\leq f(\vec{x}) - \frac{1}{2L} \|\nabla f(\vec{x})\|_2^2 经过整理后即得结论。

      实际上，上述推导中(x⃗−∇f(x⃗)L,f(x⃗)−12L∥∇f(x⃗)∥22)\left(\vec{x}-\dfrac{\nabla f(\vec{x})}{L},f(\vec{x}) - \dfrac{1}{2L} \|\nabla f(\vec{x})\|_2^2\right)这一点恰好就是过(x⃗,f(x⃗))(\vec{x},f(\vec{x}))的上包络抛物线最低点。

  • 现在我们就能正式给出函数梯度下降收敛性的结论了：设μ,L>0\mu,L>0，f:Rn→Rf:\R^n\to\R同时满足μ\mu-强凸性与LL-光滑性。若下述优化问题 min⁡x⃗∈Rnf(x⃗)\min_{\vec{x}\in\R^n}f(\vec{x}) 存在最优解x⃗∗\vec{x}^*，那么令步长η=1L\eta=\dfrac{1}{L}，下述梯度下降迭代过程 x⃗t+1=x⃗t−η∇f(x⃗t)\vec{x}_{t+1}=\vec{x}_t-\eta\nabla f(\vec{x}_t) 对任意初值x⃗0\vec{x}_0，任意t∈Nt\in\N都有 ∥x⃗t+1−x⃗∗∥22≤(1−μL)∥x⃗t−x⃗∗∥22.\|\vec{x}_{t+1} - \vec{x}^*\|_2^2 \leq \left(1 - \frac{\mu}{L}\right)\|\vec{x}_t - \vec{x}^*\|_2^2. 证明留给读者（利用上述LL-光滑性性质和μ\mu-强凸性性质即可）。要证明lim⁡t→∞∥x⃗t−x⃗∗∥=0\displaystyle\lim_{t\to\infty}\|\vec{x}_{t}-\vec{x}^*\|=0，只需要0<μL≤10< \dfrac{\mu}{L}\leq 1即可。这是显然的，因为由光滑性与强凸性条件， f(x⃗)+[∇f(x⃗)]⊤(y⃗−x⃗)+μ2∥y⃗−x⃗∥22≤f(y⃗)≤f(x⃗)+[∇f(x⃗)]⊤(y⃗−x⃗)+L2∥y⃗−x⃗∥22⟹μ2∥y⃗−x⃗∥22≤L2∥y⃗−x⃗∥22⟹μ≤L\begin{aligned} &f(\vec{x}) + [\nabla f(\vec{x})]^\top (\vec{y} - \vec{x}) + \frac{\mu}{2} \|\vec{y} - \vec{x}\|_2^2\leq f(\vec{y})\leq f(\vec{x}) + [\nabla f(\vec{x})]^\top (\vec{y} - \vec{x}) + \frac{L}{2} \|\vec{y} - \vec{x}\|_2^2\\ \Longrightarrow & \frac{\mu}{2} \|\vec{y} - \vec{x}\|_2^2\leq\frac{L}{2}\|\vec{y} - \vec{x}\|_2^2\Longrightarrow \mu\leq L \end{aligned}
    • 由上述推导可见，μL\dfrac{\mu}{L}决定了梯度下降的收敛速度：其值越大，收敛速度就越快。

      极端情况下（μ=L\mu=L，此时ff为标准抛物面），从任意位置出发只需要一次迭代即可达到最优解。

  • 当然，梯度下降的收敛性并不只局限于强凸光滑函数。对于一般的光滑凸函数，使用合适的步长，经过足够多的迭代次数后也能达到收敛，只是整体速度会更慢一些。
    • 从定量角度，如果需要的收敛误差为ϵ\epsilon，那么梯度下降收敛所需迭代次数级别大致在O(1ϵ)O\left(\dfrac{1}{\epsilon}\right)。

随机梯度下降（SGD）

  • 在现实情形中，梯度的计算往往会比较复杂。比如下述优化问题 min⁡x⃗∈Rnf(x⃗)=min⁡x⃗∈Rn1m∑i=1mfi(x⃗)\min_{\vec{x}\in\R^n}f(\vec{x})=\min_{\vec{x}\in\R^n}\frac{1}{m}\sum_{i=1}^mf_i(\vec{x}) 其梯度∇f(x⃗)=1m∑i=1m∇fi(x⃗)\displaystyle\nabla f(\vec{x})=\frac{1}{m}\sum_{i=1}^m\nabla f_i(\vec{x})，当mm较大，∇fi(x⃗)\nabla f_i(\vec{x})较复杂时计算效率较低。
  • 对此，随机梯度下降的策略是：在{f1,⋯ ,fm}\{f_1,\cdots,f_m\}中随机抽取一个子函数fif_i作为替代计算其梯度，得到表达式 x⃗t+1=x⃗t−η∇fi(x⃗t)\vec{x}_{t+1}=\vec{x}_t-\eta\nabla f_i(\vec{x}_t) 当每个子函数的抽取概率都相等时，其得到的梯度期望恰好与原始函数梯度相等 E[fi(x⃗t)]=1m∑i=1mfi(x⃗t)=f(x⃗t).\mathbb{E}[f_i(\vec{x}_t)]=\frac{1}{m}\sum_{i=1}^mf_i(\vec{x}_t)=f(\vec{x}_t).
  • 那么如何保证SGD同样能收敛呢？这里我们不能直接套用上面的证明方法（−∇fi(x⃗t)-\nabla f_i(\vec{x}_t)方向甚至可能使目标函数增大）。实际上，对于随机梯度下降，我们取迭代函数序列的均值可以得到 lim⁡T→∞f(1T∑t=1Tx⃗t)=min⁡x⃗∈Rnf(x⃗)\lim_{T \to \infty} f\left(\frac{1}{T} \sum_{t=1}^{T} \vec{x}_t\right) = \min_{\vec{x} \in \mathbb{R}^n} f(\vec{x}) 另一方面，为保证SGD收敛，我们还需要将步长随迭代次数增加逐渐趋向00。
  • 对于一般情形的SGD收敛性证明比较复杂，但如果加上一些约束条件，证明的复杂性会降低一些。【具体略，可参见知乎文章】
  • 在机器学习中，随机梯度下降一般会自然融入于在线学习（即数据点逐个依次到达），当新数据到达时自动进行优化。【注意每次迭代时都要除以样本数量进行归一化】

    而在神经网络中，往往会使用小批量数据（即Mini-batch）计算梯度，相比单样本SGD可以有效降低方差/噪声影响。

带约束的梯度下降

  • 在上述梯度下降算法中，我们没有对目标函数施加约束。对于带约束的优化问题，如 min⁡x⃗∈Ωf(x⃗),Ω为凸集\min_{\vec{x}\in\Omega}f(\vec{x}),\quad \Omega\text{为凸集} 直接套用上述梯度下降算法可能导致最终解不在Ω\Omega中。
  • 为解决这一问题，我们可以使用下述两种梯度下降的变体：
    1. 投影梯度下降法（PGD）
      PGD的想法很简单：对于Ω\Omega之外的解，将其映射到Ω\Omega中。具体而言，对任意y⃗∈Rn\vec{y}\in\R^n，定义 projΩ(y⃗)=arg min⁡x⃗∈Ω∥x⃗−y⃗∥22\text{proj}_{\Omega}(\vec{y})=\argmin_{\vec{x}\in\Omega}\|\vec{x}-\vec{y}\|_2^2 这里假设Ω\Omega为闭凸集，这样能保证projΩ(y⃗)\text{proj}_{\Omega}(\vec{y})一定存在。然后梯度下降表达式就可以写为 x⃗t+1=projΩ(x⃗t−η∇fi(x⃗t)).\vec{x}_{t+1}=\text{proj}_{\Omega}(\vec{x}_t-\eta\nabla f_i(\vec{x}_t)). 注意PGD中投影函数本身也是一个凸优化问题，只有当这一问题相比原始问题足够简单时PGD算法才可行。
    2. 条件梯度下降法（CGD）
      条件梯度下降法（也称为Frank-Wolfe算法）给出了另一种解决策略：在计算搜索方向v⃗t\vec{v}_t时加入可行域Ω\Omega约束，即 v⃗t=arg min⁡v⃗∈Ω[∇f(x⃗t)]⊤v⃗\vec{v}_t=\argmin_{\vec{v}\in\Omega}[\nabla f(\vec{x}_t)]^\top\vec{v} 同时，为保证迭代后x⃗t+1\vec{x}_{t+1}不会飞到Ω\Omega之外，将更新公式改为凸组合 x⃗t+1=(1−δt)x⃗t+δtv⃗t\vec{x}_{t+1}=(1-\delta_t)\vec{x}_t+\delta_t\vec{v}_t 其中δt∈[0,1]\delta_t\in[0,1]且lim⁡t→∞δt=0\displaystyle\lim_{t\to\infty}\delta_t=0。【一个保守的取值是δt=1t\delta_t=\dfrac{1}{t}】
      当然，这里v⃗t\vec{v}_t的计算同样也是Ω\Omega内的凸优化问题，因此要求同上。

    上述两种方法对于解决一般的带约束优化问题仍然比较麻烦，下一讲我们将进一步阐述如何处理带约束的优化问题。