自适应梯度下降（AdaGrad）算法在非凸随机优化中的基础应用

字数 4599 2025-12-14 17:41:40

自适应梯度下降（AdaGrad）算法在非凸随机优化中的基础应用

题目描述

考虑一个无约束的非凸随机优化问题：

\[\min_{x \in \mathbb{R}^n} f(x) := \mathbb{E}_{\xi}[F(x; \xi)] \]

其中，目标函数 $f(x)$ 是非凸的，且我们无法直接计算其梯度 $\nabla f(x)$。我们只能通过随机抽样得到随机梯度 $g(x; \xi) = \nabla_x F(x; \xi)$，并满足无偏性条件：$\mathbb{E}_{\xi}[g(x; \xi)] = \nabla f(x)$。此外，随机梯度的方差是有限的，即 $\mathbb{E}[ \| g(x; \xi) - \nabla f(x) \|^2 ] \le \sigma^2$。

AdaGrad算法 是一种自适应步长的随机梯度下降法，它通过累积历史梯度的平方和来自适应地为每个参数分量调整学习率。其基本思想是：对于那些历史上梯度较大的参数，说明该方向可能比较陡峭或不稳定，应给予较小的步长；反之，对于梯度较小的参数，说明该方向可能较平缓，可以给予较大的步长以加快收敛。

本题的目标是：理解并推导AdaGrad算法的更新公式，分析其在非凸随机优化问题中的收敛性质，并通过一个简单例子（如最小化一个非凸的随机函数）来演示算法的实现步骤。

解题过程详解

第一步：问题形式化与AdaGrad算法动机

标准随机梯度下降（SGD）的局限性：
- 标准SGD的更新公式为：$x_{k+1} = x_k - \alpha_k g_k$，其中 $\alpha_k$ 是固定的或预先设定的步长（学习率）。
- 在非凸问题中，不同维度的梯度量级可能差异很大。固定步长对所有维度“一视同仁”，可能导致在梯度大的维度上更新步伐过大（可能引起震荡甚至发散），在梯度小的维度上更新步伐过小（收敛缓慢）。
AdaGrad的核心思想：
- 为每个参数 $x^{(i)}$ 维护一个独立的自适应步长。
- 这个步长与该参数历史梯度平方和的平方根成反比。历史梯度大的维度，累积和 $G_{k}^{(i)}$ 大，步长就自动变小。
- 数学上，它通过一个对角矩阵 $D_k$ 来调整梯度方向，这个对角矩阵的元素是历史梯度平方和的逆平方根。

第二步：AdaGrad算法公式推导

定义累积梯度外积：
初始化一个向量 $s_0 = \mathbf{0} \in \mathbb{R}^n$。
在第 $k$ 次迭代，计算随机梯度 $g_k = g(x_k; \xi_k)$。
更新累积平方梯度（按分量）：

\[ s_{k}^{(i)} = s_{k-1}^{(i)} + (g_k^{(i)})^2, \quad i = 1, 2, \dots, n \]

这里 $ s_k^{(i)} $ 是一个标量，表示到第 $ k $ 轮为止，第 $ i $ 个维度上所有随机梯度分量的平方和。写成向量形式为：

\[ s_k = s_{k-1} + g_k \odot g_k \]

其中 $ \odot $ 表示逐元素乘法（Hadamard积）。

构造自适应缩放矩阵：
定义对角矩阵 $D_k = \text{diag}( \delta I + \sqrt{s_k} )^{-1}$。即：

\[ D_k = \text{diag} \left( \frac{1}{\sqrt{\delta + \sqrt{s_k^{(1)}}}, \frac{1}{\sqrt{\delta + \sqrt{s_k^{(2)}}}, \dots, \frac{1}{\sqrt{\delta + \sqrt{s_k^{(n)}}} } \right) \]

实践中，更常见且直接的形式是避免对 $ s_k $ 再开方，而是：

\[ D_k = \text{diag} \left( \frac{1}{\sqrt{\delta + s_k^{(1)}}}, \frac{1}{\sqrt{\delta + s_k^{(2)}}}, \dots, \frac{1}{\sqrt{\delta + s_k^{(n)}}} \right) \]

其中 $ \delta > 0 $ 是一个很小的常数（例如 $ 10^{-8} $），用于防止除以零，并保证数值稳定性。注意，这里 $ s_k $ 的定义是梯度平方的累积和，所以其平方根 $ \sqrt{s_k^{(i)}} $ 大致反映了历史梯度的大小。

AdaGrad更新公式：

\[ x_{k+1} = x_k - \alpha D_k g_k \]

其中 $ \alpha > 0 $ 是一个全局步长（或称为初始学习率）。
- 将上式按分量展开：

\[ x_{k+1}^{(i)} = x_k^{(i)} - \frac{\alpha}{\sqrt{\delta + s_k^{(i)}}} \cdot g_k^{(i)}, \quad i = 1, \dots, n \]

- 可以看到，每个参数 $ x^{(i)} $ 的更新步长是 $ \alpha / \sqrt{\delta + s_k^{(i)}} $。随着迭代进行，$ s_k^{(i)} $ 单调增加，导致步长单调递减。这是AdaGrad的一个重要特性。

第三步：收敛性分析（直观理解）

对于非凸随机优化，我们通常关心算法是否能找到目标函数的平稳点（即梯度为零的点）。AdaGrad的收敛性可以从以下几个方面直观理解：

步长衰减：由于每个维度的步长 $\alpha / \sqrt{\delta + s_k^{(i)}}$ 是随时间衰减的，这有助于算法在后期稳定下来，避免在最优解附近震荡。
自适应缩放：梯度大的方向被抑制，梯度小的方向被相对放大。这种自动的尺度调整，使得算法对不同尺度特征的参数更新更为均衡，有助于改善条件数较差问题的收敛速度。
理论保证：在适当的假设下（如函数有下界、梯度方差有限、步长 $\alpha$ 选择合适），可以证明AdaGrad产生的序列满足：

\[ \liminf_{k \to \infty} \mathbb{E}[ \| \nabla f(x_k) \|^2 ] = 0 \]

这意味着算法最终会收敛到一个平稳点（可能是局部极小点、鞍点或极大点）。

第四步：算法实现步骤

以最小化一个简单的非凸随机函数为例，比如：

\[f(x) = \frac{1}{2}x_1^2 + 100 \cdot \sin^2(x_2) + \epsilon, \quad \epsilon \sim \mathcal{N}(0, 0.1^2) \]

其中 $x = (x_1, x_2)^T$。随机性体现在附加的高斯噪声 $\epsilon$ 上。其真实梯度为 $\nabla f(x) = (x_1, 200 \sin(x_2) \cos(x_2))^T$。我们只能得到带有噪声的观测：$g(x) = \nabla f(x) + \nu, \quad \nu \sim \mathcal{N}(0, 0.05^2 I)$。

初始化：
- 设定初始点 $x_0 = (3.0, 1.5)^T$。
- 设定初始累积向量 $s_0 = (0, 0)^T$。
- 选择参数：全局步长 $\alpha = 0.5$，常数 $\delta = 10^{-8}$，最大迭代次数 $K = 2000$。
主迭代循环（对于 $k = 0, 1, \dots, K-1$）：
a. 采样随机梯度：在当前点 $x_k$，计算带噪声的随机梯度 $g_k$。
例如，计算真实梯度 $\nabla f(x_k)$ 后，加上一个从 $\mathcal{N}(0, 0.05^2 I)$ 采样的噪声向量 $\nu_k$。
b. 更新累积平方梯度：
$s_{k+1}^{(1)} = s_k^{(1)} + (g_k^{(1)})^2$
$s_{k+1}^{(2)} = s_k^{(2)} + (g_k^{(2)})^2$
（向量操作：$s_{k+1} = s_k + g_k \odot g_k$）
c. 计算自适应步长向量：
构造向量 $\eta_k$，其中 $\eta_k^{(i)} = \alpha / \sqrt{\delta + s_{k+1}^{(i)}}$。
（注意：这里用 $s_{k+1}$ 是因为我们先累积了当前梯度的平方。有些变体使用 $s_k$，区别在于索引，不影响算法本质。）
d. 更新参数：
$x_{k+1}^{(1)} = x_k^{(1)} - \eta_k^{(1)} \cdot g_k^{(1)}$
$x_{k+1}^{(2)} = x_k^{(2)} - \eta_k^{(2)} \cdot g_k^{(2)}$
（向量操作：$x_{k+1} = x_k - \eta_k \odot g_k$）
输出：最终得到的点 $x_K$，并计算其函数值 $f(x_K)$ 和梯度范数 $\| \nabla f(x_K) \|$ 作为收敛性的近似度量。

第五步：算法特点与讨论

优点：
- 完全自适应：无需为每个维度手动调整学习率。
- 适合稀疏数据/梯度：对于不常出现的特征（对应梯度经常为零的维度），累积平方和小，步长大，使得这些特征对应的参数能快速更新。这使得AdaGrad在自然语言处理等稀疏数据问题上表现出色。
- 理论上有较严格的收敛保证。
缺点：
- 步长单调递减：由于累积平方和 $s_k^{(i)}$ 只增不减，步长会持续减小，最终可能变得过小，导致在非凸问题中可能过早停止更新，陷入一个不是很好的平稳点。
- 对于某些问题，累积平方和可能增长过快，导致步长过早变得极小，收敛缓慢。
后续改进：
为了克服步长单调递减的问题，后续出现了RMSProp、Adam等算法，它们引入了衰减因子（滑动平均）来累积历史梯度平方，使得步长可以动态调整，避免了过度衰减。

总结
AdaGrad算法通过为每个参数维度独立地自适应调整步长，有效应对了随机优化中梯度量级差异大和稀疏性的挑战。其核心在于利用历史梯度平方和的平方根来缩放当前梯度。虽然存在步长单调递减的潜在缺点，但它为自适应随机优化算法的发展奠定了重要基础。理解其推导、更新规则和基本性质，是掌握更复杂自适应优化器（如Adam）的关键前提。

自适应梯度下降（AdaGrad）算法在非凸随机优化中的基础应用题目描述考虑一个无约束的非凸随机优化问题： $$ \min_ {x \in \mathbb{R}^n} f(x) := \mathbb{E} {\xi}[ F(x; \xi) ] $$ 其中，目标函数 $ f(x) $ 是非凸的，且我们无法直接计算其梯度 $ \nabla f(x) $。我们只能通过随机抽样得到随机梯度 $ g(x; \xi) = \nabla_ x F(x; \xi) $，并满足无偏性条件：$ \mathbb{E} {\xi}[ g(x; \xi)] = \nabla f(x) $。此外，随机梯度的方差是有限的，即 $ \mathbb{E}[ \| g(x; \xi) - \nabla f(x) \|^2 ] \le \sigma^2 $。 AdaGrad算法是一种自适应步长的随机梯度下降法，它通过累积历史梯度的平方和来自适应地为每个参数分量调整学习率。其基本思想是：对于那些历史上梯度较大的参数，说明该方向可能比较陡峭或不稳定，应给予较小的步长；反之，对于梯度较小的参数，说明该方向可能较平缓，可以给予较大的步长以加快收敛。本题的目标是：理解并推导AdaGrad算法的更新公式，分析其在非凸随机优化问题中的收敛性质，并通过一个简单例子（如最小化一个非凸的随机函数）来演示算法的实现步骤。解题过程详解第一步：问题形式化与AdaGrad算法动机标准随机梯度下降（SGD）的局限性：标准SGD的更新公式为：$ x_ {k+1} = x_ k - \alpha_ k g_ k $，其中 $ \alpha_ k $ 是固定的或预先设定的步长（学习率）。在非凸问题中，不同维度的梯度量级可能差异很大。固定步长对所有维度“一视同仁”，可能导致在梯度大的维度上更新步伐过大（可能引起震荡甚至发散），在梯度小的维度上更新步伐过小（收敛缓慢）。 AdaGrad的核心思想：为每个参数 $ x^{(i)} $ 维护一个独立的自适应步长。这个步长与该参数历史梯度平方和的平方根成反比。历史梯度大的维度，累积和 $ G_ {k}^{(i)} $ 大，步长就自动变小。数学上，它通过一个对角矩阵 $ D_ k $ 来调整梯度方向，这个对角矩阵的元素是历史梯度平方和的逆平方根。第二步：AdaGrad算法公式推导定义累积梯度外积：初始化一个向量 $ s_ 0 = \mathbf{0} \in \mathbb{R}^n $。在第 $ k $ 次迭代，计算随机梯度 $ g_ k = g(x_ k; \xi_ k) $。更新累积平方梯度（按分量）： $$ s_ {k}^{(i)} = s_ {k-1}^{(i)} + (g_ k^{(i)})^2, \quad i = 1, 2, \dots, n $$ 这里 $ s_ k^{(i)} $ 是一个标量，表示到第 $ k $ 轮为止，第 $ i $ 个维度上所有随机梯度分量的平方和。写成向量形式为： $$ s_ k = s_ {k-1} + g_ k \odot g_ k $$ 其中 $ \odot $ 表示逐元素乘法（Hadamard积）。构造自适应缩放矩阵：定义对角矩阵 $ D_ k = \text{diag}( \delta I + \sqrt{s_ k} )^{-1} $。即： $$ D_ k = \text{diag} \left( \frac{1}{\sqrt{\delta + \sqrt{s_ k^{(1)}}}, \frac{1}{\sqrt{\delta + \sqrt{s_ k^{(2)}}}, \dots, \frac{1}{\sqrt{\delta + \sqrt{s_ k^{(n)}}} } \right) $$ 实践中，更常见且直接的形式是避免对 $ s_ k $ 再开方，而是： $$ D_ k = \text{diag} \left( \frac{1}{\sqrt{\delta + s_ k^{(1)}}}, \frac{1}{\sqrt{\delta + s_ k^{(2)}}}, \dots, \frac{1}{\sqrt{\delta + s_ k^{(n)}}} \right) $$ 其中 $ \delta > 0 $ 是一个很小的常数（例如 $ 10^{-8} $），用于防止除以零，并保证数值稳定性。注意，这里 $ s_ k $ 的定义是梯度平方的累积和，所以其平方根 $ \sqrt{s_ k^{(i)}} $ 大致反映了历史梯度的大小。 AdaGrad更新公式： $$ x_ {k+1} = x_ k - \alpha D_ k g_ k $$ 其中 $ \alpha > 0 $ 是一个全局步长（或称为初始学习率）。将上式按分量展开： $$ x_ {k+1}^{(i)} = x_ k^{(i)} - \frac{\alpha}{\sqrt{\delta + s_ k^{(i)}}} \cdot g_ k^{(i)}, \quad i = 1, \dots, n $$ 可以看到，每个参数 $ x^{(i)} $ 的更新步长是 $ \alpha / \sqrt{\delta + s_ k^{(i)}} $。随着迭代进行，$ s_ k^{(i)} $ 单调增加，导致步长单调递减。这是AdaGrad的一个重要特性。第三步：收敛性分析（直观理解）对于非凸随机优化，我们通常关心算法是否能找到目标函数的平稳点（即梯度为零的点）。AdaGrad的收敛性可以从以下几个方面直观理解：步长衰减：由于每个维度的步长 $ \alpha / \sqrt{\delta + s_ k^{(i)}} $ 是随时间衰减的，这有助于算法在后期稳定下来，避免在最优解附近震荡。自适应缩放：梯度大的方向被抑制，梯度小的方向被相对放大。这种自动的尺度调整，使得算法对不同尺度特征的参数更新更为均衡，有助于改善条件数较差问题的收敛速度。理论保证：在适当的假设下（如函数有下界、梯度方差有限、步长 $ \alpha $ 选择合适），可以证明AdaGrad产生的序列满足： $$ \liminf_ {k \to \infty} \mathbb{E}[ \| \nabla f(x_ k) \|^2 ] = 0 $$ 这意味着算法最终会收敛到一个平稳点（可能是局部极小点、鞍点或极大点）。第四步：算法实现步骤以最小化一个简单的非凸随机函数为例，比如： $$ f(x) = \frac{1}{2}x_ 1^2 + 100 \cdot \sin^2(x_ 2) + \epsilon, \quad \epsilon \sim \mathcal{N}(0, 0.1^2) $$ 其中 $ x = (x_ 1, x_ 2)^T $。随机性体现在附加的高斯噪声 $ \epsilon $ 上。其真实梯度为 $ \nabla f(x) = (x_ 1, 200 \sin(x_ 2) \cos(x_ 2))^T $。我们只能得到带有噪声的观测：$ g(x) = \nabla f(x) + \nu, \quad \nu \sim \mathcal{N}(0, 0.05^2 I) $。初始化：设定初始点 $ x_ 0 = (3.0, 1.5)^T $。设定初始累积向量 $ s_ 0 = (0, 0)^T $。选择参数：全局步长 $ \alpha = 0.5 $，常数 $ \delta = 10^{-8} $，最大迭代次数 $ K = 2000 $。主迭代循环（对于 $ k = 0, 1, \dots, K-1 $）： a. 采样随机梯度：在当前点 $ x_ k $，计算带噪声的随机梯度 $ g_ k $。例如，计算真实梯度 $ \nabla f(x_ k) $ 后，加上一个从 $ \mathcal{N}(0, 0.05^2 I) $ 采样的噪声向量 $ \nu_ k $。 b. 更新累积平方梯度： $ s_ {k+1}^{(1)} = s_ k^{(1)} + (g_ k^{(1)})^2 $ $ s_ {k+1}^{(2)} = s_ k^{(2)} + (g_ k^{(2)})^2 $ （向量操作：$ s_ {k+1} = s_ k + g_ k \odot g_ k $） c. 计算自适应步长向量：构造向量 $ \eta_ k $，其中 $ \eta_ k^{(i)} = \alpha / \sqrt{\delta + s_ {k+1}^{(i)}} $。（注意：这里用 $ s_ {k+1} $ 是因为我们先累积了当前梯度的平方。有些变体使用 $ s_ k $，区别在于索引，不影响算法本质。） d. 更新参数： $ x_ {k+1}^{(1)} = x_ k^{(1)} - \eta_ k^{(1)} \cdot g_ k^{(1)} $ $ x_ {k+1}^{(2)} = x_ k^{(2)} - \eta_ k^{(2)} \cdot g_ k^{(2)} $ （向量操作：$ x_ {k+1} = x_ k - \eta_ k \odot g_ k $）输出：最终得到的点 $ x_ K $，并计算其函数值 $ f(x_ K) $ 和梯度范数 $ \| \nabla f(x_ K) \| $ 作为收敛性的近似度量。第五步：算法特点与讨论优点：完全自适应：无需为每个维度手动调整学习率。适合稀疏数据/梯度：对于不常出现的特征（对应梯度经常为零的维度），累积平方和小，步长大，使得这些特征对应的参数能快速更新。这使得AdaGrad在自然语言处理等稀疏数据问题上表现出色。理论上有较严格的收敛保证。缺点：步长单调递减：由于累积平方和 $ s_ k^{(i)} $ 只增不减，步长会持续减小，最终可能变得过小，导致在非凸问题中可能过早停止更新，陷入一个不是很好的平稳点。对于某些问题，累积平方和可能增长过快，导致步长过早变得极小，收敛缓慢。后续改进：为了克服步长单调递减的问题，后续出现了RMSProp、Adam等算法，它们引入了衰减因子（滑动平均）来累积历史梯度平方，使得步长可以动态调整，避免了过度衰减。总结 AdaGrad算法通过为每个参数维度独立地自适应调整步长，有效应对了随机优化中梯度量级差异大和稀疏性的挑战。其核心在于利用历史梯度平方和的平方根来缩放当前梯度。虽然存在步长单调递减的潜在缺点，但它为自适应随机优化算法的发展奠定了重要基础。理解其推导、更新规则和基本性质，是掌握更复杂自适应优化器（如Adam）的关键前提。