随机规划中的随机拟梯度法 随机拟梯度法（Stochastic Quasi-Gradient Method, SQGM）是求解带有期望值目标函数的随机优化问题的一类迭代算法。它是确定性拟牛顿法在随机环境下的推广，适用于目标函数梯度无法精确计算、但可通过随机样本近似的情形。下面逐步展开讲解。 1. 问题背景与核心思想 考虑随机优化问题：min_ {x ∈ X} F(x) = E[ f(x, ξ) ]，其中ξ为随机变量，X为可行域。 若F(x)可微，经典梯度下降需计算∇F(x) = E[ ∇f(x, ξ) ]，但期望常难以解析求解。 随机梯度下降（SGD）采用无偏估计∇f(x, ξ_ t)代替梯度，但收敛速度受方差影响。 SQGM的核心改进：引入拟牛顿思想，通过随机样本构建梯度估计的同时，利用历史信息近似Hessian逆矩阵，降低方差并加速收敛。 2. 拟牛顿法的随机扩展 确定性拟牛顿法（如BFGS）的更新规则：x_ {k+1} = x_ k - α_ k H_ k ∇F(x_ k)，其中H_ k近似Hessian逆矩阵。 在随机环境中，∇F(x_ k)被随机拟梯度g_ k替代，需满足 渐近无偏性 ：E[ g_ k | x_ k] → ∇F(x_ k)（当k→∞）。 关键挑战：H_ k的更新需避免随机噪声积累。常用方法包括： 随机BFGS ：通过随机样本计算梯度差和参数差，但需控制更新条件（如只当曲率条件满足时更新）。 自适应矩阵缩放 ：使用对角矩阵近似H_ k，结合随机梯度幅值调整步长（类似AdaGrad思想）。 3. 算法框架与收敛条件 基本迭代格式：x_ {k+1} = Π_ X [ x_ k - α_ k H_ k g_ k]，其中Π_ X为投影算子，α_ k为步长。 随机拟梯度g_ k需满足： 一致性：E[ ∥g_ k - ∇F(x_ k)∥² ] → 0（均方收敛）。 有界方差：E[ ∥g_ k∥²] ≤ C(1 + ∥x_ k∥²)。 步长条件：α_ k → 0, ∑α_ k = ∞, ∑α_ k² < ∞（典型选择α_ k = O(1/k)）。 矩阵H_ k需保持一致正定且有界，例如通过正则化强制∥H_ k∥ ≤ M。 4. 方差缩减技术的结合 SQGM常与方差缩减方法（如SVRG、SAGA）结合，进一步改善收敛性： SVRG-SQGM ：定期计算全梯度估计，迭代中使用锚点梯度校正当前随机梯度。 控制变量法 ：构造g_ k = ∇f(x_ k, ξ_ k) + c_ k，其中c_ k为减少方差的控制项。 5. 应用场景与优势 适用于大规模随机规划问题（如机器学习中的经验风险最小化）。 相比SGD，在条件数较大的问题上收敛更快（近似二阶信息利用）。 在随机均衡问题、随机变分不等式中也有扩展应用。 6. 理论保证与扩展 几乎必然收敛：在步长和噪声条件下，x_ k以概率1收敛到稳定点。 收敛速率：在强凸条件下可达O(1/k)的次线性收敛，与SGD相同，但常数更优。 扩展方向包括非光滑问题的随机束方法、分布式随机拟梯度法等。