📊 statistics

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

This paper establishes the first uniform-in-time high-probability convergence bounds and matching $1/k$ expected suboptimality rates for Stochastic Gradient Descent under the Polyak-Lojasiewicz condition, accounting for mixed Markovian and martingale noise with state-dependent magnitudes across decentralized, privacy-preserving, and system identification applications.

Original authors: Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy mountain range. This is what machine learning models do when they "learn": they try to minimize an error function (the height of the mountain) to find the best solution (the valley).

The tool they use to navigate is called Stochastic Gradient Descent (SGD). Think of SGD as a hiker taking steps downhill. At every step, the hiker looks around to see which way is down and takes a step in that direction.

However, in the real world, the hiker isn't perfect. They can't see the whole mountain clearly. Sometimes the ground is slippery, or the wind blows them off course. This is noise.

The Problem: The "Foggy" and "Correlated" Hiker

For a long time, mathematicians assumed that the hiker's mistakes (noise) were like flipping a fair coin at every step. If you got blown left today, you had a 50/50 chance of getting blown right tomorrow. This is called "random noise" or a "martingale."

But in many real-world scenarios, the noise isn't that random. It's Markovian.

The Analogy: Imagine the hiker is walking through a forest where the wind doesn't just change randomly; it follows a pattern. If the wind is blowing from the North today, it's very likely to blow from the North tomorrow, and maybe the day after. The mistakes are correlated.
Why it matters: If the hiker gets pushed off course by a gust of wind, and the wind keeps blowing them in the same direction for a while, they might wander far away from the path before the wind finally changes. Standard math tools often fail to predict how far they might get lost in this "sticky" wind.

The Solution: A New Map for the Hiker

This paper presents a new, highly reliable map for hikers (algorithms) navigating these tricky, wind-swept mountains. Specifically, it focuses on mountains that have a special shape called the Polyak-Łojasiewicz (PL) condition.

The PL Condition Analogy: Imagine a funnel-shaped valley. No matter where you are in the funnel, if you look at the slope, it points you toward the bottom. Even if the valley isn't perfectly round (convex), as long as it's "steep enough" everywhere, you are guaranteed to reach the bottom eventually. This shape is common in modern AI, like training neural networks.

The authors prove two main things about hikers in these funnels with "sticky" wind:

The "High-Probability" Guarantee: They prove that with extremely high confidence (like 99.9%), the hiker won't just eventually reach the bottom, but will stay on a predictable path to get there quickly. They give a formula showing exactly how fast the hiker gets closer to the goal, even with the tricky wind.
The "Average" Guarantee: They also calculate the average speed of the hiker over many trials, showing it gets better and better as time goes on.

How Did They Do It? (The Secret Sauce)

The authors used two clever tricks to solve the "sticky wind" problem:

The "Poisson Equation" (The Wind Predictor):
Instead of treating the wind as a random surprise, they used a mathematical tool called the Poisson equation to "predict" the wind's behavior. They essentially calculated the "average drift" caused by the wind and subtracted it out. This turned the "sticky" wind into something that looked more like random noise, which is much easier to handle mathematically.
Probabilistic Induction (The "Good Day" Chain):
Usually, to prove a hiker won't get lost, you need to know they never take a giant wrong step. But in this problem, the hiker could theoretically take a giant step if the wind is bad enough.
The authors used a clever logic trick: "If the hiker has been doing well up to today, then the wind is likely under control today, which means they will likely do well tomorrow."
They created a chain of "Good Days." If the hiker stays on the path today, the math guarantees they are likely to stay on the path tomorrow. By linking these days together, they proved the hiker stays safe for the entire journey, not just for a single step.

Real-World Applications

The paper doesn't just stay in theory; it shows how this works in three real-world scenarios:

Decentralized Learning (The Token Game): Imagine a group of people trying to solve a puzzle together, but they can only talk to their neighbors. A "token" (a piece of paper with the current answer) is passed around a network. The path the token takes is random (Markovian). This paper proves that even with this random passing, the group will find the best answer quickly.
Privacy-Preserving Learning: Sometimes, to protect people's privacy, we shuffle data in specific patterns (like dealing cards from a deck). This shuffling creates correlated noise. The paper shows how to train AI models safely and efficiently even with these privacy rules.
System Identification: Imagine trying to figure out how a car engine works by listening to it while it's running. The engine's state at one moment depends on the moment before. This paper helps engineers estimate the engine's parameters accurately despite the "memory" in the system.

The Bottom Line

This paper is a major upgrade for the "hiker's map." It tells us that even when the environment is messy, correlated, and unpredictable (Markovian noise), and the goal is complex (non-convex but PL-shaped), we can still guarantee that our AI algorithms will find the solution quickly and reliably. It bridges the gap between theoretical math and the messy reality of how data is actually collected in the real world.

1. Problem Formulation

The paper addresses the convergence analysis of the Stochastic Gradient Descent (SGD) algorithm for unconstrained optimization problems of the form $\min_{x \in \mathbb{R}^d} f(x)$ . The specific challenges addressed are:

Non-Convexity: The objective function $f$ is not assumed to be convex but satisfies the Polyak-Łojasiewicz (PL) condition. This condition, defined as $\|\nabla f(x)\|^2 \ge 2\mu (f(x) - f^\star)$ , guarantees global linear convergence for gradient descent and is satisfied by many modern machine learning models (e.g., wide neural networks, linear quadratic regulators).
Markovian Noise: Unlike standard SGD analyses that assume gradient noise is a martingale difference sequence (i.i.d. or conditionally unbiased), this work considers noise with temporal correlations. The gradient estimate $G_k$ is modeled as:
$G_k = g(x_k, Z_k) + M_{k+1}$
where $Z_k$ is a state from a time-homogeneous Markov chain (representing the source of correlated noise, e.g., in decentralized networks or online system identification) and $M_{k+1}$ is a martingale difference noise component.
Unbounded Noise: The framework allows the magnitude of the noise to grow with the function value and the true gradient (Generalized ABC condition), which is crucial for analyzing practical subsampling strategies.

2. Methodology

The authors develop a novel proof technique to derive uniform-in-time high-probability bounds (guarantees that hold for all $k \ge 0$ simultaneously with high probability) rather than just expected bounds. The methodology relies on three key pillars:

Poisson Equation Decomposition:
To handle the Markovian noise component $g(x_k, Z_k) - \nabla f(x_k)$ , the authors utilize the Poisson equation. They define a function $V(x, z)$ such that:
$g(x, z) - \nabla f(x) = V(x, z) - \int V(x, z') p(dz'|z)$
This allows the Markovian noise to be decomposed into a martingale difference sequence ( $\tilde{M}_{k+1}$ ) and a correction term ( $d_k$ ). The martingale part can be handled using standard concentration inequalities, while the correction term is shown to be negligible for the convergence rate.
Probabilistic Induction Argument:
A major hurdle in high-probability analysis is that standard concentration inequalities (like Azuma-Hoeffding) require almost-sure bounds on the noise or the iterates. However, under the PL condition with unbounded noise, such deterministic bounds do not exist.
- The authors introduce a sequence of "good events" $E_k$ , defined as the event where the suboptimality gap $\Delta_k = f(x_k) - f^\star$ decays at the desired rate up to time $k$ .
- They use a probabilistic induction argument: assuming $E_\ell$ holds (the iterates are well-behaved), the noise terms become bounded, allowing the application of Azuma-Hoeffding to show that $E_{\ell+1}$ also holds with high probability.
- This inductive step allows them to bound the probability of the union of "bad events" ( $\cup \bar{E}_k$ ) without requiring a priori almost-sure bounds on the loss function.
Generalized ABC Condition:
The analysis assumes the gradient noise satisfies $\|G_k\|^2 \le A\|\nabla f(x_k)\|^2 + B(f(x_k)-f^\star) + C$ . This generalizes standard bounded variance assumptions, enabling the analysis of scenarios where noise scales with the gradient magnitude (common in subsampling).

3. Key Contributions

First Uniform-in-Time High-Probability Bound: The paper provides the first high-probability bound for SGD under the PL condition with Markovian noise that holds uniformly for all iterations $k \ge 0$ .
Optimal Convergence Rates:
- High-Probability Bound: With probability at least $1-\delta$ , the suboptimality gap decays as:
  $\Delta_k = O\left( \frac{t_{mix}^2 \log(k/\delta)}{\mu^2 k} \right)$
  where $t_{mix}$ is the mixing time of the underlying Markov chain.
- Expected Bound: The expected suboptimality gap decays as:
  $\mathbb{E}[\Delta_k] = O\left( \frac{t_{mix}}{\mu^2 k} \right)$
- The $O(1/k)$ rate matches the optimal rate for strongly convex/PL problems, though the high-probability bound incurs a quadratic dependence on $t_{mix}$ (due to the Poisson decomposition and union bound), whereas the expected bound is linear in $t_{mix}$ .
Handling Unbounded Noise: The framework accommodates noise that grows with the function value, making it applicable to practical settings like privacy-preserving learning and decentralized optimization.
Novel Proof Technique: The probabilistic induction method for establishing uniform bounds without almost-sure assumptions is a significant theoretical contribution applicable to other stochastic approximation settings.

4. Results and Applications

The theoretical framework is validated through three specific applications where Markovian noise naturally arises:

Token-Based Decentralized Linear Regression:
- Scenario: Agents in a network perform local updates. A "token" carrying the iterate performs a random walk (Markov chain) over the network.
- Result: The global objective (Least Squares) satisfies the PL condition. The derived bounds confirm convergence with rates dependent on the mixing time of the token's random walk.
Supervised Learning with Subsampling for Privacy Amplification:
- Scenario: Differentially private SGD using subsampling schemes (e.g., $b$ -min-sep) where data points are sampled based on a state-dependent Markov process to ensure privacy.
- Result: The paper shows that wide neural networks satisfy the PL condition and that the specific subsampling noise fits the Markovian framework, providing convergence guarantees for private learning.
Online System Identification:
- Scenario: Estimating parameters of a linear dynamical system where observations are generated by a Markov process.
- Result: The loss function for system identification satisfies the PL condition under stability assumptions, and the algorithm converges despite the temporal correlation in observations.

5. Significance

This work bridges a critical gap in optimization theory. While SGD is the backbone of modern machine learning, theoretical guarantees have historically lagged behind practice in two areas:

Non-Convexity: Most tight finite-time bounds assumed convexity, whereas the PL condition is the standard for analyzing non-convex deep learning models.
Correlated Noise: Real-world distributed and online systems generate correlated (Markovian) noise, yet most theoretical bounds assume i.i.d. or martingale noise.

By providing high-probability (rather than just expected) guarantees under these realistic conditions, the paper offers stronger theoretical justification for the use of SGD in decentralized, privacy-sensitive, and online learning environments. The introduction of the probabilistic induction technique provides a new tool for researchers to analyze stochastic algorithms where almost-sure bounds are unavailable.