首次给出PL条件下带马尔可夫噪声的SGD统一时间高概率界。
High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
- 用泊松方程处理马尔可夫噪声，结合概率归纳证明
- 实现期望次优性$1/k$衰减率，与最优率匹配
- 适用于分布式回归、隐私采样、在线识别等场景
本文首次在满足Polyak-Łojasiewicz条件且梯度噪声包含马尔可夫和鞅差分成分的情形下，建立了SGD的统一时间高概率边界。该结果显著拓展了有限时间保证的应用范围，因为PL条件广泛存在于机器学习与深度学习模型中，而马尔可夫噪声自然出现在分布式优化与在线系统辨识问题中。我们还允许噪声幅度随函数值增长，从而支持多种实际采样策略的分析。除了高概率保证外，我们还建立了期望次优性$1/k$的匹配衰减率。证明技巧依赖泊松方程处理马尔可夫噪声，并采用概率归纳法应对目标函数几乎处处有界性的缺失。最后，通过三个实际优化问题验证了框架的适用性：基于令牌的分布式线性回归、用于隐私增强的子采样监督学习，以及在线系统辨识。
原文摘要 · Abstract (English)
We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and deep learning models while Markovian noise naturally arises in decentralized optimization and online system identification problems. We further allow the magnitude of noise to grow with the function value, enabling the analysis of many practical sampling strategies. In addition to the high-probability guarantee, we establish a matching $1/k$ decay rate for the expected suboptimality. Our proof technique relies on the Poisson equation to handle the Markovian noise and a probabilistic induction argument to address the lack of almost-sure bounds on the objective. Finally, we demonstrate the applicability of our framework by analyzing three practical optimization problems: token-based decentralized linear regression, supervised learning with subsampling for privacy amplification, and online system identification.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。