🤖 machine learning

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

This paper establishes optimal high-probability convergence rates for Polyak-Łojasiewicz stochastic gradient descent under Markovian noise by closing the gap between expectation and high-probability bounds for light-tailed gradients via lag-blocking and extending the framework to heavy-tailed settings using a novel all-samples clipped block method.

Original authors: Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

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 valley (the "optimal solution" to a complex problem). You have a map, but it's a bit broken: every time you ask for directions, the person giving them is slightly confused or biased because they are part of a chain of people passing a message down a line. This is the problem of Markovian noise: your data isn't random and independent; it's connected to the previous piece of data, like a game of "telephone."

This paper tackles how to find the bottom of that valley efficiently when the "noise" (the bad directions) comes from this chain of connected data. The authors focus on a specific type of valley called a PL (Polyak-Łojasiewicz) landscape. Think of this as a valley that might not be perfectly bowl-shaped (convex), but it has a special property: if you are far from the bottom, the ground slopes down steeply enough that you are guaranteed to get closer, even if you take a few wrong turns.

Here is the breakdown of their discovery, using simple analogies:

1. The Problem: The "Telephone Game" of Data

In standard machine learning, we usually assume every piece of data is a fresh, independent coin flip. But in real life (like in robotics, finance, or decentralized networks), data often comes in a sequence where the next piece depends on the last.

The Old Way: Previous research tried to fix the "telephone game" bias by using a mathematical tool called a "Poisson equation." Imagine trying to correct the message by having a super-smart translator rewrite the whole history of the game. This worked, but it was clumsy. It suggested that the error in your final answer would grow with the square of the "mixing time" (how long it takes for the chain to forget its past).
The Gap: Other math suggested the error should only grow linearly with the mixing time. There was a gap between the "square" prediction and the "linear" hope.

2. The Light-Tailed Solution: The "Lag-Blocking" Trick

The authors found a way to close that gap. They proved that for "light-tailed" noise (data that doesn't have extreme, wild outliers), you can achieve the linear error rate.

The Analogy: The Lagging Observer
Imagine you are trying to listen to a noisy conversation in a crowded room.

The Old Method: You try to listen to every word immediately, but because the room is noisy and the conversation is connected, you get confused. You try to mathematically "undo" the noise, but the math gets messy and amplifies the confusion (the square error).
The New Method (Lag-Blocking): Instead of listening to every word as it happens, you decide to listen to a word, then wait for a specific amount of time (the "lag") before listening to the next one. By waiting, you let the "noise" in the room settle down and become independent of the previous word.
The Magic: They split the conversation into different "residue classes" (like listening to every 3rd word, then every 4th word, etc.). Because you waited long enough between these specific words, they act like independent samples. This allows them to prove that the error grows only linearly with how long the chain takes to settle, not quadratically.

The Bottom Line: They proved this is the best possible result. You can't do better than linear. They even built a tiny, simple example (a two-state chain) to prove that if you try to go faster, you will fail.

3. The Heavy-Tailed Solution: The "Clipping" Strategy

Sometimes, the data isn't just noisy; it's wild. Imagine the person giving directions suddenly screams a number that is a million times larger than normal. This is "heavy-tailed" noise. Standard methods break because one crazy outlier ruins the whole average.

The Analogy: The Bouncer and the Group

The Problem: If you have a group of people passing a message, and one person screams a nonsense number, the average message becomes garbage.
The Solution (Clipped Blocks):
1. Hold the Line: Instead of updating your position after every single message, you wait for a whole block of messages (say, 10 messages).
2. The Bouncer (Clipping): Before you average these 10 messages, you put a "bouncer" at the door. If any message is too huge (an outlier), the bouncer cuts it off at a safe limit.
3. The Average: You then average the 10 "tamed" messages.
The Result: This method uses every single message in the block (none are thrown away), but it prevents the wild ones from breaking the math. They proved that with this method, the error depends on the "mixing time" and the "heavy-tail" nature of the data in a very specific, optimal way.

4. Why This Matters

For Light Noise: They fixed a long-standing puzzle. We now know that for standard problems with connected data, the error grows linearly with the "forgetting time" of the data chain. It's not as bad as we thought, and we can't do better than that.
For Wild Noise: They showed how to handle data that has extreme outliers without throwing away data. They proved that the "effective" number of useful samples is reduced by the mixing time, and their method achieves the best possible rate for this scenario.

Summary

The paper is like a guidebook for navigating a foggy, noisy valley where the fog moves in connected waves.

If the fog is mild: You can navigate perfectly by waiting a little bit between steps (Lag-Blocking) to let the fog clear, proving you don't need to overcompensate.
If the fog is wild and stormy: You need to group your steps, cut off the extreme gusts (Clipping), and average them out to stay on the path.

The authors didn't just invent a new way to walk; they proved mathematically that their way is the fastest and most efficient possible given the rules of the game.

Technical Summary: High-Probability PL-SGD with Markovian Noise

Problem Formulation
This paper investigates first-order stochastic optimization methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition, where gradient samples are generated by an exogenous Markov chain rather than independently. The setting involves the recursion $x_{k+1} = x_k - \alpha_k G_k$ , where $G_k = g(x_k, Z_k) + M_{k+1}$ . Here, $(Z_k)$ is a Markov chain with invariant distribution $\pi$ , $g(x, \cdot)$ is an oracle such that $\int g(x, z)\pi(dz) = \nabla f(x)$ , and $M_{k+1}$ is a martingale-difference perturbation. The gradient oracle satisfies a bounded "ABC" growth envelope, $\|G_k\|^2 \leq A\|\nabla f(x_k)\|^2 + B(f(x_k) - f^\star) + C$ , which allows gradient variance to scale with the objective gap and gradient norm, a common feature in overparameterized learning and least-squares problems.

The primary challenge addressed is the temporal dependence of the noise. Unlike independent or martingale noise, Markovian noise introduces a bias that decays only as the chain mixes. Prior work established expectation bounds scaling as $\tilde{O}(t_{\text{mix}}/k)$ but high-probability bounds scaling as $\tilde{O}(t_{\text{mix}}^2/k)$ , leaving a gap regarding whether the quadratic dependence on mixing time $t_{\text{mix}}$ was intrinsic or an artifact of proof techniques (specifically, Poisson-equation decompositions).

Methodology
The paper employs two distinct methodological frameworks for light-tailed and heavy-tailed regimes:

Light-Tailed Regime (Bounded ABC Envelope):
- Lag-Blocking Argument: Instead of using Poisson-equation decompositions (which amplify noise magnitude by a factor of $t_{\text{mix}}$ ), the authors introduce a "lag-blocking" technique. For a target time $k$ , they introduce an analytical delay $m_k$ . The Markovian descent term is decomposed into a delayed part, a mixing-bias part, a replacement error, and an initial window.
- Residue-Class Martingales: By conditioning on the $\sigma$ -algebra $m_k$ steps in the past, the delayed observable becomes a martingale difference with respect to a down-sampled filtration. The sum is split into $m_k$ residue classes. Concentration inequalities (Azuma-Hoeffding) are applied within each class, avoiding the need for independence between classes.
- Control of Bias and Error: The mixing bias is controlled via the total-variation mixing profile, and the replacement error (due to the iterate moving during the delay) is bounded using the Lipschitz continuity of the oracle and the ABC envelope.
Heavy-Tailed Regime (Finite $p$ -th Moment, $p \in (1, 2]$ ):
- All-Samples Clipped Block Method: To handle gradients with only finite $p$ -th moments (where variance may be infinite), the authors propose a block-based algorithm. The iterate is held fixed over a block of $b$ consecutive Markov transitions. Every gradient in the block is clipped coordinate-wise, and the update is performed using the average of these clipped samples.
- No Sample Discarding: Unlike some robust methods that discard samples to ensure independence, this method utilizes every Markov transition within a block. The mixing window enters only through the analysis (lag-blocking) and the choice of the clipping threshold.
- Concentration: The analysis combines stationary clipping bias/variance estimates with a residue-class martingale concentration argument for the consecutive block, similar to the light-tailed case but adapted for heavy tails using Freedman's inequality.

Key Contributions and Results

Optimal High-Probability Bounds for Light-Tailed PL-SGD:
- The paper establishes a uniform-in-time high-probability bound for ordinary one-sample SGD under geometric mixing. The leading stochastic term scales as $\tilde{O}\left(\frac{t_{\text{mix}}}{k + K_0}\right)$ .
- This result closes the gap between the $\tilde{O}(t_{\text{mix}}/k)$ expectation bounds and the previously known $\tilde{O}(t_{\text{mix}}^2/k)$ high-probability bounds, proving that the linear dependence on mixing time is achievable without modifying the SGD algorithm.
Matching Lower Bound:
- A lower bound is proven for a one-dimensional quadratic objective driven by a persistent two-state Markov chain. The result shows that $\mathbb{E}[f(x_k) - f^\star] = \Omega(\sigma^2 t_{\text{mix}}/k)$ and holds with constant probability.
- This confirms that the linear polynomial dependence on $t_{\text{mix}}$ is unavoidable for high-probability guarantees at constant confidence, up to logarithmic factors.
Heavy-Tailed Robust Optimization:
- For gradients with finite stationary $p$ -th moments, the proposed clipped block method achieves a high-probability stochastic error of $\tilde{O}\left(\sigma_p^2 \left(\frac{t_{\text{mix}}}{T}\right)^{2(p-1)/p}\right)$ , where $T$ is the total transition budget.
- The exponent $2(p-1)/p$ and the dependence on the effective sample size ( $T/t_{\text{mix}}$ ) are shown to be optimal via a matching lower bound constructed using a "sticky" Markov chain.

Significance and Claims
The paper claims to tightly characterize the statistical price of Markovian dependence for PL stochastic optimization.

For Light-Tailed Noise: It resolves the open question of whether the quadratic mixing-time dependence in prior high-probability bounds was intrinsic. By proving a matching lower bound and a linear upper bound, it establishes that ordinary SGD achieves the optimal polynomial dependence on mixing time.
For Heavy-Tailed Noise: It extends robust optimization guarantees to the Markovian setting, demonstrating that the effective sample size is reduced by the mixing time and that the finite-moment exponent is unavoidable.
Methodological Novelty: The lag-blocking argument is presented as a superior alternative to Poisson-equation decompositions for high-probability analysis, as it avoids the artificial amplification of noise magnitude while maintaining the simplicity of the standard SGD algorithm.

The work does not claim optimality regarding dimension dependence in the heavy-tailed upper bound, noting that the lower bound construction is one-dimensional. It also notes that the analysis assumes exogenous Markov chains, leaving parameter-dependent kernels (e.g., in actor-critic methods) as an open direction.