High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence

技术摘要：高概率 PL-SGD 与马尔可夫噪声

问题表述
本文研究了满足 Polyak-Łojasiewicz (PL) 条件的平滑目标函数的阶一随机优化方法，其中梯度样本是由外生马尔可夫链而非独立样本生成的。该设定涉及递归式 $x_{k+1} = x_k - \alpha_k G_k$，其中 $G_k = g(x_k, Z_k) + M_{k+1}$。这里 $(Z_k)$ 是具有不变分布 $\pi$ 的马尔可夫链，$g(x, \cdot)$ 是一个满足 $\int g(x, z)\pi(dz) = \nabla f(x)$ 的算子，$M_{k+1}$ 是鞅差扰动。梯度算子满足有界的“ABC”增长包络 $\|G_k\|^2 \leq A\|\nabla f(x_k)\|^2 + B(f(x_k) - f^\star) + C$，这允许梯度方差随目标差距和梯度范数进行缩放，这是过参数化学习和最小二乘问题中的常见特征。

本文解决的主要挑战是噪声的时间依赖性。与独立或鞅噪声不同，马尔可夫噪声引入了一种仅随链的混合而衰减的偏差。先前的研究确立了规模为 $\tilde{O}(t_{\text{mix}}/k)$ 的期望界限，但高概率界限规模为 $\tilde{O}(t_{\text{mix}}^2/k)$，这留下了一个疑问：二次方依赖于混合时间 $t_{\text{mix}}$ 的现象究竟是本质属性，还是证明技术（特别是 Poisson 方程分解）造成的产物。

方法论
本文针对轻尾和重尾情形采用了两种不同的方法论框架：

1. 轻尾情形（有界 ABC 包络）：

   • 滞后分块（Lag-Blocking）论证： 为了避免使用会放大噪声幅度的 Poisson 方程分解（其放大因子为 $t_{\text{mix}}$），作者引入了一种“滞后分块”技术。对于目标时间 $k$，他们引入了一个解析延迟 $m_k$。马尔可夫下降项被分解为延迟部分、混合偏差部分、替换误差部分以及初始窗口部分。
   • 剩余类鞅（Residue-Class Martingales）： 通过对 $m_k$ 步之前的 $\sigma$-代数进行条件化，延迟的可观测项变为关于降采样过滤的鞅差。总和被拆分为 $m_k$ 个剩余类。在每个类内应用集中不等式（Azuma-Hoeffding），从而避免了类之间需要独立性的问题。
   • 偏差与误差控制： 混合偏差通过全变分混合剖面进行控制，而由于迭代点在延迟期间移动导致的替换误差则通过算子的 Lipschitz 连续性和 ABC 包络进行界定。

2. 重尾情形（有限 $p$ 阶矩，$p \in (1, 2]$）：

   • 全样本裁剪块方法（All-Samples Clipped Block Method）： 为了处理仅具有有限 $p$ 阶矩（方差可能无穷大）的梯度，作者提出了一种基于块的算法。在连续的 $b$ 个马尔可夫转移过程中，迭代点保持不变。在该块内的每个梯度都进行逐坐标裁剪，并使用这些裁剪样本的平均值进行更新。
   • 无样本丢弃： 不同于某些通过丢弃样本来确保独立性的鲁棒方法，该方法利用了块内的每一个马尔可夫转移。混合窗口仅通过分析（滞后分块）和裁剪阈值的选择进入分析过程。
   • 集中性： 分析结合了平稳裁剪偏差/方差估计，以及针对连续块的剩余类鞅集中性论证，这与轻尾情形类似，但使用了 Freedman 不等式进行了重尾适配。

核心贡献与结果

1. 轻尾 PL-SGD 的最优高概率界限：

   • 本文为具有几何混合性质的普通单样本 SGD 建立了统一时间的高概率界限。领先的随机项规模为 $\tilde{O}\left(\frac{t_{\text{mix}}}{k + K_0}\right)$。
   • 该结果弥合了 $\tilde{O}(t_{\text{mix}}/k)$ 期望界限与此前已知的 $\tilde{O}(t_{\text{mix}}^2/k)$ 高概率界限之间的差距，证明了在不修改标准 SGD 算法的情况下，实现线性依赖于混合时间的复杂度是可行的。

2. 匹配的下界：

   • 文中证明了一个由持久性两状态马尔可夫链驱动的一维二次目标的下界。结果表明 $\mathbb{E}[f(x_k) - f^\star] = \Omega(\sigma^2 t_{\text{mix}}/k)$ 且以常数概率成立。
   • 这证实了在常数置信度下，对于高概率保证而言，线性多项式依赖于 $t_{\text{mix}}$ 是不可避免的。

3. 重尾鲁棒优化：

   • 对于梯度仅具有有限平稳 $p$ 阶矩的情况，所提出的裁剪块方法实现了高概率随机误差 $\tilde{O}\left(\sigma_p^2 \left(\frac{t_{\text{mix}}}{T}\right)^{2(p-1)/p}\right)$，其中 $T$ 是总转移预算。
   • 通过使用“粘性（sticky）”马尔可夫链构建的匹配下界，证明了指数 $2(p-1)/p$ 以及对有效样本量（$T/t_{\text{mix}}$）的依赖关系是优化的。

意义与主张
本文声称精确地刻画了马尔可夫依赖对 PL 随机优化的统计代价。

• 对于轻尾噪声： 它解决了关于先前高概率界限中是否存在二次方混合时间依赖性的开放性问题。通过证明匹配的下界和线性上界，它确立了普通 SGD 在混合时间上的多项式依赖是达到最优的。
• 对于重尾噪声： 它将鲁棒优化保证扩展到了马尔可夫设定，表明有效样本量被混合时间所削减，并且有限阶矩的指数是不可避免的。
• 方法论创新： 滞后分块论证被呈现为一种优于 Poisson 方程分解的用于高概率分析的方法，因为它避免了人为放大噪声幅度的副作用，同时保持了标准 SGD 算法的简洁性。

本文并未声称在重尾上界中实现了关于维度依赖的最优性，并指出其下界构造是基于一维情形的。同时，文中指出其分析假设的是外生马尔可夫链，而参数依赖型核（例如在 Actor-Critic 方法中）仍是一个开放的研究方向。