梯度下降算法｜在写作的Yitso

一、什么是梯度下降？

假设我们在一座山上，如果不考虑其他条件，怎么走可以最快下山（即下山走的路最少）？

肯定是选择坡度最陡峭的。

梯度下降的目标也就是基于这样的思想，梯度就是我们当前所在位置的坡度（导数）。若把它表示为一个向量么，记为$\nabla f(\mathbf{x})$，它所指向的就是最陡上坡方向。

所以当我们在某一个位置的时候，只要每一步我们都沿着函数变化最陡的方向往下（即反梯度）走，最终我们会很快地找到一个平缓地带，也就是这个函数的一个极小值点。

为了便于理解，这里举两个具体的例子：

例 1. 单变量函数的梯度

如果山的高度和我们所在位置的函数表达是 $ f(x) = x^2 $，因为是单变量，所以我们只能选择往右（增加$ x $）走还是往左走（减小$ x $）。

在 $ x=2 $ 处，导数 $ f'(x)=2x=4 $，此时意味着如果往右走（增加 $x$ ），那么我们所在位置会变高（函数值$ f(x) $ 增大），所以算法上需要往左走（减小$ x $）减小函数值。

例 2. 多变量函数的梯度

如果山的高度和我们所在位置的函数表达函数 $ f(x,y) = x^2 + y^2 $。

在点$ (1,1)$ 处，梯度 $ -\nabla f(x,y)=(\partial f/\partial x, \partial f/\partial y) = (2x, 2y) = (2,2) $

那么负梯度方向$ (-2,-2) $就是下山最快的方向。

二、算法目标

从上面的例子可以得到，梯度下降算法是一种迭代优化方法，用于寻找可微函数的局部极小值点。其核心思想是沿目标函数的负梯度方向逐步调整参数，从而逐步逼近极小值点。

用数学语言描述的话，即给定目标函数 $ f: \mathbb{R}^n \to \mathbb{R} $，梯度下降的目标是找到参数向量 $ \mathbf{x}^* \in \mathbb{R}^n $，使得： $$ \mathbf{x}^* = \arg\min_{\mathbf{x}} f(\mathbf{x}). $$

三、算法步骤

梯度下降实现的方式，是通过每一次迭代来减小函数值以此逼近极小值点。

即对于第 $k$ 次迭代，对当前点 $ \mathbf{x}_k $，则需要找到 $ \mathbf{x}_{k+1} $ 使得 $ f(\mathbf{x^*}_{k+1}) < f(\mathbf{x}_k) $。

那么问题就转换为了如何选择 $ \Delta \mathbf{x} = \mathbf{x}_{k+1} - \mathbf{x}_k $ ，尽可能使得$ k+1 $次迭代更接近极小值？

3.1 迭代过程

这个问题实际上需要被拆解成两个问题：

确定方向，应该往哪个方向走？直观感受即是负梯度方向。
确定步长，应该走多远？走远了，可能会走过头，走近了，就会走得太慢了（迭代次数多）。

3.1.1 确定方向

从前文我们可以直观的感受到，负梯度的方向即是最优方向，即 $$ \mathbf{d} = -\frac{\nabla f(\mathbf{x}_k)}{\|\nabla f(\mathbf{x}_k)\|} $$ 其中 $\mathbf{d} \in \mathbb{R}^n$ 为单位位方向向量（即 $\|\mathbf{d}\| = 1$）。

下面给出证明：

我们用方向导数描述函数在某一点沿着特定方向的变化率，其定义如下为 $$ D_{\mathbf{v}} f(\mathbf{x}) = \nabla f(\mathbf{x}) \cdot \mathbf{d}, $$ 方向导数衡量的是函数在该方向的瞬时变化趋势，若我们需要找到函数下降最快的方向，则需要找到找到一个$\mathbf{d^*}$，使得方向导数最小。

根据柯西-施瓦茨不等式，对任意向量 $\mathbf{a}, \mathbf{b} \in \mathbb{R}^n$，有： $$ |\mathbf{a}\cdot \mathbf{b}| \leq \|\mathbf{a}\| \cdot \|\mathbf{b}\|, $$ 当且仅当 $\mathbf{a}$ 与 $\mathbf{b}$ 线性相关时取等。

令 $\mathbf{a} = \nabla f(\mathbf{x})$，$\mathbf{b} = \mathbf{d}$，方向导数的下限为： $$ \nabla f(\mathbf{x}) \cdot \mathbf{d} \geq -\|\nabla f(\mathbf{x})\|. $$

且当 $ \mathbf{d} $ 与梯度反向时，方向导数最小，即 $$ \mathbf{d^*} = -\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|} $$

3.1.2 确定步长

我们已经确定了方向，第二步则是需要确定走多远。

首先我们考虑固定步长，即 $$ \Delta \mathbf{x} = -\eta \frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|} $$ 步长恒为 $ \eta $，与梯度模长无关。这会带来两个核心问题：

陡峭区域步长不足，在陡峭区域，梯度非常大，比如 $ \|\nabla f(\mathbf{x})\| = 100 $，此时应该大步走，若以固定步长走，则需要走更多步。
平缓区域步长过大，当 $\mathbf{x}_k $ 在接近 $ f(\mathbf{x}_k)$ 小值附近时，即此时 $ \|\nabla f(\mathbf{x})\| \approx 0 $，迭代可能反复跨过最小值，导致震荡

所以，我们可以看到，步长应当与梯度的模 $ \|\nabla f(\mathbf{x})\| $ 正相关时，可以保持最优的下降效率。

那么最终我们可以得到如下的迭代方式 $$ \Delta x = -\eta \frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\|\nabla f(\mathbf{x})\| = -\eta \cdot \nabla f(\mathbf{x}) $$ 其中 $ \eta $ 为常数，被称为学习率，学习率太小会导致收敛慢，太大可能会震荡甚至发散。

学习率的取值一般由目标函数的性质决定，本节主要关心算法步骤，这里暂时不展开，将在后续收敛性分析章节中详细阐述。

3.2 算法步骤描述

我们已经得出了迭代的方式，那么至此我们就已经可以完整的描述整个梯度下降算法了。

梯度下降算法的步骤如下：

初始化：选择初始点 $ \mathbf{x}_0 $、学习率 $ \eta > 0 $、收敛阈值 $ \epsilon > 0 $，最大迭代次数 $ K > 0 $，设置初始迭代次数 $ k = 0 $，。
迭代更新： - 计算当前梯度：$ \mathbf{g}_k = \nabla f(\mathbf{x}_k) $. - 更新参数：$ \mathbf{x}_{k+1} = \mathbf{x}_k - \eta \mathbf{g}_k $. - 检查停止条件（如 $ \|\mathbf{g}_k\| < \epsilon $ 或达到最大迭代次数）。若满足条件，停止迭代；否则，令 $ k = k + 1 $，重复步骤。

3.3 算法计算示例：$ f(x, y) = x^2 + y^2 $

目标：找到极小值点 $ (x^*, y^*) $。

梯度计算： $$ \nabla f(x, y) = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right) = (2x, 2y). $$
参数更新规则： $$ x_{k+1} = x_k - 2\eta x_k = x_k (1 - 2\eta), $$

$$ y_{k+1} = y_k - 2\eta y_k = y_k (1 - 2\eta). $$

初始点：$(x_0, y_0) = (-1, 2)$，学习率 $\eta = 0.25$，最大迭代次数 $K = 20$，收敛阈值 $ \epsilon = 10^{-6} $，
具体计算代码：

# 定义初始参数
x = -1.0
y = 2.0
eta = 0.25
max_iterations = 10  
epsilon = 1e-6    

for i in range(max_iterations):
    # 计算梯度
    grad_x = 2 * x
    grad_y = 2 * y

    # 更新参数
    x_new = x - eta * grad_x
    y_new = y - eta * grad_y

    # 打印迭代结果
    print("Iteration {}:".format(i+1))
    print("  Gradient: ({:.4f}, {:.4f})".format(grad_x, grad_y))
    print("  New Point: ({:.4f}, {:.4f})\n".format(x_new, y_new))

    # 检查收敛条件（参数变化极小则停止）
    if abs(x_new - x) < epsilon and abs(y_new - y) < epsilon:
        print("Converged!")
        break

    # 更新参数
    x, y = x_new, y_new

从运行后可得最终输出结果为 $ (-0.001, 0.002) $。接近实际最小值点$(0,0)$。

四、收敛性分析

梯度下降算法的收敛性分析依赖于目标函数的性质和算法参数的设置。以下为详细分析步骤：

4.1 基本假设条件

在进行收敛性分析前，通常需要目标函数满足以下条件之一或组合：

Lipschitz连续梯度：存在常数 $ L > 0 $，使得对所有 $ \mathbf{x}, \mathbf{y} \in \mathbb{R}^n $，有： $$ \|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \leq L \|\mathbf{x} - \mathbf{y}\| $$
强凸性：存在常数 $ \mu > 0 $，使得对所有 $ \mathbf{x}, \mathbf{y} \in \mathbb{R}^n $，有： $$ f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x}) \cdot (\mathbf{y} - \mathbf{x}) + \frac{\mu}{2} \|\mathbf{y} - \mathbf{x}\|^2 $$
一般凸性：满足凸函数定义，即对任意 $ \mathbf{x}, \mathbf{y} $ 和 $ \theta \in [0,1] $，有： $$ f(\theta \mathbf{x} + (1-\theta)\mathbf{y}) \leq \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}) $$

4.2 学习率选择

学习率 $ \eta $ 需满足稳定性条件：

对于Lipschitz连续梯度函数：选择 $ \eta \leq \frac{1}{L} $，避免步长过大导致发散。
对于强凸函数：结合 $ \mu $ 和 $ L $，选择 $ \eta \in \left(0, \frac{2}{\mu + L}\right) $。

4.3 收敛速率分析

根据函数性质的不同，梯度下降的收敛速率分为以下几种类型：

情形1：强凸且光滑函数

假设：目标函数是 $ \mu $-强凸且梯度 $ L $-Lipschitz连续。
收敛速率：线性收敛（几何收敛），即： $$ f(\mathbf{x}_k) - f(\mathbf{x}^*) \leq \left(1 - \frac{2\eta \mu L}{\mu + L}\right)^k \left(f(\mathbf{x}_0) - f(\mathbf{x}^*)\right). $$
最优学习率：当 $ \eta = \frac{2}{\mu + L} $，收敛速率最快。

情形2：一般凸且光滑函数

假设：目标函数是凸且梯度 $ L $-Lipschitz连续。
收敛速率：次线性收敛，即： $$ f(\mathbf{x}_k) - f(\mathbf{x}^*) \leq \frac{L \|\mathbf{x}_0 - \mathbf{x}^*\|^2}{2k}. $$
学习率选择：固定学习率 $ \eta = \frac{1}{L} $。

情形3：非凸但光滑函数

假设：目标函数梯度 $ L $ - Lipschitz连续，但不一定凸。
收敛结果：梯度范数以 $ O\left(\frac{1}{\sqrt{k}}\right) $ 速率趋近于零，即： $$ \min_{0 \leq i \leq k} \|\nabla f(\mathbf{x}_i)\|^2 \leq \frac{2L(f(\mathbf{x}_0) - f(\mathbf{x}^*))}{k+1}. $$
意义：算法最终会收敛到一个梯度为零的稳定点（可能是局部极小值或鞍点）。

4.4 收敛性证明

以强凸且光滑函数为例，简要展示收敛性证明步骤：

利用泰勒展开与强凸性： $$ f(\mathbf{x}_{k+1}) \leq f(\mathbf{x}_k) - \eta \|\nabla f(\mathbf{x}_k)\|^2 + \frac{L \eta^2}{2} \|\nabla f(\mathbf{x}_k)\|^2. $$
结合强凸性条件： $$ \|\nabla f(\mathbf{x}_k)\|^2 \geq 2\mu \left(f(\mathbf{x}_k) - f(\mathbf{x}^*)\right). $$
递推不等式： $$ f(\mathbf{x}_{k+1}) - f(\mathbf{x}^*) \leq \left(1 - 2\mu \eta + L \eta^2 \mu \right) \left(f(\mathbf{x}_k) - f(\mathbf{x}^*)\right). $$
选择学习率：令 $ \eta = \frac{2}{\mu + L} $，代入可得线性收敛速率。

五、总结

本文总结了梯度下降算法的一些知识点，先从直观角度理解算法的目标和行为，再引入数学上的定义和步骤，对其中关键的点进行了证明，同时给出了代码示例展示整个算法运行的过程。