HIGH-PROBABILITY PL-SGD WITH MARKOVIAN NOISE: OPTIMAL MIXING AND TAIL DEPENDENCE

This paper investigates the convergence behavior of Stochastic Gradient Descent (SGD) when gradient samples are generated by an exogenous Markov chain rather than independent and identically distributed (i.i.d.) sources. Specifically, the authors focus on objectives satisfying the Polyak-Łojasiewicz (PL) condition, which is weaker than strong convexity but sufficient for global linear convergence. The primary goal is to determine the optimal dependence of high-probability convergence bounds on the mixing time of the Markov chain, both for light-tailed noise and for heavy-tailed noise where gradients may lack finite variance.

To address the limitations of existing Poisson-equation-based analyses—which often result in suboptimal quadratic dependence on mixing time—the authors introduce a lag-blocking technique. This method decomposes the Markovian sum into an initial window, a centered delayed martingale, and a mixing-bias term. By analyzing these components separately and applying concentration inequalities within residue classes, the authors derive a uniform-in-time high-probability bound. For the heavy-tailed regime, they propose an all-samples clipped block method that robustly handles gradients with only finite $p$-th moments ($p \in (1, 2]$) by averaging clipped transitions within blocks.

1. Optimal Mixing Dependence: The authors prove that for light-tailed PL-SGD, the leading stochastic term scales as $\widetilde{O}(t_{mix}/k)$, which is optimal. They provide a matching lower bound using a quadratic objective driven by a two-state Markov chain, demonstrating that the linear dependence on mixing time cannot be improved.
2. Robust Heavy-Tailed Optimization: For heavy-tailed gradients, the proposed clipped block method achieves a high-probability error of $\widetilde{O}(\sigma_p^2(t_{mix}/T)^{2(p-1)/p})$ given a transition budget $T$. This rate is shown to be optimal via a reduction to mean estimation for a sticky Markov chain.