马尔可夫噪声下的高概率PL-SGD：最优混合与尾部依赖

# 具有马尔可夫噪声的高概率 PL-SGD：最优混合与尾依赖  
来源：https://arxiv.org/html/2606.26316  

Dhruv Sarkar¹,² Aprameyo Chakrabartty¹ Vaneet Aggarwal³  
¹印度理工学院克勒格布尔分校  
²穆罕默德·本·扎耶德人工智能大学  
³普渡大学  
dhruv\.sarkar223@gmail\.com aprameyo8858@gmail\.com vaneet@purdue\.edu  

###### 摘要  

我们研究在梯度样本由外生马尔可夫链生成时，满足 Polyak–Łojasiewicz (PL) 条件的平滑目标的一阶方法。在轻尾设定下，标准增长包络下普通随机梯度下降 (SGD) 的先验一致时间高概率界标度为 \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\)，与期望界 \(\widetilde{O}(t_{\mathrm{mix}}/k)\) 之间存在差距。我们通过使用滞后分块论证来弥补这一差距，在几何混合下建立了一个均匀高概率保证，其主导随机项为 \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\)。我们通过在一个由持久双态链驱动的二次目标上建立匹配的 \(\Omega(\sigma^2 t_{\mathrm{mix}}/k)\) 下界，证明了这种对混合时间的线性依赖是最优的。然后，我们将此框架扩展到满足平稳有限 \(p\) 阶矩条件 (\(p\in(1,2]\)) 的重尾马尔可夫梯度。我们设计了一种全样本裁剪分块方法，在利用每次马尔可夫转移的同时减轻马尔可夫偏差。在转移预算 \(T\) 下，该算法实现了 \(\widetilde{O}(\sigma_p^2 (t_{\mathrm{mix}}/T)^{2(p-1)/p})\) 的高概率随机误差。我们通过将 PL 优化约简为粘性马尔可夫链的重尾均值估计，建立了匹配的下界。最终，本工作严格刻画了轻尾 PL-SGD 中对混合时间的最优多项式依赖，以及鲁棒区的最优重尾指数和有效样本量依赖。  

**关键词**：随机梯度下降；马尔可夫噪声；Polyak–Łojasiewicz 条件；高概率界；混合时间；重尾噪声；裁剪 SGD；下界。  

## 1 引言  

随机梯度方法是随机逼近和大规模优化中的核心工具。随机逼近和随机梯度下降 (SGD) 的经典分析通常依赖于独立样本或条件无偏的鞅差梯度噪声 [57, 37, 5, 39, 9, 10]。在这些假设下，下降递归中的随机误差可以通过鞅或集中论证来控制，并且在许多凸、强凸和非凸场景中，非渐近收敛保证现已得到充分理解 [50, 27, 36]。然而，在许多现代应用中，梯度预言使用的样本是由马尔可夫链顺序生成的，而不是独立的。这种情况出现在基于令牌和随机游走的分布式优化 [30, 48, 28]、马尔可夫链蒙特卡洛梯度估计、具有时间排除规则的隐私保护子采样方案 [1, 14, 19]、在线系统辨识 [38] 以及强化学习和时间差分算法 [7, 59, 32, 43, 4, 24, 23] 中。在这些设定下，梯度预言通常仅在相对于链的不变分布平均后才无偏。在有限时间内，马尔可夫状态的条件律不一定平稳，因此产生的偏差必须通过链的混合行为来控制。本文针对满足 Polyak–Łojasiewicz (PL) 不等式的平滑目标研究此问题。PL 条件由 [54] 引入，并在 [35] 中发展为现代优化形式，它弱于强凸性，但对于确定性梯度下降仍能产生全局线性收敛。它是过参数化学习、最小二乘问题、控制以及其他可以在没有凸性情况下实现全局收敛的场景中的自然条件。  

我们考虑马尔可夫 SGD 递归  

\[
x_{k+1} = x_k - \alpha_k G_k, \quad G_k = g(x_k, Z_k) + M_{k+1},
\tag{1}
\]

其中 \((Z_k)_{k\ge 0}\) 是外生马尔可夫链，具有不变分布 \(\pi\)，平稳预言满足 \(\int g(x,z)\,\pi(dz) = \nabla f(x)\)，而 \((M_{k+1})_{k\ge 0}\) 是鞅差扰动。该预言允许满足有界 \(A\)-\(B\)-\(C\) 增长包络，称为 ABC 条件，因为常数 \(A, B, C\) 控制了梯度相关项、目标间隙相关项和加性噪声基底：  

\[
\|G_k\|^2 \le A\|\nabla f(x_k)\|^2 + B(f(x_k) - f^\star) + C.
\]

此条件在先前的 PL-SGD 分析 [33] 中使用。这种增长模型很重要，因为在 PL 问题、最小二乘模型、插值区域和小批量采样中，均匀有界方差假设可能过于严格。  

现在有大量关于马尔可夫采样的一阶方法和随机逼近的文献。马尔可夫随机梯度方法的有限时间分析已在凸、强凸和非凸设定中由 [60, 17, 18, 21] 开发。更一般的马尔可夫随机逼近和强化学习问题通常使用泊松方程分解来处理 [5, 39, 9, 49, 62]。最近的工作还研究了使用随机批处理、多级或方差缩减思想的几种一阶方法的最优混合时间依赖 [6, 21]。在与我们最相关的 PL 设定中，Kar、Chandak、Singh、Moulines、Bhatnagar 和 Bambos [33] 证明了在 ABC 预言包络下具有马尔可夫加鞅差噪声的 SGD 的第一个一致时间高概率保证。他们的期望界具有主导随机阶 \(\widetilde{O}(t_{\mathrm{mix}}/k)\)，而其一致高概率界具有主导随机阶 \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\)。因此，在本工作之前，尚不清楚高概率 PL-SGD 是否真的需要对混合时间的二次多项式依赖，或者期望界所暗示的线性依赖是否可以实现。  

我们的第一个主要结果表明最优多项式依赖是线性的。对于在有限 ABC 预言包络下的普通单样本 SGD，我们证明了一个一致时间高概率界，在几何混合下，其主导随机项标度为 \(\widetilde{O}\!\left(\frac{t_{\mathrm{mix}}}{k+K_0}\right)\)，直至对数因子和通常的优化瞬态 \(K_0\{f(x_0)-f^\star\}/(k+K_0)\)。隐藏常数依赖于光滑性、PL 和有界 ABC 包络常数，包括假设 2 中的噪声尺度项。我们还通过一个由持久双态马尔可夫链驱动的一维二次 PL 目标证明了匹配的下界：在期望中且以恒定概率有 \(f(x_k)-f^\star = \Omega\!\left(\frac{\sigma^2 t_{\mathrm{mix}}}{k}\right)\)。因此，在同类实例上有效的任何定理都不能在 \(t_{\mathrm{mix}}\) 的多项式依赖上改进到线性以下，除去对数因子。  

### 1.1 技术挑战与证明创新  

主要的技术困难在于 PL 下降递归中的马尔可夫项是一个*自适应*的马尔可夫加性泛函。在引理 2 的加权下降递归中，随机部分包含  

\[
\sum_{\ell=0}^{k-1} w_{\ell,k} h(x_\ell, Z_\ell), \quad h(x,z) = \langle \nabla f(x),\, g(x,z) - \nabla f(x) \rangle,
\]

其中 \(h\) 定义在 (16) 中。对于每个固定的 \(x\)，假设 2 中的平稳梯度恒等式意味着 \(\int h(x,z)\,\pi(dz)=0\)。然而，在给定过去条件下，\(Z_\ell\) 不一定按 \(\pi\) 分布，而 \(x_\ell\) 本身由之前的马尔可夫状态和鞅扰动生成。因此，\(h(x_\ell, Z_\ell)\) 既不是鞅差，也不是马尔可夫链的固定加性泛函。标准的鞅集中不能直接应用，固定马尔可夫链可观测量的经典集中不等式也不能以黑盒方式使用。  

#### 泊松方程的局限性  

解耦时间依赖的标准机制依赖于泊松方程的解。该框架通过解 \(V(x,z)\) 表示局部梯度偏差，从而产生一个鞅差序列。例如，在 Kar 等人 [33] 的近期高概率 PL-SGD 分析中，该解（参见其中的引理 4.1）定义为无限视界和：  

\[
V(x,z) := \mathbb{E}\left[ \sum_{j=0}^\infty \big(g(x, Z_j) - \nabla f(x)\big) \;\Big|\; Z_0 = z \right].
\tag{2}
\]

这使得马尔可夫噪声可以完美分解为 \(g(x,z) - \nabla f(x) = V(x,z) - \int V(x,z') p(dz'|z)\)。虽然此恒等式成功地分离出一个严格的鞅差序列（定义为 \(\tilde{M}_{\ell+1} := V(x_\ell, Z_{\ell+1}) - \int V(x_\ell, z) p(dz|Z_\ell)\)），但这是通过无意中放大随机增量的幅度实现的。由于马尔可夫链需要 \(\mathcal{O}(t_{\mathrm{mix}})\) 步才能收缩到不变测度 \(\pi\)，定义 \(V(x,z)\) 的几何级数迫使其幅度线性依赖于混合时间。Kar 等人将其依赖形式化在他们的引理 C.1 中，建立了结构上界 \(\|V(x,z)\|^2 \le \mathcal{O}(t_{\mathrm{mix}}^2 \cdot \Delta(x))\)。当对导出的鞅应用一致时间集中不等式（如 Azuma-Hoeffding 界）时，方差代理依赖于几乎必然增量界的平方。通过测量增量固有有界范围为 \(\mathcal{O}(t_{\mathrm{mix}})\) 的鞅的偏差，得到的集中界累积了 \(\mathcal{O}(t_{\mathrm{mix}}^2)\) 的多项式惩罚。这种二次依赖反映了该证明路径的局限性，并相对于期望界中可实现的线性 \(\mathcal{O}(t_{\mathrm{mix}})\) 标度留下了差距。  

#### 我们的方法：滞后分块与时间条件  

我们的证明通过改变调节结构（而不是通过泊松修正子改变可观测量）来避免这种损失。对于固定的目标时间 \(k\)，从 (18) 中选择解析延迟 \(m_k\)。对于 \(\ell \ge m_k\)，分解  

\[
h(x_\ell, Z_\ell) = h(x_{\ell-m_k}, Z_\ell) + \bigl\{ h(x_\ell, Z_\ell) - h(x_{\ell-m_k}, Z_\ell) \bigr\}.
\]

前 \(m_k\) 个索引单独处理为初始窗口项，在引理 9 中控制。对于剩余项，延迟迭代 \(x_{\ell-m_k}\) 是 \(\mathcal{F}_{\ell-m_k}\) 可测的，而根据假设 3，链在时间 \(\ell\) 之前有 \(m_k\) 次转移趋向平稳。令  

\[
Y_\ell := w_{\ell,k} h(x_{\ell-m_k}, Z_\ell), \quad \overline{Y}_\ell := \mathbb{E}[Y_\ell \mid \mathcal{F}_{\ell-m_k}],
\]

如 (65) 中，马尔可夫和分解为初始窗口、中心化延迟鞅部分、混合偏差部分和替换部分：  

\[
\begin{aligned}
\sum_{\ell=0}^{k-1} w_{\ell,k} h(x_\ell, Z_\ell) &=
\sum_{\ell=0}^{m_k-1} w_{\ell,k} h(x_\ell, Z_\ell) \\
&\quad + \sum_{\ell=m_k}^{k-1} (Y_\ell - \overline{Y}_\ell) \\
&\quad + \sum_{\ell=m_k}^{k-1} \overline{Y}_\ell \\
&\quad + \sum_{\ell=m_k}^{k-1} w_{\ell,k} \bigl\{ h(x_\ell, Z_\ell) - h(x_{\ell-m_k}, Z_\ell) \bigr\}.
\end{aligned}
\]

中心化延迟项通过引理 6 中的剩余类鞅论证控制。索引按模 \(m_k\) 分割。沿固定剩余类，连续的延迟项恰好由 \(m_k\) 次马尔可夫转移分隔，因此在减去 \(\overline{Y}_\ell\) 后，它们相对于降采样滤子形成一个鞅差序列。对于实际的 PL 递归，相关对象是上述加权和，剩余类界涉及加权平方和 \(\sum_{\ell} c, c_0 > 0\)。因此，在恒定置信度下，对混合时间的线性多项式依赖是不可避免的。  

4. 我们将滞后分块观点扩展到有限 \(p\) 重尾马尔可夫梯度。所提出的全样本裁