Gradient descent method

发表于 更新于 分类于

梯度下降法

梯度下降法是一种用于优化函数的优化算法，它通过迭代地更新参数以找到函数的最小值。

算法介绍

对于光滑的函数f(x)f(\boldsymbol{x}), 在给定起始点xk\boldsymbol{x}^k处，我们需要选择一个下降方向dk\boldsymbol{d}^k。 由此可以得到新的迭代点xk+1=xk+αdk\boldsymbol{x}^{k+1} = \boldsymbol{x}^k + \alpha \boldsymbol{d}^k，其中α\alpha为步长。最自然的想法是选取函数下降最快的方向作为dk\boldsymbol{d}^k。那么，函数下降最快的方向是什么方向呢？
由函数的泰勒展开式可以得到：

f(xk+αdk)=f(xk)+α∇f(xk)⊤dk+O(α2∥dk∥2)f(\boldsymbol{x}^k + \alpha \boldsymbol{d}^k) = f(\boldsymbol{x}^k) + \alpha\nabla f(\boldsymbol{x}^k)^\top \boldsymbol{d}^k + \mathcal{O}(\alpha^2\|\boldsymbol{d}^k\|^2)

因此，dk\boldsymbol{d}^k应该使得∇f(xk)⊤dk\nabla f(\boldsymbol{x}^k)^\top \boldsymbol{d}^k尽可能小，所以dk\boldsymbol{d}^k应该取梯度的反方向作为最快的下降方向， 即dk=−∇f(xk)\boldsymbol{d}^k = -\nabla f(\boldsymbol{x}^k). 因此，梯度下降算法的迭代公式为：

xk+1=xk−α∇f(xk)\boldsymbol{x}^{k+1} = \boldsymbol{x}^k - \alpha \nabla f(\boldsymbol{x}^k)

其中步长α\alpha可以是固定步长也可以是动态步长。

应用举例-LASSO问题求解

本节将介绍如何使用梯度下降法求解LASSO问题。LASSO问题是线性回归问题加上L1范数正则化项，即：

min⁡f(x)=12∥Ax−b∥2+μ∥x∥1\min f(\boldsymbol{x}) = \frac{1}{2}\|A\boldsymbol{x}- b\|^2 + \mu\|\boldsymbol{x}\|_1

注意LASSO问题并不是一个光滑的问题，在某些点上其导数可能不存在，因此不能直接使用梯度法求解。考虑到非光滑项为L1范数，如果能找到一个光滑的函数来近似L1范数，就可以通过梯度下降法求解。实际上，我们可以考虑下面的一维光滑函数：

lδ(x)={12δx2,∣x∣<δ,∣x∣−δ2,其他.l_{\delta}(x)=\begin{cases}\frac{1}{2\delta}x^{2},&|x|<\delta,\\|x|-\frac{\delta}{2},&\text{其他}.&&&\end{cases}

当δ→0\delta\rightarrow0时，光滑函数lδ(x)l_{\delta}(x)会和绝对值函数∣x∣|x|越来越相似。因此，我们构造光滑化的LASSO函数为：

min⁡f(x)=12∥Ax−b∥2+μLδ(x),\min f(\boldsymbol{x}) = \frac{1}{2}\|A\boldsymbol{x}- b\|^2 + \mu L_{\delta}(x),

其中μ\mu是正则化参数，δ\delta是光滑化参数。Lδ(x)=∑inlδ(xi)L_{\delta}(x)=\sum_i^nl_\delta(x_i)。
计算出光滑化的LASSO函数的梯度为：

∇fδ(x)=AT(Ax−b)+μ∇Lδ(x),\nabla f_\delta(x)=A^\mathrm{T}(Ax-b)+\mu\nabla L_\delta(x),

其中∇Lδ(x)\nabla L_\delta(x)是针对逐个变量定义的：

(∇Lδ(x))i={sign(xi),∣xi∣>δ,xiδ,∣xi∣⩽δ.(\nabla L_{\delta}(x))_{i}=\begin{cases}\mathrm{sign}(x_{i}),&|x_{i}|>\delta,\\\frac{x_{i}}{\delta},&|x_{i}|\leqslant\delta.&&&\end{cases}