High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

• URL: http://arxiv.org/abs/2603.14514v1
• Date: Sun, 15 Mar 2026 17:50:03 GMT
• Title: High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
• Abstract summary: 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.<n>This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and deep learning models.
• Score: 27.3629260943211
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• High-Probability Convergence of SGD via Batched Updates [4.862625283098196]
  Batched SGD is a simple variant that iterates online epochs into optimizations.<n>Our main contribution demonstrates that this mechanism enables a surprisingly simple high-probability analysis.
  arXiv  Detail & Related papers  (2026-09-11T12:17:18Z)
• Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation [16.106678611834102]
  Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed noise.<n>Existing techniques typically rely on magnitude checks, which fail to distinguish informative geometric signals from outliers.
  arXiv  Detail & Related papers  (2026-06-21T10:57:37Z)
• Decoded Quantum Interferometry Under Noise [4.180458188910334]
  We present a rigorous analysis of Decoded Quantum Interferometry (DQI) under noise.<n>For the maximum linear satisfiability problem, we prove that, in the presence of noise, performance is governed by a noise-weighted sparsity parameter of the instance matrix.<n>We offer guidance on preserving DQI's potential quantum advantage under realistic noise.
  arXiv  Detail & Related papers  (2025-08-14T15:08:09Z)
• Differentially Private Clipped-SGD: High-Probability Convergence with Arbitrary Clipping Level [18.723330586196997]
  We provide the first high-probability convergence analysis for DP with a fixed clipping level.<n>Our results show that, with a fixed clipping level, the method converges to a neighborhood optimal solution with a faster rate than the existing ones.<n>The neighborhood is balanced against the noise introduced by DP, providing a refined trade-off between convergence speed and privacy guarantees.
  arXiv  Detail & Related papers  (2025-07-31T12:48:29Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• CoLiDE: Concomitant Linear DAG Estimation [12.415463205960156]
  We deal with the problem of learning acyclic graph structure from observational data to a linear equation. We propose a new convex score function for sparsity-aware learning DAGs.
  arXiv  Detail & Related papers  (2023-10-04T15:32:27Z)
• Probabilistic Reach-Avoid for Bayesian Neural Networks [71.67052234622781]
  We show that an optimal synthesis algorithm can provide more than a four-fold increase in the number of certifiable states. The algorithm is able to provide more than a three-fold increase in the average guaranteed reach-avoid probability.
  arXiv  Detail & Related papers  (2023-10-03T10:52:21Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  We introduce a general approach for seeking high dimensional non-linear optimization problems in which maintaining safety during learning is crucial. Our approach called LBSGD is based on applying a logarithmic barrier approximation with a carefully chosen step size. We demonstrate the effectiveness of our approach on minimizing violation in policy tasks in safe reinforcement learning.
  arXiv  Detail & Related papers  (2022-07-21T11:14:47Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Probabilistic robust linear quadratic regulators with Gaussian processes [73.0364959221845]
  Probabilistic models such as Gaussian processes (GPs) are powerful tools to learn unknown dynamical systems from data for subsequent use in control design. We present a novel controller synthesis for linearized GP dynamics that yields robust controllers with respect to a probabilistic stability margin.
  arXiv  Detail & Related papers  (2021-05-17T08:36:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.