High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
June 24, 2026
Abstract
We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time high-probability bounds for ordinary Stochastic Gradient Descent (SGD) under a standard growth envelope scale as \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\), leaving a gap with the \(\widetilde{O}(t_{\mathrm{mix}}/k)\) expectation bounds. We close this gap using a lag-blocking argument to establish a uniform high-probability guarantee with a leading stochastic term of \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching \(\Omega(\sigma^2 t_{\mathrm{mix}}/k)\) lower bound on a quadratic objective driven by a persistent two-state chain.
We then extend this framework to heavy-tailed Markovian gradients satisfying a stationary finite-\(p\)-moment condition, \(p \in (1,2]\). We design an all-samples clipped block method that uses every Markov transition while mitigating Markovian bias. Under a transition budget \(T\), this algorithm achieves a high-probability stochastic error of \(\widetilde{O}(\sigma_p^2(t_{\mathrm{mix}}/T)^{2(p-1)/p})\). We establish a matching lower bound by reducing PL optimization to heavy-tailed mean estimation for a sticky Markov chain. Ultimately, this work tightly characterizes the optimal polynomial dependence on mixing time for light-tailed PL-SGD, and the optimal heavy-tail exponent and effective-sample-size dependence in the robust regime.
Keywords: stochastic gradient descent; Markovian noise; Polyak-Łojasiewicz condition; high-probability bounds; mixing time; heavy-tailed noise; clipped SGD; lower bounds.
1 Introduction↩︎
Stochastic gradient methods are a central tool in stochastic approximation and large-scale optimization. Classical analyses of stochastic approximation and Stochastic Gradient Descent (SGD) typically rely on either independent samples or conditionally unbiased martingale-difference gradient noise [1]–[6]. Under these assumptions, the stochastic error in the descent recursion can be controlled by martingale or concentration arguments, and nonasymptotic convergence guarantees are now well understood in many convex, strongly convex, and nonconvex regimes [7]–[9]. In many modern applications, however, the samples used by the gradient oracle are generated sequentially by a Markov chain rather than independently. This occurs in token-based and random-walk decentralized optimization [10]–[12], Markov Chain Monte Carlo gradient estimation, privacy-preserving subsampling schemes with temporal exclusion rules [13]–[15], online system identification [16], and reinforcement-learning and temporal-difference algorithms [17]–[23]. In such settings the gradient oracle is generally unbiased only after averaging with respect to the invariant distribution of the chain. At a finite time, the conditional law of the Markov state need not be stationary, and the resulting bias must be controlled through the mixing behavior of the chain.
This paper studies this problem for smooth objectives satisfying the Polyak–Łojasiewicz (PL) inequality. The PL condition, introduced in [24] and developed in its modern optimization form in [25], is weaker than strong convexity but still yields global linear convergence for deterministic gradient descent. It is a natural condition in overparameterized learning, least-squares problems, control, and other settings where global convergence can hold without convexity. We consider the Markovian SGD recursion \[\label{eq:sgd-intro} x_{k+1}=x_k-\alpha_kG_k, \qquad G_k=g(x_k,Z_k)+M_{k+1},\tag{1}\] where \((Z_k)_{k\ge 0}\) is an exogenous Markov chain with invariant distribution \(\pi\), the stationary oracle satisfies \[\int g(x,z)\,\pi(dz)=\nabla f(x),\] and \((M_{k+1})_{k\ge0}\) is a martingale-difference perturbation. The oracle is allowed to satisfy a bounded \(A\)-\(B\)-\(C\) growth envelope, called the ABC condition because the constants \(A,B,C\) control the gradient-dependent term, the objective-gap-dependent term, and the additive noise floor: \[\|G_k\|^2 \le A\|\nabla f(x_k)\|^2 + B(f(x_k)-f^\star)+C.\] This condition is used in prior PL-SGD analyses [26]. This growth model is important because a uniform bounded-variance assumption can be too restrictive in PL problems, least-squares models, interpolation regimes, and minibatch sampling.
There is now a substantial literature on first-order methods and stochastic approximation with Markovian sampling. Finite-time analyses of Markovian stochastic gradient methods were developed in convex, strongly convex, and nonconvex settings by [27]–[30]. More general Markovian stochastic-approximation and reinforcement-learning problems are often handled using Poisson-equation decompositions [3]–[5], [31], [32]. Recent work has also studied optimal mixing-time dependence for several first-order methods using randomized batching, multilevel, or variance-reduction ideas [30], [33]. In the PL setting most closely related to ours, Kar, Chandak, Singh, Moulines, Bhatnagar, and Bambos [26] proved the first uniform-in-time high-probability guarantee for SGD with Markovian plus martingale-difference noise under an ABC oracle envelope. Their expectation bound has leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}/k)\), while their uniform high-probability bound has leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\). Thus, before the present work, it was unclear whether high-probability PL-SGD truly requires a quadratic polynomial dependence on the mixing time, or whether the linear dependence suggested by expectation bounds is achievable.
Our first main result shows that the optimal polynomial dependence is linear. For ordinary one-sample SGD under the bounded ABC oracle envelope, we prove a uniform-in-time high-probability bound whose leading stochastic term scales as \[\widetilde{O}\!\left(\frac{t_{\mathrm{mix}}}{k+K_0}\right)\] under geometric mixing, up to logarithmic factors and the usual optimization transient \(K_0\{f(x_0)-f^\star\}/(k+K_0)\). The hidden constants depend on the smoothness, PL, and bounded-ABC envelope constants, including the noise-scale term in [ass:abc]. We also prove a matching lower bound on a one-dimensional quadratic PL objective driven by a persistent two-state Markov chain: \[f(x_k)-f^\star = \Omega\!\left(\frac{\sigma^2t_{\mathrm{mix}}}{k}\right)\] in expectation and with constant probability. Therefore no theorem valid over the same class of instances can improve the polynomial dependence on \(t_{\mathrm{mix}}\) below linear, apart from logarithmic factors.
1.1 Technical challenge and proof novelty↩︎
The main technical obstacle is that the Markovian term in the PL descent recursion is an adaptive Markovian additive functional. In the weighted descent recursion of 2, the stochastic part contains \[\sum_{\ell=0}^{k-1} w_{\ell,k} h(x_\ell,Z_\ell), \qquad h(x,z) = \big\langle \nabla f(x),\,g(x,z)-\nabla f(x)\big\rangle,\] where \(h\) is defined in 6 . For each fixed \(x\), the stationary-gradient identity in [ass:abc] implies \[\int h(x,z)\,\pi(dz)=0.\] However, conditionally on the past, \(Z_\ell\) need not be distributed according to \(\pi\), and \(x_\ell\) is itself generated from the previous Markov states and martingale perturbations. Consequently, \(h(x_\ell,Z_\ell)\) is neither a martingale difference nor a fixed additive functional of the Markov chain. Standard martingale concentration cannot be applied directly, and classical concentration inequalities for fixed Markov-chain observables do not apply in a black-box way.
1.1.0.1 The limitation of the Poisson equation.
The standard mechanism for decoupling this temporal dependence relies on solutions to the Poisson equation. This framework yields a martingale difference sequence by representing the local gradient bias through the solution \(V(x,z)\). For instance, in the recent high-probability PL-SGD analysis by Kar et al. [26], this solution is defined (cf. Lemma 4.1 therein) as the infinite-horizon sum: \[V(x,z) := \mathbb{E}\left[ \sum_{j=0}^\infty \big( g(x,Z_j) - \nabla f(x) \big) \;\Big|\; Z_0 = z \right].\] This allows the Markovian noise to be perfectly decomposed as \(g(x,z) - \nabla f(x) = V(x,z) - \int V(x,z')p(dz'|z)\). While this identity successfully isolates a strict martingale difference sequence, defined as \(\tilde{M}_{\ell+1} := V(x_\ell, Z_{\ell+1}) - \int V(x_\ell, z) p(dz | Z_\ell)\), it achieves this by inadvertently amplifying the magnitude of the stochastic increments.
Because the Markov chain requires \(\mathcal{O}(t_{\mathrm{mix}})\) steps to contract toward the invariant measure \(\pi\), the geometric series defining \(V(x,z)\) forces its magnitude to scale linearly with the mixing time. Kar et al. formalize this dependence in their Lemma C.1, establishing the structural upper bound \(\|V(x,z)\|^2 \le \mathcal{O}(t_{\mathrm{mix}}^2 \cdot \Delta(x))\).
When uniform-in-time concentration inequalities, such as the Azuma-Hoeffding bound, are applied to this derived martingale, the variance proxy relies on the square of the almost-sure increment bounds. By measuring the deviations of a martingale whose increments have inherently bounded ranges of \(\mathcal{O}(t_{\mathrm{mix}})\), the resulting concentration bound accumulates a \(\mathcal{O}(t_{\mathrm{mix}}^2)\) polynomial penalty. This quadratic dependence reflects a limitation of that proof route and leaves a gap relative to the optimal linear \(\mathcal{O}(t_{\mathrm{mix}})\) scaling achievable in expectation bounds.
1.1.0.2 Our approach: lag-blocking and temporal conditioning.
Our proof avoids this loss by changing the conditioning structure instead of changing the observable through a Poisson corrector. For a fixed target time \(k\), choose the analytical delay \(m_k\) from 8 . For \(\ell\ge m_k\), decompose \[h(x_\ell,Z_\ell) = h(x_{\ell-m_k},Z_\ell) + \bigl\{ h(x_\ell,Z_\ell)-h(x_{\ell-m_k},Z_\ell) \bigr\}.\] The first \(m_k\) indices are treated separately as an initial-window term, controlled in 9. For the remaining terms, the delayed iterate \(x_{\ell-m_k}\) is \(\mathcal{F}_{\ell-m_k}\)-measurable, while by 3 the chain has \(m_k\) transitions to move toward stationarity before time \(\ell\). With \[Y_\ell := w_{\ell,k} h(x_{\ell-m_k},Z_\ell), \qquad \overline{Y}_\ell := \mathbb{E}[Y_\ell\mid \mathcal{F}_{\ell-m_k}],\] as in ?? , the Markovian sum is split into an initial window, a centered delayed martingale part, a mixing-bias part, and a replacement part: \[\begin{align} \sum_{\ell=0}^{k-1} w_{\ell,k}h(x_\ell,Z_\ell) &= \sum_{\ell=0}^{m_k-1} w_{\ell,k}h(x_\ell,Z_\ell) + \sum_{\ell=m_k}^{k-1}(Y_\ell-\overline{Y}_\ell) \\ &\quad + \sum_{\ell=m_k}^{k-1}\overline{Y}_\ell + \sum_{\ell=m_k}^{k-1} w_{\ell,k} \bigl\{h(x_\ell,Z_\ell)-h(x_{\ell-m_k},Z_\ell)\bigr\}. \end{align}\]
The centered delayed term is controlled by the residue-class martingale argument in 6. The indices are split modulo \(m_k\). Along a fixed residue class, consecutive delayed terms are separated by exactly \(m_k\) Markov transitions, so after subtracting \(\overline{Y}_\ell\) they form a martingale-difference sequence with respect to a down-sampled filtration. For the actual PL recursion, the relevant object is the weighted sum above, and the residue-class bounds involve the weighted square sum \(\sum_{\ell<k}w_{\ell,k}^2\). Summing over the \(m_k\) residue classes produces a variance proxy of order \[m_k\sum_{\ell<k}w_{\ell,k}^2 \asymp \frac{m_k}{k+K_0},\] up to logarithmic and offset factors; the required weight estimates are collected in 3. Under geometric mixing, \(m_k=\widetilde{O}(t_{\mathrm{mix}})\), which is the source of the leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) in 1. No independence between different residue classes is required: concentration is applied separately within each residue class, and the resulting high-probability bounds are combined by a union bound.
The remaining terms are controlled separately. The mixing bias \(\sum_{\ell=m_k}^{k-1}\overline{Y}_\ell\) is small by the total-variation mixing condition in 3 and the bound in 7. The replacement term is deterministic on the stopped good event: by 4, \[\bigl|h(x_\ell,z)-h(x_{\ell-m_k},z)\bigr| \le c_{\mathrm{lip}} \bigl(1+\sqrt{\Delta(x_\ell)}+\sqrt{\Delta(x_{\ell-m_k})}\bigr) \|x_\ell-x_{\ell-m_k}\|,\] and \[\|x_\ell-x_{\ell-m_k}\| \le \sum_{i=\ell-m_k}^{\ell-1}\alpha_i\|G_i\|.\] The ABC envelope in [ass:abc] controls the gradients on the stopped event, and the resulting replacement bound is stated in 8. These ingredients are combined in 10, and the first-failure argument in Appendix 12 yields the uniform-in-time guarantee of 1. The delay \(m_k\) and residue classes are only analytical devices; the algorithm remains the ordinary one-sample SGD recursion 2 .
We also study a heavy-tailed Markovian regime. In many applications, individual gradient samples may have no deterministic envelope and may not even have finite variance. High-probability guarantees under only finite \(p\)-th moments, \(p\in(1,2]\), therefore require robustification. For independent or martingale-type noise, clipping, normalization, median-of-means, and related robust methods have been used to obtain high-probability guarantees [34]–[40]. Markovian heavy-tailed data are more delicate because dependence reduces the effective sample size and nonstationary initialization creates an additional bias. We address this by holding the iterate fixed over a block, clipping every consecutive Markovian gradient in the block, and averaging all clipped samples. No samples inside the block are discarded; the mixing window enters only through the analysis and the choice of clipping scale. Under geometric mixing and total transition budget \(T\), the resulting high-probability stochastic term has order \[\widetilde{O}\!\left( \sigma_p^2 \left(\frac{t_{\mathrm{mix}}}{T}\right)^{2(p-1)/p} \right),\] up to dimension and logarithmic factors. A sticky-chain lower bound shows that the exponent \(2(p-1)/p\) and the dependence on the Markovian effective sample size cannot be improved, up to logarithmic and dimension factors. The lower bound is one-dimensional, so we do not claim optimality of the dimension dependence in the upper bound.
1.2 Contributions.↩︎
The paper makes the following contributions.
We prove a uniform-in-time high-probability PL-SGD upper bound under a general uniform total-variation mixing profile on a general measurable Markov state space. The result applies to ordinary one-sample SGD and does not require compactness of the state space.
Under geometric mixing, the leading stochastic term in the bounded-ABC regime satisfies \[\widetilde{O}\!\left(\frac{t_{\mathrm{mix}}}{k+K_0}\right),\] with no additional polynomial power of \(t_{\mathrm{mix}}\). This closes the gap between the \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\) high-probability behavior obtained by Poisson-equation-type analyses and the \(\widetilde{O}(t_{\mathrm{mix}}/k)\) behavior suggested by expectation bounds.
We prove a matching lower bound. Even for the quadratic objective \(f(x)=x^2/2\) and a bounded two-state Markovian oracle, SGD satisfies \[\Pr\!\left( f(x_k)-f^\star \ge c\,\frac{\sigma^2t_{\mathrm{mix}}}{k} \right) \ge c_0\] for universal constants \(c,c_0>0\). Thus linear polynomial dependence on the mixing time is unavoidable at constant confidence.
We extend the lag-blocking viewpoint to finite-\(p\) heavy-tailed Markovian gradients. The proposed all-samples clipped block method uses every Markov transition in each block and achieves the transition-budget rate \[\widetilde{O}\!\left( \sigma_p^2 \left(\frac{t_{\mathrm{mix}}}{T}\right)^{2(p-1)/p} \right)\] under geometric mixing, up to logarithmic and dimension factors.
We prove a matching heavy-tailed lower bound by reducing PL optimization to mean estimation for a sticky Markov chain. This shows that both the Markovian effective-sample-size dependence and the finite-moment exponent \(2(p-1)/p\) are unavoidable up to logarithmic and dimension factors; the result does not claim optimality of the dimension dependence.
2 Related work↩︎
We summarize the closest comparisons in 1. The table separates objective or problem-class assumptions from oracle/noise assumptions: PL is an objective-geometry condition, whereas the ABC envelope is an oracle growth condition. The main comparison is with high-probability PL-SGD under Markovian sampling; broader background on stochastic approximation, Poisson-equation methods, Markov-chain concentration, decentralized and MCMC sampling, and robust heavy-tailed optimization is deferred to Appendix 9.
2.2pt
2.0.0.1 Closest PL-SGD comparison.
The closest prior result is Kar et al. [26], which studies ordinary one-sample SGD for smooth PL objectives with Markovian plus martingale-difference noise under an ABC oracle envelope. Their expectation bound has leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}/k)\), while their uniform high-probability bound has leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\). Thus, before the present work, it was unclear whether the quadratic high-probability dependence on the mixing time was intrinsic or an artifact of the proof technique. Our light-tailed theorem closes this gap by proving a uniform high-probability bound with leading stochastic term \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) for the same ordinary SGD recursion, under a general uniform total-variation mixing profile. The matching two-state lower bound shows that the order \(\Omega(\sigma^2t_{\mathrm{mix}}/k)\) is unavoidable at constant confidence, up to logarithmic factors.
2.0.0.2 Other Markovian first-order methods.
Finite-time analyses of stochastic gradient methods with Markovian samples were developed in convex, strongly convex, and nonconvex settings by Sun, Sun, and Yin [27], Doan et al. [28], and Doan [29]. Even [30] studies general Markovian sampling schemes, including MC-SGD and the variance-reduced MC-SAG method, and proves lower bounds involving hitting-time quantities. Beznosikov et al. [33] obtain linear mixing-time dependence for several first-order methods using randomized batching and multilevel gradient estimators, including nonconvex, strongly convex, and variational-inequality settings. These works show that favorable mixing dependence is possible in several regimes, but they do not resolve the high-probability behavior of ordinary one-sample PL-SGD under an ABC oracle envelope.
2.0.0.3 Heavy-tailed Markovian regimes.
The heavy-tailed part of the paper is related to robust stochastic optimization and Markovian stochastic approximation under finite-moment noise. Agrawal, Maguluri, and Zubeldia [41] study concentration and tail behavior for general stochastic approximation with finite-state Markovian components and heavy-tailed martingale perturbations. Our robust result is different in two ways: it is a PL optimization theorem, and the Markovian gradient component itself is allowed to have only a finite stationary \(p\)-th moment, \(p\in(1,2]\). Using clipped Markovian blocks and a total transition budget \(T\), we obtain the high-probability rate \[\widetilde{O}\!\left( \sigma_p^2\left(\frac{t_{\mathrm{mix}}}{T}\right)^{2(p-1)/p} \right),\] and prove a matching sticky-chain lower bound for the Markovian effective-sample-size dependence and the finite-moment exponent, up to logarithmic and dimension factors.
2.0.0.4 Scope of the comparison.
The rows in 1 are not directly interchangeable. Some works study convex or nonconvex optimization rather than PL objectives; some use modified estimators or variance-reduced methods rather than ordinary SGD; and some prove lower bounds for hitting-time or oracle-complexity models rather than PL last-iterate optimization. The contribution of the present paper is to identify the optimal polynomial mixing-time dependence for ordinary high-probability PL-SGD in the bounded-ABC regime, and the optimal finite-moment exponent and Markovian effective-sample-size dependence for the clipped-block heavy-tailed regime.
3 Problem formulation and assumptions↩︎
Let \(f:\mathbb{R}^d\to\mathbb{R}\) be differentiable and lower bounded. Write \[f^\star:=\inf_{x\in\mathbb{R}^d}f(x), \qquad \Delta(x):=f(x)-f^\star, \qquad \Delta_k:=\Delta(x_k).\] The algorithm is \[\label{eq:sgd} x_{k+1}=x_k-\alpha_kG_k, \qquad G_k=g(x_k,Z_k)+M_{k+1}.\tag{2}\] The initial point \(x_0\) is deterministic and \(\Delta_0<\infty\). If \(x_0\) is random, the same statements hold conditionally on \(\mathcal{F}_0\) on every realization with finite \(\Delta_0\).
Assumption 1 (Objective). The function \(f\) is \(L\)-smooth and satisfies the \(\mu\)-PL inequality: \[\label{eq:pl} \|\nabla f(x)\|^2\ge 2\mu\Delta(x), \qquad x\in\mathbb{R}^d.\qquad{(1)}\] Since \(f\) is lower bounded and \(L\)-smooth, the gradient upper bound \[\label{eq:grad-upper} \|\nabla f(x)\|^2\le 2L\Delta(x)\qquad{(2)}\] holds for all \(x\).
Remark 1 (Role, commonness, and scope of the objective assumption). Smoothness and PL geometry are standard in the nonconvex-optimization and stochastic-gradient literature. The PL inequality goes back to Polyak [24], and its modern optimization role, together with its relation to error bounds, quadratic growth, and related conditions, is surveyed by Karimi, Nutini, and Schmidt [25]. The same smoothness-plus-PL framework is used in stochastic-gradient analyses with growth-type noise conditions [8], [9] and in the closest prior Markovian PL-SGD work [26]. Thus 1 is not a special assumption introduced for our lag-blocking argument; it is the standard geometry under which last-iterate objective convergence is usually proved beyond convexity.
The assumption also holds for many functions of interest. Every differentiable strongly convex smooth function is PL, but PL is strictly weaker than strong convexity. It also holds for full-rank least-squares and more generally for quadratic objectives with a positive curvature direction on the relevant range; it appears in several overparameterized models and neural-network loss landscapes [42]; and it is used in control examples such as linear-quadratic regulator objectives [43]. In applications where the property is only valid on a sublevel set, the localized version in 4 allows the same proof to be run with local constants.
In the proof, 1 is used in two distinct ways. Smoothness gives the one-step descent inequality that leads to the weighted recursion in 2. The PL inequality ?? converts gradient decrease into objective decrease, producing the contraction factors in the weights 5 . The smoothness upper bound ?? , proved in 1, is repeatedly used to express gradient magnitudes in terms of the suboptimality \(\Delta(x)\). The same geometry is used in the heavy-tailed inexact-gradient argument, 21. Thus 1 is the mechanism that turns stochastic gradient control into last-iterate objective control.
Assumption 2 (Oracle, martingale noise, and ABC envelope). Let \[\mathcal{F}_k:=\sigma(x_0,Z_0,\ldots,Z_k,M_1,\ldots,M_k).\] The sequence \((M_{k+1})_{k\ge0}\) is a martingale difference sequence with respect to \((\mathcal{F}_k)\): \[\mathbb{E}[M_{k+1}\mid\mathcal{F}_k]=0.\] For every \(x\in\mathbb{R}^d\), \[\label{eq:stationary-gradient} \int g(x,z)\,\pi(dz)=\nabla f(x).\qquad{(3)}\] There are constants \(A,B,C\ge0\) such that almost surely, for every \(k\), \[\label{eq:abc-G} \|G_k\|^2\le A\|\nabla f(x_k)\|^2+B\Delta_k+C,\qquad{(4)}\] and, for every \(x\in\mathbb{R}^d\) and \(z\in\mathsf Z\), \[\label{eq:abc-g} \|g(x,z)\|^2\le A\|\nabla f(x)\|^2+B\Delta(x)+C.\qquad{(5)}\] Moreover \(g(\cdot,z)\) is \(L_g\)-Lipschitz for every \(z\): \[\label{eq:g-lip} \|g(x,z)-g(y,z)\|\le L_g\|x-y\|.\qquad{(6)}\]
Remark 2 (Scope, examples, and role of the ABC envelope). [ass:abc] is a pathwise ABC or weak-growth type envelope. Conditions of this form are common in modern SGD analyses under the names ABC, weak growth, strong growth, expected smoothness, or growth-noise conditions; see, for example, [8], [9], [26], [44]. The point of the assumption is to allow the stochastic-gradient magnitude to grow with the local scale of the problem, rather than requiring a uniform variance or uniform bounded-gradient bound over all \(x\). This is important for least squares, interpolation, minibatch gradients, and state-dependent oracle models, where the sample gradient is typically small near a solution but can grow away from it.
The envelope contains several familiar bounded-oracle models as special cases. Uniformly bounded stochastic gradients correspond to \(A=B=0\). Additive bounded noise, \(G_k=\nabla f(x_k)+\xi_k\) with \(\|\xi_k\|\le\sigma\), gives \(\|G_k\|^2\le 2\|\nabla f(x_k)\|^2+2\sigma^2\). Relative-noise or strong-growth conditions correspond to the case in which the stochastic-gradient magnitude is proportional to \(\|\nabla f(x_k)\|\), possibly with an additive constant. In finite-sum and minibatch problems, such bounds hold whenever the component gradients are controlled by the objective residual or by the full gradient on the sublevel set visited by the algorithm; in least-squares and generalized-linear models this is typically verified from bounded features or from a local sublevel-set bound. The additional \(B\Delta_k\) term is natural under PL geometry because ?? allows \(\|\nabla f(x_k)\|^2\) and \(\Delta_k\) to be controlled together. When the envelope holds only locally, 4 gives the corresponding localized statement.
The pathwise form is needed for high-probability control. In 5, it gives deterministic martingale increment bounds for the martingale-difference perturbation. In 4, ?? gives a deterministic envelope for the Markovian descent observable \(h\). The Lipschitz condition ?? is used in 8 to control the error made by replacing \(x_\ell\) with the delayed iterate \(x_{\ell-m}\). Finite moment assumptions that do not imply such deterministic envelopes are treated separately in 5 through clipping and blockwise averaging.
Assumption 3 (Exogenous Markov chain and uniform mixing profile). The process \((Z_k)_{k\ge0}\) is a time-homogeneous Markov chain on a measurable space \((\mathsf Z,\mathcal{Z})\) with transition kernel \(P\) and invariant law \(\pi\). It is Markov with respect to the full filtration: \[\label{eq:full-markov} \mathbb{P}(Z_{k+1}\in B\mid\mathcal{F}_k)=P(Z_k,B), \qquad B\in\mathcal{Z}.\qquad{(7)}\] Define the uniform total-variation mixing profile \[\label{eq:mixing-profile} \varepsilon(m):=\sup_{z\in\mathsf Z}\|P^m(z,\cdot)-\pi\|_{\mathrm{TV}}, \qquad m\ge0.\qquad{(8)}\] We assume \(\varepsilon(m)\to0\) as \(m\to\infty\). Whenever a single geometric mixing time is used, we say that \(t_{\mathrm{mix}}\ge1\) is valid if \[\label{eq:mixing-def} \varepsilon(m)\le 2^{-\lfloor m/t_{\mathrm{mix}}\rfloor}, \qquad m\ge0.\qquad{(9)}\]
Remark 3 (Why exogeneity and uniform mixing are assumed). Uniform total-variation mixing is a standard assumption in finite-time analyses and concentration results for Markovian stochastic algorithms. It is used, either directly or through closely related mixing-time parameters, in Markovian-gradient and first-order analyses such as [26]–[30], [33] and in concentration inequalities for uniformly ergodic Markov chains [45], [46]. The assumption holds for every finite-state irreducible aperiodic chain, and more generally for uniformly ergodic chains satisfying a Doeblin or minorization condition. Thus it covers many fixed-sampling mechanisms used in applications, such as finite-state random walks with laziness, token chains on finite connected networks, fixed MCMC samplers after a uniform-ergodicity verification, and privacy-subsampling chains with a fixed transition rule. The theorem is stated in terms of the whole profile \(\varepsilon(m)\) so that the analysis can also use nonasymptotic mixing estimates when a single closed-form \(t_{\mathrm{mix}}\) is not the most convenient description.
3 has two proof roles. First, the full-filtration Markov property ?? makes the chain exogenous: the transition kernel of \(Z_k\) does not depend on the current iterate. This is essential for the lag argument, because once \(x_{\ell-m}\) is \(\mathcal{F}_{\ell-m}\)-measurable, the conditional law of \(Z_\ell\) is exactly \(P^m(Z_{\ell-m},\cdot)\). Second, the uniform total-variation profile ?? , together with [eq:tv-dual], controls the conditional bias of the delayed observable. This is the bound used in 7.
The main theorem is stated for the full profile \(\varepsilon(m)\), not for a single scalar mixing time. The geometric form ?? is used only in 1, where 12 verifies that the analysis windows are admissible with \(m_k=\widetilde{O}(t_{\mathrm{mix}})\). Parameter-dependent Markov kernels, such as adaptive MCMC or policy-dependent reinforcement-learning chains, would require additional control of the change in the transition kernel or invariant law and are outside the present exogenous model.
We use the stepsize \[\label{eq:stepsize} \alpha_k=\frac{a}{k+K_0}, \qquad a\ge\frac{2}{\mu}.\tag{3}\] Set \[\label{eq:basic-K} K_0\ge K_{\mathrm{base}} :=\max\left\{1,\mu a,\frac{aL}{2}\left(2A+\frac{B}{\mu}\right)\right\}.\tag{4}\] For \(0\le \ell\le k-1\), define \[\label{eq:weights} \zeta_{\ell+1,k-1}:=\prod_{j=\ell+1}^{k-1}(1-\mu\alpha_j), \qquad w_{\ell,k}:=\alpha_\ell\zeta_{\ell+1,k-1},\tag{5}\] with empty products equal to one. We also define \[\label{eq:xi-h} \xi(x,z):=g(x,z)-\nabla f(x), \qquad h(x,z):=\left\langle \nabla f(x),\xi(x,z)\right\rangle.\tag{6}\] Then \(\int h(x,z)\pi(dz)=0\) for each fixed \(x\).
3.0.0.1 Notation.
For probability measures \(\nu\) and \(\nu'\) on \((\mathsf Z,\mathcal{Z})\), we use the probability total-variation distance \[\|\nu-\nu'\|_{\mathrm{TV}}:=\sup_{A\in\mathcal{Z}}|\nu(A)-\nu'(A)| =\frac{1}{2} |\nu-\nu'|(\mathsf Z).\] Thus the largest possible distance between two probability laws is one. With this convention, for every bounded measurable scalar function \(\varphi\), \[\label{pehxkimq} \left|\int \varphi\,d(\nu-\nu')\right| \le 2\|\varphi\|_\infty\|\nu-\nu'\|_{\mathrm{TV}}.\tag{7}\] All norms on vectors are Euclidean.
4 Sharp upper and lower bounds↩︎
4.1 Upper bound for a general mixing profile↩︎
The main theorem is stated for a general mixing profile. Fix \(\delta\in(0,e^{-1})\) and define, for \(k\ge1\), \[\label{eq:delay-def} N_k:=k+K_0, \qquad \widehat m_k:=\min\left\{m\in\mathbb{N}: m\ge1,\;\varepsilon(m)\le \frac{\delta}{32N_k^4}\right\}, \qquad m_k:=\min\{k,\widehat m_k\}.\tag{8}\] The minimum is finite by Assumption 3. The profile \(\varepsilon(m)\) is nonincreasing in integer \(m\): indeed, Markov kernels contract total variation and \(P^{m+1}(z,\cdot)-\pi=(P^m(z,\cdot)-\pi)P\). Since the threshold \(\delta/(32N_k^4)\) is nonincreasing in \(k\), the sequences \(\widehat m_k\) and \(m_k\) are nondecreasing. Define \[\label{eq:u-theta} u_k:=\log\left(\frac{16(m_k+1)(k+1)^2}{\delta}\right), \qquad q_k:=1+\frac{m_k}{K_0}, \qquad \Theta_k:=m_ku_kq_k^2.\tag{9}\] Consequently \(u_k,q_k,\) and \(\Theta_k\) are also nondecreasing in \(k\).
Theorem 1 (Mixing-profile high-probability upper bound). Suppose Assumptions 1–3 hold and let \((x_k)\) be generated by 2 with stepsizes 3 . There exist constants \[\rho_0\in(0,1),\qquad K_D<\infty,\qquad C_\star<\infty,\] depending only on \(a,\mu,L,L_g,A,B,C,\Delta_0\), such that the following holds. Assume \(K_0\ge K_{\mathrm{base}}\vee K_D\) and that the analysis windows satisfy, for every \(k\ge1\), \[\begin{align} \frac{\Theta_k}{N_k}&\le \rho_0,\label{eq:admissible-1}\\ \frac{m_k}{N_k}\left(1+\log\frac{N_k}{K_0}+\frac{m_k}{K_0}\right)&\le \rho_0.\label{eq:admissible-2} \end{align}\] {#eq: sublabel=eq:eq:admissible-1,eq:eq:admissible-2} Then, with probability at least \(1-\delta\), for all \(k\ge1\), \[\label{eq:profile-bound} \Delta_k\le \frac{2K_0\Delta_0+C_\star(1+\Theta_k)}{k+K_0}.\qquad{(10)}\]
The proof is given in Appendix 12.
Remark 4 (Constants and admissible windows). The constant \(C_\star\) in 1 is problem-dependent: it may depend on the ABC constants \(A,B,C\), the geometry constants \(L,\mu,L_g\), the stepsize parameter \(a\), and the initial suboptimality \(\Delta_0\). Thus rate statements such as \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) are always meant after fixing these problem constants; in particular, the noise-size parameter \(C\) in [ass:abc] is part of the hidden constant. This is consistent with the lower-bound normalization in 2, where the corresponding envelope scale is proportional to \(\sigma^2\).
The theorem is also an admissible-window result for a general mixing profile. It becomes a closed form rate only after the window conditions ?? –?? are verified. 1 performs this verification for geometric mixing.
Corollary 1 (Geometric mixing rate). Suppose, in addition to the assumptions of 1, that the chain has a valid geometric mixing time \(t_{\mathrm{mix}}\) in the sense of ?? . There exists \(K_{\mathrm{geo}}<\infty\), depending only on \(a,\mu,L,L_g,A,B,C,\Delta_0\), such that if \[\label{eq:K-geometric} K_0\ge K_{\mathrm{geo}}\,t_{\mathrm{mix}}\left(1+\log\frac{et_{\mathrm{mix}}}{\delta}\right)^3,\qquad{(11)}\] then ?? holds with probability at least \(1-\delta\). More explicitly, for every \(k\ge1\), \[\begin{align} m_k&\le \left\lceil t_{\mathrm{mix}}\left(1+\log_2\left(\frac{32(k+K_0)^4}{\delta}\right)\right)\right\rceil \le 1+t_{\mathrm{mix}}\left(1+\log_2\left(\frac{32(k+K_0)^4}{\delta}\right)\right),\label{eq:mk-geometric-explicit}\\ \Theta_k &\le M_k\,\log\left(\frac{16(k+1)^2(M_k+1)}{\delta}\right) \left(1+\frac{M_k}{K_0}\right)^2,\label{eq:theta-geometric-explicit}\\ M_k&:=1+t_{\mathrm{mix}}\left(1+\log_2\left(\frac{32(k+K_0)^4}{\delta}\right)\right).\notag \end{align}\] {#eq: sublabel=eq:eq:mk-geometric-explicit,eq:eq:theta-geometric-explicit} Consequently, ?? gives a leading stochastic contribution of order \[\widetilde{O}\!\left(\frac{t_{\mathrm{mix}}}{k+K_0}\right),\] where the hidden factors are logarithmic in \(k\), \(1/\delta\), and \(t_{\mathrm{mix}}\), and the prefactor is the problem-dependent constant described in 4; there is no additional polynomial power of \(t_{\mathrm{mix}}\).
The proof is given in Appendix 13.
Remark 5 (Comparison with Poisson-equation bounds). Poisson-equation high-probability analyses typically control a derived martingale whose increment range scales with the mixing time. Applying worst-case martingale range bounds to such increments leads to a leading stochastic term of order \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\). The lag-blocking analysis instead applies concentration to delayed residue-class sums whose increments are bounded by the original oracle envelope from [ass:abc]. The number of residue classes is \(m_k\), and under ?? , 12 gives \(m_k=\widetilde{O}(t_{\mathrm{mix}})\). This yields the order \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) in 1.
4.2 A matching lower bound↩︎
The upper bound has the optimal polynomial dependence on mixing time. Let \(\mathsf Z=\{-1,+1\}\) and fix \(\varepsilon\in(0,1/8]\). Consider the persistent two-state chain \[\label{eq:two-state-kernel} P= \begin{pmatrix} 1-\varepsilon & \varepsilon\\ \varepsilon & 1-\varepsilon \end{pmatrix},\tag{10}\] whose invariant law is uniform. Let \[\label{eq:lower-instance} f(x)=\frac{x^2}{2}, \qquad g(x,z)=x+\sigma z, \qquad \sigma>0.\tag{11}\] With \(M_{k+1}\equiv0\), SGD becomes \[\label{eq:lower-sgd-recursion} x_{n+1}=\left(1-\frac{a}{n+K}\right)x_n -\frac{a\sigma}{n+K}Z_n, \qquad x_0=0.\tag{12}\] The chain is started in stationarity.
Theorem 2 (Linear mixing-time lower bound). Fix \(a\ge2\). There are positive constants \(c_a\) and \(c_0\) depending at most on \(a\) such that the following holds. Let \(K\ge \max\{4a,4a^2\}\) and let \(\varepsilon\in(0,1/8]\). For the instance 10 12 , if \[\label{eq:k-condition-main} k\ge \max\left\{8K,\frac{16}{\varepsilon},16a^2\right\},\qquad{(12)}\] then \[\label{eq:expectation-lower-main} \mathbb{E}\left[f(x_k)-f^\star\right] \ge c_a\,\frac{\sigma^2}{\varepsilon k},\qquad{(13)}\] and \[\label{eq:probability-lower-main} \mathbb{P}\!\left( f(x_k)-f^\star\ge c_a\,\frac{\sigma^2}{\varepsilon k} \right) \ge c_0.\qquad{(14)}\] One may take \(c_0=1/96\) and \[\label{eq:c-a-explicit} c_a=\frac{a^2 e^{-2}}{2^{14}\,3^{2a+2}}.\qquad{(15)}\] The mixing time of the chain is \(\Theta(1/\varepsilon)\). Consequently, for another constant \(c'_a>0\) depending only on \(a\), \[\label{eq:tmix-lower-main} \mathbb{E}\left[f(x_k)-f^\star\right] \ge c'_a\,\frac{\sigma^2t_{\mathrm{mix}}}{k}, \qquad \mathbb{P}\!\left(f(x_k)-f^\star\ge c'_a\,\frac{\sigma^2t_{\mathrm{mix}}}{k}\right) \ge c_0.\qquad{(16)}\]
The proof is given in Appendix 15; the final moment-to-probability argument is in Appendix 15.4.
Corollary 2 (No sublinear order in \(t_{\mathrm{mix}}/k\) at constant confidence). Any high-probability theorem that is valid for all instances satisfying [ass:objective,ass:abc,ass:mixing] cannot have leading stochastic order \(o(t_{\mathrm{mix}}/k)\) at constant confidence. More precisely, if the failure probability is smaller than the constant \(c_0\) in 2, then the right-hand side of a uniform upper bound cannot be \(o(t_{\mathrm{mix}}/k)\) on the family 10 –12 .
Proof. This follows directly from 2. The lower-bound family 10 –12 satisfies [ass:objective,ass:abc,ass:mixing]. On this family, 2 shows that, with probability at least \(c_0\), \[f(x_k)-f^\star \ge c'_a\frac{\sigma^2t_{\mathrm{mix}}}{k}.\] Therefore any uniform high-probability upper bound over the same class, with failure probability strictly smaller than \(c_0\), cannot have a leading stochastic term \(o(t_{\mathrm{mix}}/k)\), since such a bound would eventually be smaller than the lower-bound threshold on this family, contradicting 2. ◻
5 Heavy-tailed Markovian gradients↩︎
The bounded-ABC theorem is sharp for light-tailed or almost-sure controlled gradients. We now treat a genuinely heavy-tailed regime in which the Markovian gradient component has only a finite \(p\)th moment under the invariant law. Ordinary one-sample SGD is not stable enough to provide logarithmic-confidence high-probability guarantees under this assumption alone. The robust method below therefore uses clipping and blockwise averaging. During each block the iterate is held fixed, the next consecutive Markovian gradients are all used, and the update is made with the average of the clipped samples. The mixing window is a design and proof parameter used to choose the clipping scale and to analyze the consecutive block; it is not a spacing rule and no observations inside the block are discarded.
Remark 6 (Why clipping is used). The clipping step in 1 is not intended to improve the constant-confidence exponent in the number of samples. Even for independent samples, ordinary averaging can have the same \(T^{-2(p-1)/p}\) scaling at constant probability under a finite \(p\)-moment condition. The obstruction is the dependence on the confidence parameter: under only finite \(p\)-moments, a single rare outlier can dominate an unclipped average, and worst-case high-probability bounds for ordinary averaging or unclipped SGD generally have polynomial rather than logarithmic dependence on \(1/\delta\). Robust mean-estimation and heavy-tailed stochastic optimization methods therefore use clipping, truncation, normalization, median-of-means, or related transformations to obtain logarithmic-confidence guarantees [34]–[40], [47]–[49]. Our contribution in this section is the Markovian extension: clipped finite-\(p\) high-probability control for consecutive Markovian samples while using every transition in each block, together with a sticky-chain lower bound for the Markovian effective sample size.
For \(\lambda>0\), define the coordinatewise clipping map \[\label{eq:coord-clip-def} [\mathsf T_\lambda(v)]_j:=\max\{-\lambda,\min\{v_j,\lambda\}\}, \qquad j=1,\ldots,d.\tag{13}\] The heavy-tailed oracle is written as \[\label{eq:heavy-oracle} Y(x,z,u)={\mathcal{G}}(x,z,u),\tag{14}\] where \(u\) denotes auxiliary randomness conditionally independent of the past given the current iterate and Markov state.
Assumption 4 (Stationary finite-moment Markovian oracle). Fix \(p\in(1,2]\). At each oracle call, the auxiliary variable \(U\) is sampled conditionally independently of the past given the queried point and current Markov state, with the same conditional law used in ?? and ?? . The oracle satisfies the stationary unbiasedness condition \[\label{eq:heavy-unbiased} \int \mathbb{E}_U[{\mathcal{G}}(x,z,U)]\,\pi(dz)=\nabla f(x), \qquad x\in\mathbb{R}^d.\qquad{(17)}\] Let \(\eta(x,z,u):={\mathcal{G}}(x,z,u)-\nabla f(x)\) and \[\label{eq:Rp-def} R_p(x):=1+\|\nabla f(x)\|+\sqrt{\Delta(x)}.\qquad{(18)}\] There is a scale \(\sigma_p\ge1\) such that, for every \(x\in\mathbb{R}^d\), \[\label{eq:stationary-p-moment} \int \mathbb{E}_U\left[\|\eta(x,z,U)\|^p\right] \pi(dz) \le \sigma_p^p R_p(x)^p.\qquad{(19)}\]
Remark 7 (Why the heavy-tailed moment condition is stationary). Finite-moment assumptions are standard in robust stochastic optimization and robust mean estimation under heavy-tailed data; see, for example, [34]–[40]. Markovian stochastic approximation with heavy-tailed perturbations has also been studied in [41]. 4 is the Markovian optimization analogue of these conditions: it allows the raw oracle to have no deterministic envelope and, when \(p<2\), no finite variance.
The moment bound is imposed under the invariant law rather than uniformly over all Markov states. This is natural for Markovian data because rare states may produce very large gradients, but their contribution is controlled by their stationary probability under \(\pi\). Such a condition holds whenever the stationary distribution has a finite \(p\)-moment for the gradient noise scale. This includes bounded-gradient models, sub-Weibull or polynomial-tail models with finite \(p\)-moment, mixtures with rare outliers, and Markov chains whose high-gradient states have sufficiently small stationary mass. In particular, the bounded ABC model in [ass:abc] implies a finite-\(p\) stationary moment bound for every \(p\in(1,2]\), after adjusting the scale \(\sigma_p\); the heavy-tailed theorem is nevertheless complementary because it analyzes a clipped block method rather than ordinary one-sample SGD.
Nonstationary initialization is handled by clipping and lag-blocking. The clipping bias and stationary second-moment estimates are isolated in 19; the Markovian consecutive-block concentration is proved in 20. The first \(m\) observations of each block are controlled directly by clipping, while the remaining observations are centered relative to the sigma-field one lag in the past. Thus every Markov transition in a block is used by the algorithm; the mixing window enters only through the proof and the clipping scale.
Definition 1 (All-samples clipped block method). Fix integers \(N,b\ge1\) and a clipping level \(\lambda\). Set \(\tau_0=0\). At outer iteration \(r=0,\ldots,N-1\), hold \(x_r\) fixed and observe the next \(b\) consecutive Markovian gradients. Specifically, for \(i=1,\ldots,b\), after one Markov transition from time \(\tau_r+i-1\) to \(\tau_r+i\), draw \(U_{r,i}\) and observe \[Y_{r,i}:={\mathcal{G}}(x_r,Z_{\tau_r+i},U_{r,i}).\] After the block is collected, set \(\tau_{r+1}:=\tau_r+b\) and update \[\label{eq:robust-batch-update} \widehat g_r:=\frac{1}{b}\sum_{i=1}^b\mathsf T_\lambda(Y_{r,i}), \qquad x_{r+1}=x_r-\frac{1}{4L}\widehat g_r .\qquad{(20)}\] Thus each Markov transition in the block contributes exactly one clipped gradient sample to the update.
Let \[\label{eq:theta-p-def} \vartheta_p:=\frac{2(p-1)}{p}.\tag{15}\] For a radius \(\mathcal{R}\ge1\), define \[\label{eq:BR-def} B_{\mathcal{R}}:=1+\sqrt{2L\mathcal{R}}+\sqrt{\mathcal{R}}.\tag{16}\] For confidence level \(\delta\in(0,e^{-1})\) and an integer analysis lag \(m\in\{1,\ldots,b\}\), set \[\label{eq:heavy-u-def} u_{\rm ht}:=\log\left(\frac{64dN(m+1)}{\delta}\right), \qquad s_{\rm ht}:=\frac{m u_{\rm ht}}{b},\tag{17}\] and choose \[\label{eq:heavy-fixed-lambda} \lambda:=c_{\lambda,p}\,\sigma_pB_{\mathcal{R}}\,s_{\rm ht}^{-1/p},\tag{18}\] where \(c_{\lambda,p}\) is a sufficiently large numerical constant depending only on \(p\). The following theorem is stated with explicit admissibility conditions. They require the block to be long enough for the clipping bias, sampling fluctuation, and residual mixing bias to be below the radius used in the induction.
Theorem 3 (Heavy-tailed robust Markovian PL optimization). Suppose Assumptions 1, 3, and 4 hold. Let \((x_r)_{r=0}^N\) be generated by 1 with clipping level 18 . Let \(\mathcal{R}\ge 4\Delta_0+4\) and assume \[\begin{align} \varepsilon(m)&\le \frac{\delta}{64dNb},\label{eq:heavy-mixing-condition}\\ \lambda&\ge 2\sqrt{2L\mathcal{R}},\label{eq:heavy-lambda-condition}\\ \frac{c_p d\sigma_p^2B_{\mathcal{R}}^2}{\mu} s_{\rm ht}^{\vartheta_p}&\le \frac{\mathcal{R}}{4},\label{eq:heavy-batch-size-condition} \end{align}\] {#eq: sublabel=eq:eq:heavy-mixing-condition,eq:eq:heavy-lambda-condition,eq:eq:heavy-batch-size-condition} where \(c_p\) is a numerical constant depending only on \(p\). Then, with probability at least \(1-\delta\), \[\label{eq:heavy-profile-bound} \Delta(x_N) \le \left(1-\frac{\mu}{16L}\right)^N\Delta_0 +\frac{c_p d\sigma_p^2B_{\mathcal{R}}^2}{\mu} s_{\rm ht}^{\vartheta_p}.\qquad{(21)}\] Moreover, on the same event all outer iterates satisfy \(\Delta(x_r)\le\mathcal{R}\) for \(0\le r\le N\).
The proof is given in Appendix 16.2.
Corollary 3 (Geometric mixing and total transition budget). Suppose, in addition, that ?? holds with a valid mixing time \(t_{\mathrm{mix}}\). For a total Markov-transition budget \(T\), choose \[\label{eq:heavy-geo-choices} N=\left\lceil \frac{32L}{\mu}\log(eT)\right\rceil, \qquad b=\left\lfloor\frac{T}{N}\right\rfloor, \qquad m=\left\lceil t_{\mathrm{mix}}\left(1+\log_2\left(\frac{64dNT}{\delta}\right)\right)\right\rceil .\qquad{(22)}\] If \(1\le m\le b\) and the admissibility conditions in 3 hold for a radius \(\mathcal{R}\ge4\Delta_0+4\), then the robust method uses at most \(T\) Markov transitions and, with probability at least \(1-\delta\), \[\label{eq:heavy-geo-rate} \Delta(x_N) \le \widetilde{O}\left(\frac{\Delta_0}{T}\right) +\widetilde{O}\left( \frac{d\sigma_p^2B_{\mathcal{R}}^2}{\mu} \left(\frac{t_{\mathrm{mix}}}{T}\right)^{\frac{2(p-1)}{p}} \right),\qquad{(23)}\] where the hidden factors are polylogarithmic in \(T\), \(1/\delta\), \(d\), \(L/\mu\), and \(t_{\mathrm{mix}}\), and contain no additional polynomial power of \(t_{\mathrm{mix}}\).
The proof is given in Appendix 16.3.
Remark 8 (Radius admissibility and dimension dependence). [thm:heavy-upper,cor:heavy-geometric] are stated with an explicit induction radius \(\mathcal{R}\). In applications one may choose any \(\mathcal{R}\ge 4\Delta_0+4\) for which ?? and ?? hold; increasing the block size \(b\) decreases \(s_{\rm ht}\) and makes these conditions easier to satisfy. The factor \(d\) in ?? comes from coordinatewise clipping and a union bound over coordinates in 20. We do not claim this dimension dependence is optimal. The lower bound in 4 is one-dimensional and matches only the finite-moment exponent and the Markovian effective-sample-size dependence.
The exponent in 3 and the dependence on the Markovian effective sample size cannot be improved in general. The lower bound below reduces PL optimization to estimating the mean of a heavy-tailed sticky Markov chain.
Theorem 4 (Heavy-tail and mixing lower bound). Fix \(p\in(1,2]\), \(\tau\ge2\), and \(\sigma_p\ge1\). There are universal constants \(c,c_0>0\) such that the following holds for every \(n\ge 8\tau\). Consider all algorithms which, after observing \(n\) oracle outputs generated during \(n\) Markov transitions starting from the fixed initial state \(Z_0=0\), output an estimate \(\widehat x_n\). There exists a one-dimensional quadratic PL objective \[f_\theta(x)=\frac{1}{2}(x-\theta)^2\] and a Markovian oracle satisfying Assumption 4 with a valid geometric mixing time at most \(c\tau\) and moment scale at most a constant multiple of \(\sigma_p\), such that \[\label{eq:heavy-lower-prob} \mathbb{P}\left( f_\theta(\widehat x_n)-f_\theta^\star \ge c\,\sigma_p^2\left(\frac{\tau}{n}\right)^{\frac{2(p-1)}{p}} \right) \ge c_0.\qquad{(24)}\] Hence the heavy-tail exponent and the polynomial dependence on the number of effective Markovian samples in 3 are unavoidable up to logarithmic factors. Since the construction is one-dimensional, this lower bound does not address the dimension factor in the upper bound.
The proof is given in Appendix 16.4.
6 Relaxing global assumptions↩︎
The main theorem already removes compactness of the Markov state space and replaces a single geometric mixing-time parameter by a general mixing profile. The remaining global assumptions can also be localized in the standard way. We record a formal version because it is useful in overparameterized models, where PL and oracle Lipschitzness often hold only near the initialization.
For \(R>0\), write \[\mathcal{S}_R:=\{x\in\mathbb{R}^d:\Delta(x)\le R\}.\] Assume that \(f\) is globally \(L\)-smooth, while the PL inequality ?? , the stationary-gradient identity ?? , the pointwise oracle envelope ?? , and the Lipschitz condition ?? hold only for \(x,y\in\mathcal{S}_R\). The pathwise ABC bound ?? is required only at times for which \(x_k\in\mathcal{S}_R\).
Corollary 4 (Local PL and local oracle regularity). Let the local assumptions above hold on \(\mathcal{S}_R\). Let the windows satisfy the admissibility conditions ?? ?? , and let \(C_\star\) and \(\rho_0\) be the constants from 1 computed using the local constants on \(\mathcal{S}_R\). If \[\label{eq:R-local-condition} R\ge 2\Delta_0+C_\star(1+\rho_0),\qquad{(25)}\] then the conclusion of 1 holds. In particular, with probability at least \(1-\delta\), all iterates remain in \(\mathcal{S}_R\) and satisfy ?? for every \(k\ge1\).
The proof is given in Appendix 14.
7 Proof roadmap↩︎
We summarize the proof architecture and point to the specific appendix results used in each step. The paper has three proof mechanisms. The first is a weighted PL descent recursion for ordinary SGD. The second is the lag-blocking argument, which converts the adaptive Markovian descent observable into residue-class martingale differences plus controlled bias and replacement terms. The third is the robust clipped-block argument for finite-\(p\) heavy-tailed Markovian gradients. The appendices are organized so that each of these mechanisms is isolated in a sequence of lemmas before being combined in the corresponding theorem.
7.0.0.1 Light-tailed upper bound: 1.
The proof begins with the deterministic descent structure induced by PL geometry. In 2, smoothness from 1 is applied to the SGD update \[x_{k+1}=x_k-\alpha_kG_k, \qquad G_k=g(x_k,Z_k)+M_{k+1}.\] The PL inequality in 1 then turns the gradient-norm term into a contraction in the suboptimality \(\Delta_k=f(x_k)-f^\star\). The ABC envelope in [ass:abc] is used at this stage to control the quadratic term \(\alpha_k^2\|G_k\|^2\). This gives a one-step inequality of the form \[\Delta_{k+1} \le (1-\mu\alpha_k)\Delta_k +controlled deterministic terms -\alpha_k\langle \nabla f(x_k),M_{k+1}\rangle -\alpha_k h(x_k,Z_k).\] Iterating this recursion produces the weighted representation in 2, with weights \(w_{\ell,k}\). The deterministic estimates on these weights are collected in 3. These estimates are used repeatedly to show that weighted square sums have the correct order, for example \[\sum_{\ell<k} w_{\ell,k}^2 \asymp \frac{1}{k+K_0}\] up to constants and logarithmic factors.
The stochastic terms in the weighted recursion are controlled on stopped good events. The martingale-difference perturbation \[\sum_{\ell=0}^{k-1} w_{\ell,k} \big\langle \nabla f(x_\ell),M_{\ell+1}\big\rangle\] is handled in 5. The stopped event ensures that \(\Delta_\ell\) remains inside the induction envelope, so the ABC envelope in [ass:abc] gives deterministic bounds on the martingale increments. A union bound over times then gives the uniform-in-time control needed in the final first-failure argument.
The Markovian descent term \[\sum_{\ell=0}^{k-1} w_{\ell,k}h(x_\ell,Z_\ell), \qquad h(x,z)=\langle \nabla f(x),g(x,z)-\nabla f(x)\rangle,\] is the main difficulty. It is not a martingale sum because \(x_\ell\) is generated from the past Markov trajectory, and \(Z_\ell\) need not be stationary conditionally on the past. For a fixed terminal time \(k\), the proof introduces the analytical lag \(m=m_k\). The first \(m\) terms are kept separate and controlled by 9. For \(\ell\ge m\), the decomposition \[h(x_\ell,Z_\ell) = h(x_{\ell-m},Z_\ell) + \bigl\{h(x_\ell,Z_\ell)-h(x_{\ell-m},Z_\ell)\bigr\}\] separates the Markovian term into a delayed part and a replacement error.
The delayed part is where 3 is used. Since \(x_{\ell-m}\) is \(\mathcal{F}_{\ell-m}\)-measurable, the conditional law of \(Z_\ell\) given \(\mathcal{F}_{\ell-m}\) is \(P^m(Z_{\ell-m},\cdot)\). Thus the uniform total-variation mixing profile \(\varepsilon(m)\) controls the conditional bias of the delayed observable. After subtracting this conditional mean, the delayed sum is split into residue classes modulo \(m\). Along each residue class, consecutive indices are separated by exactly \(m\) Markov transitions, and the recentered delayed terms form a martingale-difference sequence with respect to a down-sampled filtration. This is formalized in 6. The key quantitative point is that the residue-class martingale bounds involve \[m\sum_{\ell<k}w_{\ell,k}^2,\] rather than \(m^2\sum_{\ell<k}w_{\ell,k}^2\). This single power of \(m\) is the source of the linear polynomial dependence on the mixing window.
The remaining pieces of the Markovian term are controlled separately. The conditional mixing bias is bounded in 7 by combining 3 with the envelope for \(h\). The replacement error is controlled in 8. This uses the Lipschitz condition in [ass:abc], the envelope estimates for \(h\) from 4, and the pathwise movement bound \[\|x_\ell-x_{\ell-m}\| \le \sum_{i=\ell-m}^{\ell-1}\alpha_i\|G_i\|.\] On the stopped event, the ABC envelope controls the gradients in this movement bound. Thus the replacement term is deterministic after conditioning on the good event, and the admissibility condition ?? ensures that it is small enough to be absorbed into the induction envelope.
The one-step stopped induction estimate is 10. This lemma combines 5, 6, 7, 8, and 9. The first admissibility condition ?? controls the size of the stochastic concentration terms, while the second admissibility condition ?? controls the drift accumulated by replacing \(x_\ell\) with \(x_{\ell-m}\). The proof of 1, given in Appendix 12, then applies a first-failure argument: assume the induction envelope holds up to time \(k-1\), apply 10 at time \(k\), and show that the envelope cannot be violated on the high-probability event. A union bound over the failure probabilities gives the simultaneous guarantee ?? for all \(k\ge1\).
7.0.0.2 Geometric mixing corollary: 1.
1 is stated for a general uniform total-variation profile \(\varepsilon(m)\). Therefore it does not by itself choose a closed-form delay. Under the geometric condition ?? , the delay \(m_k\) is chosen so that the mixing bias is small compared with the weighted descent scale. The elementary logarithm-over-linear estimate needed for this calculation is 11, and the admissibility of the geometric windows is verified in 12.
The role of 12 is to check that the choices of \(m_k\), \(u_k\), \(q_k\), and \(\Theta_k\) satisfy ?? –?? once \(K_0\) satisfies ?? . In particular, it shows that \[m_k=\widetilde{O}(t_{\mathrm{mix}})\] under geometric mixing. Since the leading variance term in 6 scales like \(m_k\sum_{\ell<k}w_{\ell,k}^2\), substituting the geometric-window estimates into ?? gives the leading stochastic order \[\widetilde{O}\!\left(\frac{t_{\mathrm{mix}}}{k+K_0}\right),\] with only logarithmic factors hidden in \(\widetilde{O}(\cdot)\). This proves 1.
7.0.0.3 Light-tailed lower bound: 2.
The lower bound is designed to show that the linear polynomial dependence on \(t_{\mathrm{mix}}\) cannot be improved, even in the simplest PL geometry. The construction uses the one-dimensional quadratic objective \[f(x)=\frac{1}{2}x^2\] and a persistent two-state Markov chain. The lower-bound instance is verified to satisfy [ass:objective,ass:abc,ass:mixing] in 13. The mixing time of the two-state chain is computed in 14; the key fact is that the autocorrelation decays geometrically at rate \(1-2\varepsilon\), so the mixing time is of order \(1/\varepsilon\).
The SGD recursion on this instance is linear. 15 writes the final iterate as a weighted linear filter of the Markov chain: \[x_k=-\sigma\sum_{i=0}^{k-1}b_{i,k}Z_i .\] The weights corresponding to the recent half of the trajectory are lower bounded in 16. Because the chain is persistent, the covariance \(\mathbb{E}[Z_iZ_j]\) remains positive for lags of order \(1/\varepsilon\). Combining this autocorrelation with the recent-weight lower bound yields the variance lower bound in 17: \[\mathbb{E}[x_k^2] \gtrsim \frac{\sigma^2}{\varepsilon k}.\] Since \(t_{\mathrm{mix}}\asymp 1/\varepsilon\), this is exactly the desired expectation lower bound.
To convert the second-moment lower bound into a constant-probability lower bound, 18 proves a fourth-moment upper bound for the same linear filter. The proof of 2 then applies Paley–Zygmund to \(x_k^2\). This yields both ?? and ?? ; combining these estimates with 14 gives ?? . Thus any high-probability upper bound valid over [ass:objective,ass:abc,ass:mixing] must have leading stochastic order at least \(\Omega(\sigma^2t_{\mathrm{mix}}/k)\) at constant confidence.
7.0.0.4 Heavy-tailed upper bound: 3.
The heavy-tailed proof uses a different oracle model and a different algorithm. Instead of the pathwise ABC envelope in [ass:abc], it uses the stationary finite-\(p\) moment condition in 4. Because this condition gives no deterministic envelope and may not imply a finite variance, ordinary martingale concentration cannot be applied directly to the raw gradients. The algorithm therefore holds the iterate fixed over a block, clips each consecutive Markovian gradient, and averages all clipped samples. The coordinatewise clipping map is defined in 13 , and the resulting all-samples clipped block method is 1.
The first ingredient is the stationary clipping calculation in 19. This lemma records two standard consequences of a finite-\(p\) moment assumption. First, clipping creates a bias of order \[v^p\lambda^{1-p},\] where \(v\) is the local \(p\)-moment scale and \(\lambda\) is the clipping level. Second, the clipped variable has second moment of order \[v^p\lambda^{2-p}.\] These are the heavy-tailed analogues of bounded variance estimates. They are applied coordinate by coordinate and then unioned over the dimension.
The second ingredient is the Markovian clipped-block concentration lemma, 20. This lemma is the heavy-tailed analogue of the lag-blocking concentration argument used in the light-tailed proof. For a block of length \(b\), the first \(m\) samples are controlled directly by the clipping level. For the remaining samples, the proof delays by \(m\) steps, subtracts the conditional mean given the sigma-field one lag in the past, and splits the centered terms into residue classes modulo \(m\). Freedman’s inequality is then applied within each residue class. Summing the residue-class bounds gives the effective variance term \[\sqrt{ mbu_{\rm ht} \bigl(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\bigr) },\] and after division by the block length \(b\), balancing this term with the clipping bias yields the rate factor \[\left(\frac{mu_{\rm ht}}{b}\right)^{(p-1)/p}.\]
The third ingredient is deterministic PL descent with inexact gradients, 21. Once the clipped block average \(\widehat g_r\) satisfies \[\|\widehat g_r-\nabla f(x_r)\|\le e_r,\] this lemma shows that the update with step size \(1/(4L)\) contracts the objective up to an error of order \(e_r^2/\mu\). Therefore the heavy-tailed concentration bound controls optimization error after squaring the gradient-estimation error.
The proof of 3, given in Appendix 16.2, combines these three ingredients through a stopped induction. The stopped event has two purposes. First, the radius condition \(\Delta(x_r)\le \mathcal{R}\) ensures that the local moment scale is bounded by \(B_{\mathcal{R}}\), so 20 can be applied at the next iterate. Second, the gradient-accuracy event ensures that 21 can be applied to perform one PL descent step. Thus the proof alternates between concentration and deterministic descent: concentration gives a sufficiently accurate clipped gradient estimate at \(x_r\), and deterministic PL descent keeps \(x_{r+1}\) inside the radius while reducing the suboptimality up to the statistical error floor.
The geometric transition-budget rate in 3 is obtained by choosing the number of outer blocks \(N\), the block length \(b\), and the analytical lag \(m\) as functions of the total transition budget \(T\). The choice of \(N\) makes the optimization transient negligible, the choice of \(b\) ensures that the block average has enough effective samples, and the choice of \(m\) makes the Markovian bias \(\varepsilon(m)\) smaller than the target confidence level. Under geometric mixing, \(m=\widetilde{O}(t_{\mathrm{mix}})\), so the statistical floor in 3 becomes \[\widetilde{O}\!\left( \sigma_p^2 \left(\frac{t_{\mathrm{mix}}}{T}\right)^{2(p-1)/p} \right),\] up to logarithmic and dimension factors.
7.0.0.5 Heavy-tailed lower bound: 4.
The proof of 4, given in Appendix 16.4, embeds finite-\(p\) mean estimation into one-dimensional PL optimization. The algorithm is allowed to be arbitrary, subject only to observing the oracle transcript and its own internal randomness; it is not told which of the two lower-bound instances is in force. The construction uses two objectives with minimizers separated by a distance of order \[\sigma_p\left(\frac{\tau}{n}\right)^{(p-1)/p}.\] Distinguishing these two objectives is therefore necessary for returning a point with smaller suboptimality than the claimed lower bound.
The Markov chain used in the construction is sticky: it refreshes only once every \(O(\tau)\) transitions on average. Hence \(n\) observed Markov transitions contain only \(O(n/\tau)\) effectively independent opportunities to see an informative heavy-tailed sample. With constant probability, the transcript contains no informative refresh. On this event, the two instances produce identical oracle transcripts, so any algorithm coupled with the same internal randomness must output the same point under both instances. Since the two minimizers are separated, this common output must have large error for at least one of the two objectives.
The finite-\(p\) moment scale determines the separation between the two instances. The rare refresh distribution is chosen so that the stationary \(p\)-moment is bounded by \(\sigma_p^p\), while the mean shift is of order \[\sigma_p\left(\frac{\tau}{n}\right)^{(p-1)/p}.\] Squaring this separation gives the PL suboptimality lower bound \[\Delta(\widehat x_n) \gtrsim \sigma_p^2 \left(\frac{\tau}{n}\right)^{2(p-1)/p}\] with constant probability. Since the constructed sticky chain has geometric mixing time \(O(\tau)\), this matches the dependence in 3 up to logarithmic and dimension factors.
7.0.0.6 Local assumptions: 4.
The localization result in 4 is proved in Appendix 14. The point of this corollary is that the global smoothness, PL, and oracle-envelope assumptions need only hold on a sublevel set that contains the stopped trajectory. The proof repeats the first-failure induction from Appendix 12, but all estimates are restricted to \[\mathcal{S}_R:=\{x:\Delta(x)\le R\}.\] The condition ?? ensures that the induction envelope remains inside \(\mathcal{S}_R\). Consequently, every time the proof invokes 2, 4, 5, 8, or 10, the required constants are the local constants on \(\mathcal{S}_R\). Thus the global theorem transfers directly to the local setting once the initial point and the induction envelope are contained in the sublevel region.
8 Conclusion↩︎
We developed a sharp high-probability theory for stochastic optimization under the Polyak–Łojasiewicz condition when gradient samples are generated along an exogenous Markov chain. In the bounded-oracle regime, we showed that ordinary SGD achieves a uniform-in-time rate whose leading stochastic term has order \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) under geometric mixing, up to logarithmic factors. This closes the gap between the \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\) leading stochastic order produced by Poisson-equation martingale-range analyses and the \(\widetilde{O}(t_{\mathrm{mix}}/k)\) order suggested by expectation bounds. The main technical device is a lag-blocking argument: the Markovian descent observable is delayed until the chain has mixed, split into residue classes, and then controlled by martingale concentration without changing the SGD algorithm.
We also proved that this order is unavoidable. A one-dimensional quadratic PL objective driven by a persistent two-state Markov chain already exhibits suboptimality of order \(\sigma^2t_{\mathrm{mix}}/k\) in expectation and with constant probability. Thus the upper bound identifies the optimal polynomial dependence on the mixing time in the light-tailed Markovian PL-SGD setting.
Beyond bounded gradients, we studied a finite-\(p\)-moment heavy-tailed regime. Here robustification must be algorithmic: the method holds the iterate fixed over short blocks, clips every Markovian gradient in the block, and averages all of the clipped samples. The resulting high-probability bound has the effective-sample-size rate \[\widetilde{O}\!\left( \sigma_p^2 \left(\frac{t_{\mathrm{mix}}}{T}\right)^{2(p-1)/p} \right)\] under geometric mixing, where \(T\) is the Markov-transition budget. A matching sticky-chain lower bound shows that both the Markovian effective-sample-size dependence and the finite-moment exponent are unavoidable up to logarithmic factors. The lower bound is one-dimensional, so the dimension dependence in the upper bound is not claimed to be optimal. Together, the light-tailed and heavy-tailed results characterize the statistical price of Markovian dependence for PL stochastic optimization.
Several directions remain open. First, the heavy-tailed method uses blockwise updates; an important question is whether one can design a fully online robust method that updates after every Markovian sample while retaining the same effective-sample-size rate under minimal nonstationary assumptions. Second, our analysis treats exogenous Markov chains. Extending the theory to parameter-dependent kernels, as arise in policy-gradient, actor–critic, and adaptive-MCMC methods, would require controlling the interaction between iterate movement, invariant-distribution drift, and mixing. Third, the present results use uniform total-variation mixing. Developing analogous sharp high-probability bounds under weaker drift/minorization or \(V\)-uniform ergodicity assumptions would broaden the scope to noncompact state spaces such as linear dynamical systems with sub-Gaussian innovations. Finally, it would be valuable to combine the lag-blocking viewpoint with variance reduction, acceleration, and decentralized asynchronous updates, where Markovian dependence is intrinsic to the algorithmic architecture.
9 Extended Related work↩︎
This section reviews the closest work on stochastic approximation, PL optimization, Markovian gradient methods, concentration for Markov chains, and robust optimization under heavy tails. The most relevant comparison for our main theorem is summarized in 2; the paragraphs below then give broader context.
3pt
We next review the surrounding literature in more detail.
9.0.0.1 Stochastic approximation and SGD.
The recursion studied here belongs to the classical stochastic approximation lineage initiated by Robbins and Monro [1] and Kiefer and Wolfowitz [2]. The asymptotic ODE viewpoint and martingale methods for recursive algorithms were developed by Ljung [50], Kushner and Yin [4], Borkar [5], and Benveniste, Metivier, and Priouret [3]. Nonasymptotic analyses for stochastic gradient and stochastic approximation methods include Moulines and Bach [7], Rakhlin, Shamir, and Sridharan [51], Gower et al.[8], and the broad optimization perspective of Bottou, Curtis, and Nocedal [6]. Many of these works assume conditionally unbiased martingale-difference noise or independent sampling. Our work instead focuses on temporally dependent gradient samples generated by a Markov chain and seeks uniform-in-time high-probability bounds.
9.0.0.2 PL geometry and SGD under growth conditions.
The Polyak-Łojasiewicz inequality originated in Polyak’s work on gradient methods [24]; the modern optimization formulation and its relationship to error bounds, restricted secant inequalities, quadratic growth, and related conditions were developed systematically by Karimi, Nutini, and Schmidt [25]. The condition is weaker than strong convexity and appears in overparameterized learning and control; examples include wide neural networks [42], linear-quadratic control [43], and composed strongly convex objectives. For stochastic gradients under PL geometry, several analyses allow the noise magnitude to grow with the local optimization scale rather than requiring a uniform bounded-variance assumption; examples include Gower et al. [8], Li, Zhuang, and Orabona [44], and Khaled and Richtarik [9]. The ABC envelope is one such growth condition: it bounds the stochastic-gradient magnitude by a combination of \(\|\nabla f(x)\|^2\), the objective gap \(f(x)-f^\star\), and an additive noise floor. Such growth conditions are important for least squares, interpolation, and minibatch sampling because uniform bounded variance is often too restrictive. High-probability PL results under light-tailed martingale noise have been obtained by Madden, Dall’Anese, and Becker [52], while Karandikar and Vidyasagar [53] study almost-sure rates under biased noise and unbounded variance. These results do not address the Markovian sampling bias that is central in this paper.
9.0.0.3 SGD and first-order methods with Markovian sampling.
Markovian gradient noise has been studied in convex, nonconvex, strongly convex, and PL settings. Sun, Sun, and Yin [27] analyze Markov chain gradient descent for convex problems and inexact gradients. Doan, Nguyen, Pham, and Romberg [28] and Doan [29] provide finite-time analyses for stochastic gradient algorithms under Markov randomness. Even [30] studies Markov-chain SGD under mild assumptions, develops lower bounds involving hitting-time quantities, and introduces MC-SAG as a variance-reduced method for Markovian sampling. Beznosikov et al.[33] obtain optimal one-power mixing-time dependence for several first-order methods through randomized batching and multilevel ideas, and also treat variational inequalities. Kar et al.[26] establish the first uniform-in-time high-probability PL-SGD theorem with Markovian plus martingale-difference noise under an ABC envelope; their high-probability theorem has leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}^2/k)\), whereas their expectation theorem has leading stochastic order \(\widetilde{O}(t_{\mathrm{mix}}/k)\). The light-tailed part of our paper closes this high-probability mixing gap for the ordinary one-sample SGD recursion, up to logarithmic factors, and proves that the resulting order is sharp.
9.0.0.4 Markovian stochastic approximation and reinforcement learning.
A large body of stochastic approximation and reinforcement-learning theory uses Markovian noise. Poisson-equation decompositions for Markov-driven stochastic approximation go back at least to Metivier and Priouret [31] and are standard in the monographs of Benveniste et al.[3], Kushner and Yin [4], and Borkar [5]. In reinforcement learning, temporal-difference learning and linear stochastic approximation under Markovian data have been studied through finite-sample, asymptotic, and bootstrap viewpoints; representative works include Bhandariet al.[17], Srikant and Ying [18], Kaledin et al. [19], Liu et al. [20], and Ganesh et al. [23]. Recent work also treats nonexpansive or two-time-scale stochastic approximation under Markovian data [54], [55]. Agrawal et al. [41] study concentration for general stochastic approximation with a finite-state Markovian component and heavy-tailed martingale noise. Our focus is different: we study last-iterate optimization under PL geometry, allow the Markovian gradient component itself to be heavy-tailed in the robust regime, and prove matching optimization lower bounds.
9.0.0.5 Concentration for Markov chains.
Classical concentration inequalities for Markov chains include Hoeffding-type bounds for uniformly ergodic chains [45], Chernoff and spectral-gap bounds for finite chains [56], and the coupling and spectral inequalities of Paulin [46]. These inequalities show that additive functionals of a Markov chain often behave like averages over an effective sample size reduced by a mixing parameter. They are not directly plug-and-play for adaptive SGD, however, because the observable at time \(k\) depends on the iterate \(x_k\), which is itself a function of the past data. Poisson-equation methods handle this adaptivity but can introduce a squared mixing factor when combined with worst-case martingale range bounds. Our lag-blocking proof is a direct concentration argument for the weighted, iterate-adapted additive functional: the delay creates approximate independence, and splitting into residue classes converts the delayed sum into martingale differences without changing the algorithm.
9.0.0.6 Decentralized, MCMC, privacy, and system-identification motivations.
Markovian sampling appears naturally in token-based and random-walk decentralized optimization. Early randomized incremental and distributed methods include Johansson, Rabi, and Johansson [10] and Duchi, Agarwal, and Wainwright [57]; more recent token frameworks include Walkman [11] and the principled token-algorithm design of Hendrikx [12]. Markov chains also arise when gradients are estimated using MCMC samples, where mixing controls the bias and variance of the gradient estimator. In privacy-preserving learning, subsampling mechanisms for privacy amplification, including differentially private SGD [13], banded matrix-factorization schemes [14], and minimum-separation subsampling [15], can produce temporally dependent minibatches. In online system identification, observations from stable dynamical systems generate Markovian regressors, as in streaming linear system identification [16]. These examples motivate a theory that treats Markovian dependence as a first-order parameter rather than as a lower-order perturbation.
9.0.0.7 Heavy-tailed stochastic optimization.
Heavy-tailed gradient noise has motivated robust stochastic methods that avoid sub-Gaussian or bounded-variance assumptions. For SGD under infinite variance, Wang et al.[58] derive convergence rates in expectation. High-probability nonconvex stochastic optimization with finite \(p\)th moments has been studied by Cutkosky and Mehta [34], Gorbunov et al.[35], Sadiev et al.[36], and Nguyen et al.[37], with clipping, normalization, momentum, or mirror-descent variants playing a central role. Puchkin et al.[38] use smoothed median-of-means ideas to stabilize gradients, Huebler, Fatkhullin, and He [39] study normalized SGD under heavy tails, and Armacki et al.[40] give high-probability guarantees for a class of nonlinear SGD transformations including clipping, quantization, and sign methods. These works largely concern independent, online, or martingale-type noise rather than Markovian gradient samples. The heavy-tailed part of this paper combines clipping with consecutive Markovian blocks and obtains the effective-sample-size rate dictated by the mixing profile while using all samples inside each block.
9.0.0.8 Robust statistics, heavy-tailed mean estimation, and lower bounds.
Our heavy-tailed lower bound is based on the classical connection between stochastic optimization over quadratics and mean estimation. Robust mean estimation under heavy tails is a mature subject, including Catoni’s estimator [47], median-of-means and tournament estimators, and the survey of Lugosi and Mendelson [49]; Devroye et al.[48] give sub-Gaussian mean estimators under finite variance. Robust stochastic approximation ideas also appear in Juditsky and Nemirovski [59] and Nemirovski et al.[60]. For Markovian data, recent robust reinforcement-learning work analyzes median-of-means or clipping under time-correlated samples, including robust TD learning under contamination [61] and heavy-tailed rewards [62]. We use a sticky-chain construction to show that \(k\) Markovian samples can contain only \(k/t_{\mathrm{mix}}\) effective refreshes, and therefore the finite-\(p\) mean-estimation exponent \(2(p-1)/p\) is unavoidable for PL optimization as well.
9.0.0.9 Positioning.
The present paper therefore has two complementary roles. In the light-tailed regime, it sharpens the high-probability Markovian PL-SGD theory by matching the order suggested by expectation bounds and by proving a corresponding lower bound. In the heavy-tailed regime, it extends robust clipped-gradient guarantees from independent or martingale sampling to Markovian gradient oracles through all-samples clipped blocks, and proves that both the Markovian effective-sample-size dependence and finite-moment exponent are unavoidable, up to logarithmic and dimension factors.
10 Deterministic backbone for the light-tailed upper bound↩︎
This appendix collects deterministic estimates used throughout the proof of 1. Lemma 1 converts smoothness and lower boundedness into the gradient upper bound ?? . Lemma 2 derives the weighted PL descent recursion. Lemma 3 gives the weight estimates used in all concentration bounds, and Lemma 4 controls the Markovian descent observable \(h(x,z)\). Together these lemmas form the deterministic backbone of the lag-blocking proof.
Lemma 1 (Gradient upper bound under smoothness). Under Assumption 1, ?? holds.
Proof. Fix \(x\in\mathbb{R}^d\). By \(L\)-smoothness, for every \(y\), \[f(y)\le f(x)+\left\langle \nabla f(x),y-x\right\rangle+\frac{L}{2}\left\lVert y-x\right\rVert^2.\] Take \(y=x-L^{-1}\nabla f(x)\). Then \[f\left(x-L^{-1}\nabla f(x)\right) \le f(x)-\frac{1}{2L}\left\lVert \nabla f(x)\right\rVert^2.\] Since \(f^\star\le f(x-L^{-1}\nabla f(x))\), rearranging gives \[\left\lVert \nabla f(x)\right\rVert^2\le 2L(f(x)-f^\star)=2L\Delta(x).\] ◻
Lemma 2 (Weighted descent recursion). Under Assumptions 1 and 2, if 4 holds, then for every \(k\ge1\), \[\begin{align} \label{eq:descent} \Delta_k &\le \Delta_0\zeta_{0,k-1} +\frac{LC}{2}\sum_{\ell=0}^{k-1}\alpha_\ell^2\zeta_{\ell+1,k-1} -\sum_{\ell=0}^{k-1}w_{\ell,k}\left\langle \nabla f(x_\ell),M_{\ell+1}\right\rangle -\sum_{\ell=0}^{k-1}w_{\ell,k}h(x_\ell,Z_\ell). \end{align}\qquad{(26)}\]
Proof. By \(L\)-smoothness and the update \(x_{n+1}=x_n-\alpha_nG_n\), \[\begin{align} f(x_{n+1}) &\le f(x_n)-\alpha_n\left\langle \nabla f(x_n),G_n\right\rangle+\frac{L\alpha_n^2}{2}\left\lVert G_n\right\rVert^2 \\ &= f(x_n)-\alpha_n\left\lVert \nabla f(x_n)\right\rVert^2 -\alpha_n h(x_n,Z_n) -\alpha_n\left\langle \nabla f(x_n),M_{n+1}\right\rangle +\frac{L\alpha_n^2}{2}\left\lVert G_n\right\rVert^2. \end{align}\] Using ?? , the PL inequality ?? , and the gradient upper bound ?? , \[\begin{align} \Delta_{n+1} &\le \Delta_n -\left(\alpha_n-\frac{AL\alpha_n^2}{2}\right)\left\lVert \nabla f(x_n)\right\rVert^2 +\frac{BL\alpha_n^2}{2}\Delta_n +\frac{LC\alpha_n^2}{2} \\ &\quad -\alpha_n h(x_n,Z_n) -\alpha_n\left\langle \nabla f(x_n),M_{n+1}\right\rangle \\ &\le \left(1-2\mu\alpha_n+\frac{(2\mu A+B)L\alpha_n^2}{2}\right)\Delta_n +\frac{LC\alpha_n^2}{2} -\alpha_n h(x_n,Z_n) -\alpha_n\left\langle \nabla f(x_n),M_{n+1}\right\rangle. \end{align}\] The condition 4 implies \[\frac{(2\mu A+B)L\alpha_n^2}{2}\le \mu\alpha_n,\] so \[\Delta_{n+1} \le (1-\mu\alpha_n)\Delta_n +\frac{LC\alpha_n^2}{2} -\alpha_n h(x_n,Z_n) -\alpha_n\left\langle \nabla f(x_n),M_{n+1}\right\rangle.\] Iterating this affine recursion from \(n=0\) to \(n=k-1\) gives ?? . ◻
Lemma 3 (Weight estimates). Let \(\beta:=\mu a\ge2\) and assume \(K_0\ge \beta\). There is a constant \(c_w<\infty\), depending only on \(a\) and \(\mu\), such that for every \(k\ge1\), \[\begin{align} \zeta_{0,k-1}&\le \frac{K_0}{k+K_0},\label{eq:weight-init}\\ \sum_{\ell=0}^{k-1}\alpha_\ell^2\zeta_{\ell+1,k-1}&\le \frac{c_w}{k+K_0},\label{eq:weight-alpha2}\\ w_{\ell,k}&\le c_w\frac{\ell+K_0}{(k+K_0)^2},\qquad 0\le \ell\le k-1,\label{eq:weight-point}\\ \sum_{\ell=0}^{k-1}\frac{w_{\ell,k}^2}{\ell+K_0}&\le \frac{c_w}{(k+K_0)^2},\label{eq:weight-sum1}\\ \sum_{\ell=0}^{k-1}\frac{w_{\ell,k}^2}{(\ell+K_0)^2}&\le \frac{c_w}{(k+K_0)^3}.\label{eq:weight-sum2} \end{align}\] {#eq: sublabel=eq:eq:weight-init,eq:eq:weight-alpha2,eq:eq:weight-point,eq:eq:weight-sum1,eq:eq:weight-sum2} Moreover, for every integer \(m\in\{1,\ldots,k\}\), \[\begin{align} \sum_{\ell=m}^{k-1}\frac{w_{\ell,k}^2}{\ell-m+K_0} &\le \left(1+\frac{m}{K_0}\right)\frac{c_w}{(k+K_0)^2},\label{eq:weight-delay1}\\ \sum_{\ell=m}^{k-1}\frac{w_{\ell,k}^2}{(\ell-m+K_0)^2} &\le \left(1+\frac{m}{K_0}\right)^2\frac{c_w}{(k+K_0)^3}.\label{eq:weight-delay2} \end{align}\] {#eq: sublabel=eq:eq:weight-delay1,eq:eq:weight-delay2}
Proof. Since \(K_0\ge\beta\), we have \(0\le \mu\alpha_j\le1\). For \(0\le\ell\le k-1\), \[\begin{align} \zeta_{\ell+1,k-1} &=\prod_{j=\ell+1}^{k-1}\left(1-\frac{\beta}{j+K_0}\right) \le \exp\left(-\beta\sum_{j=\ell+1}^{k-1}\frac{1}{j+K_0}\right). \end{align}\] Using the integral comparison \[\sum_{j=\ell+1}^{k-1}\frac{1}{j+K_0} \ge \int_{\ell+1}^{k}\frac{dt}{t+K_0} =\log\frac{k+K_0}{\ell+K_0+1},\] we get \[\zeta_{\ell+1,k-1} \le \left(\frac{\ell+K_0+1}{k+K_0}\right)^\beta.\] Because \((\ell+K_0+1)/(\ell+K_0)\le 1+K_0^{-1}\) and \(\beta/K_0\le1\), \[\left(\frac{\ell+K_0+1}{k+K_0}\right)^\beta \le e\left(\frac{\ell+K_0}{k+K_0}\right)^\beta.\] Increasing constants from \(e\) to \(e^2\) if needed, this bound also covers the empty-product edge cases. Since \(\beta\ge2\), \[w_{\ell,k} =\frac{a}{\ell+K_0}\zeta_{\ell+1,k-1} \le ae^2\frac{(\ell+K_0)^{\beta-1}}{(k+K_0)^\beta} \le ae^2\frac{\ell+K_0}{(k+K_0)^2},\] which proves ?? . The initial product similarly satisfies \[\zeta_{0,k-1}\le \left(\frac{K_0}{k+K_0}\right)^\beta \le \frac{K_0}{k+K_0},\] which proves ?? .
For the first square sum, ?? yields \[\sum_{\ell=0}^{k-1}\frac{w_{\ell,k}^2}{\ell+K_0} \le \frac{a^2e^4}{(k+K_0)^4}\sum_{\ell=0}^{k-1}(\ell+K_0) \le \frac{a^2e^4}{(k+K_0)^4}(k+K_0)^2.\] This is ?? after enlarging \(c_w\). The second square sum follows from \[\sum_{\ell=0}^{k-1}\frac{w_{\ell,k}^2}{(\ell+K_0)^2} \le \frac{a^2e^4}{(k+K_0)^4}\sum_{\ell=0}^{k-1}1 \le \frac{a^2e^4}{(k+K_0)^3}.\] Also, \[\sum_{\ell=0}^{k-1}\alpha_\ell^2\zeta_{\ell+1,k-1} =\sum_{\ell=0}^{k-1}\alpha_\ell w_{\ell,k} \le \frac{a^2e^2}{(k+K_0)^2}\sum_{\ell=0}^{k-1}1 \le \frac{a^2e^2}{k+K_0},\] which proves ?? . Finally, for \(\ell\ge m\), \[\frac{1}{\ell-m+K_0} =\frac{\ell+K_0}{\ell-m+K_0}\frac{1}{\ell+K_0} \le\left(1+\frac{m}{K_0}\right)\frac{1}{\ell+K_0}.\] Squaring the displayed inequality gives the corresponding squared denominator bound. Combining these with ?? and ?? proves ?? and ?? . ◻
Lemma 4 (Envelope and Lipschitz bounds for the descent observable). Let \[\label{eq:r-def} r:=2AL+B,\qquad{(27)}\] and, for \(D\ge0\), define \[\label{eq:H-def} H(D):=\sqrt{2LD}\left(\sqrt{rD+C}+\sqrt{2LD}\right).\qquad{(28)}\] There are constants \(c_H,c_{\mathrm{lip}}<\infty\), depending only on \(L,L_g,A,B,C\), such that:
if \(\Delta(x)\le D\), then \(|h(x,z)|\le H(D)\) for every \(z\);
\(H(D)^2\le c_H(D+D^2)\) for every \(D\ge0\);
if \(\Delta(x)\le D_x\) and \(\Delta(y)\le D_y\), then \[\label{eq:h-lip-bound} |h(x,z)-h(y,z)| \le c_{\mathrm{lip}}(1+\sqrt{D_x}+\sqrt{D_y})\left\lVert x-y\right\rVert.\qquad{(29)}\]
Proof. If \(\Delta(x)\le D\), then ?? gives \(\left\lVert \nabla f(x)\right\rVert\le\sqrt{2LD}\). Moreover, ?? and ?? give \[\left\lVert g(x,z)\right\rVert\le \sqrt{A\left\lVert \nabla f(x)\right\rVert^2+B\Delta(x)+C} \le \sqrt{rD+C}.\] Thus \[\left\lVert \xi(x,z)\right\rVert\le \left\lVert g(x,z)\right\rVert+\left\lVert \nabla f(x)\right\rVert \le \sqrt{rD+C}+\sqrt{2LD}.\] The Cauchy-Schwarz inequality proves \(|h(x,z)|\le H(D)\).
Next, \[\begin{align} H(D)^2 &=2LD\left(\sqrt{rD+C}+\sqrt{2LD}\right)^2 \\ &\le 4LD(rD+C+2LD) \le c_H(D+D^2) \end{align}\] for a finite \(c_H\) depending only on \(L,A,B,C\).
For the Lipschitz bound, write \[\begin{align} |h(x,z)-h(y,z)| &\le \left\lVert \nabla f(x)-\nabla f(y)\right\rVert\left\lVert \xi(x,z)\right\rVert +\left\lVert \nabla f(y)\right\rVert\left\lVert \xi(x,z)-\xi(y,z)\right\rVert. \end{align}\] By \(L\)-smoothness, \(\left\lVert \nabla f(x)-\nabla f(y)\right\rVert\le L\left\lVert x-y\right\rVert\). The previous envelope gives \(\left\lVert \xi(x,z)\right\rVert\le c(1+\sqrt{D_x})\). Also, \[\left\lVert \xi(x,z)-\xi(y,z)\right\rVert \le \left\lVert g(x,z)-g(y,z)\right\rVert+\left\lVert \nabla f(x)-\nabla f(y)\right\rVert \le (L_g+L)\left\lVert x-y\right\rVert,\] and \(\left\lVert \nabla f(y)\right\rVert\le\sqrt{2LD_y}\). Combining these estimates proves ?? . ◻
11 Lag-blocking concentration estimates↩︎
This appendix proves the probabilistic estimates that control the stochastic terms in the weighted descent recursion of Lemma 2. Lemma 5 handles the martingale-difference perturbation. Lemmas 6–9 implement the lag-blocking decomposition of the adaptive Markovian term into a delayed martingale part, a mixing-bias part, a replacement error, and an initial-window term. These bounds are combined in Appendix 12.
The lemmas in this section are stated for a fixed target time \(k\). Let \(N:=k+K_0\) and let \(m\in\{1,\ldots,k\}\). Let \((\mathcal{K}_j)_{j=0}^{k-1}\) be a nonincreasing family of events, meaning \(\mathcal{K}_{j+1}\subseteq\mathcal{K}_j\), with \(\mathcal{K}_j\in\mathcal{F}_j\). Assume that on \(\mathcal{K}_j\), \[\label{eq:local-envelope} \Delta_j\le \frac{\Lambda}{j+K_0}, \qquad 0\le j\le k-1,\tag{19}\] for some deterministic \(\Lambda\ge1\).
Lemma 5 (Martingale-difference noise). For every \(\eta\in(0,1)\), with probability at least \(1-\eta\), \[\label{eq:M-noise-final} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=0}^{k-1}w_{\ell,k}\left\langle \nabla f(x_\ell),M_{\ell+1}\right\rangle\right| \le \frac{c_M}{N} \sqrt{\log\frac{2}{\eta}\left(\Lambda+\frac{\Lambda^2}{N}\right)},\qquad{(30)}\] where \(c_M<\infty\) depends only on \(a,\mu,L,A,B,C\).
Proof. Define \[Q_{\ell+1}:=w_{\ell,k}\left\langle \nabla f(x_\ell),M_{\ell+1}\right\rangle\mathbf{1}_{\mathcal{K}_\ell}, \qquad 0\le \ell\le k-1.\] Since \(\mathcal{K}_\ell\in\mathcal{F}_\ell\), \(w_{\ell,k}\) is deterministic, and \(\mathbb{E}[M_{\ell+1}\mid\mathcal{F}_\ell]=0\), the sequence \((Q_{\ell+1})\) is a martingale difference sequence. On \(\mathcal{K}_\ell\), ?? , ?? , and ?? imply \[\left\lVert M_{\ell+1}\right\rVert \le \left\lVert G_\ell\right\rVert+\left\lVert g(x_\ell,Z_\ell)\right\rVert \le 2\sqrt{r\frac{\Lambda}{\ell+K_0}+C},\] where \(r=2AL+B\). Also \(\left\lVert \nabla f(x_\ell)\right\rVert\le\sqrt{2L\Lambda/(\ell+K_0)}\). Hence \[|Q_{\ell+1}| \le c w_{\ell,k} \sqrt{\frac{\Lambda}{\ell+K_0}} \sqrt{1+\frac{\Lambda}{\ell+K_0}}\] for a constant \(c\) depending only on \(L,A,B,C\). Therefore \[|Q_{\ell+1}|^2 \le c w_{\ell,k}^2 \left(\frac{\Lambda}{\ell+K_0}+\frac{\Lambda^2}{(\ell+K_0)^2}\right).\] Define the deterministic bounds \[b_{\ell,k}^2 :=c w_{\ell,k}^2 \left(\frac{\Lambda}{\ell+K_0}+\frac{\Lambda^2}{(\ell+K_0)^2}\right), \qquad 0\le \ell\le k-1,\] so that \(|Q_{\ell+1}|\le b_{\ell,k}\) almost surely. Using ?? –?? , \[\sum_{\ell=0}^{k-1}b_{\ell,k}^2 \le \frac{c}{N^2}\left(\Lambda+\frac{\Lambda^2}{N}\right).\] The Azuma-Hoeffding inequality applied with the deterministic increment bounds \(b_{\ell,k}\) gives \[\mathbb{P}\left(\left|\sum_{\ell=0}^{k-1}Q_{\ell+1}\right| >\sqrt{2\log(2/\eta)\sum_{\ell=0}^{k-1}b_{\ell,k}^2}\right) \le \eta.\] Combining the last two displays yields the bound in ?? . On \(\mathcal{K}_{k-1}\), monotonicity gives \(\mathbf{1}_{\mathcal{K}_\ell}=1\) for every \(\ell\le k-1\), so \(\sum Q_{\ell+1}\) equals the martingale term in ?? . This proves the result after absorbing numerical constants into \(c_M\). ◻
Lemma 6 (Delayed residue-class martingale). For \(\ell\ge m\), define \[\label{eq:Y-def} Y_\ell:=w_{\ell,k}h(x_{\ell-m},Z_\ell), \qquad \overline{Y}_\ell:=\mathbb{E}[Y_\ell\mid\mathcal{F}_{\ell-m}].\qquad{(31)}\] For every \(\eta\in(0,1)\), with probability at least \(1-\eta\), \[\begin{align} \label{eq:delayed-mart-final} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=m}^{k-1}(Y_\ell-\overline{Y}_\ell)\right| &\le \frac{c_B}{N} \sqrt{m\log\left(\frac{2m}{\eta}\right) \left(1+\frac{m}{K_0}\right) \left(\Lambda+\frac{\Lambda^2}{N}\left(1+\frac{m}{K_0}\right)\right)}, \end{align}\qquad{(32)}\] where \(c_B<\infty\) depends only on \(a,\mu,L,A,B,C\).
Proof. For \(\ell\ge m\), set \[D_\ell:=(Y_\ell-\overline{Y}_\ell)\mathbf{1}_{\mathcal{K}_{\ell-m}}.\] Since \(x_{\ell-m}\) and \(\mathbf{1}_{\mathcal{K}_{\ell-m}}\) are \(\mathcal{F}_{\ell-m}\)-measurable, \[\mathbb{E}[D_\ell\mid\mathcal{F}_{\ell-m}]=0.\] On \(\mathcal{K}_{\ell-m}\), 19 and Lemma 4 give \[|Y_\ell| \le w_{\ell,k}H\left(\frac{\Lambda}{\ell-m+K_0}\right) =:b_\ell.\] The same bound holds for \(|\overline{Y}_\ell|\) on \(\mathcal{K}_{\ell-m}\), because conditional expectation is dominated by the conditional expectation of the absolute value. Hence \(|D_\ell|\le2b_\ell\).
We now spell out the filtration structure, since this is the point at which the lag creates martingale differences. Fix a residue class \(r\in\{0,1,\ldots,m-1\}\). List the indices \(\ell=r+jm\) that lie in \(\{m,m+1,\ldots,k-1\}\) in increasing order, say \(\ell_1<\cdots<\ell_s\). Define \(\mathcal{H}_0:=\mathcal{F}_{\ell_1-m}\) and \(\mathcal{H}_i:=\mathcal{F}_{\ell_i}\) for \(1\le i\le s\). For the first index, \(D_{\ell_1}\) has conditional mean zero given \(\mathcal{H}_0=\mathcal{F}_{\ell_1-m}\). For \(i\ge2\), the residue-class spacing gives \(\ell_i-m=\ell_{i-1}\), and hence \[\mathbb{E}[D_{\ell_i}\mid\mathcal{H}_{i-1}] =\mathbb{E}[D_{\ell_i}\mid\mathcal{F}_{\ell_i-m}]=0.\] Thus \((D_{\ell_i})_{i=1}^s\) is a martingale-difference sequence with respect to the down-sampled filtration \((\mathcal{H}_i)_{i=0}^s\). No independence across different residue classes is used; each class is controlled separately, and the resulting high-probability bounds are combined by a union bound. Azuma-Hoeffding gives \[\mathbb{P}\left(\left|\sum_{i=1}^sD_{\ell_i}\right| >\sqrt{8u\sum_{i=1}^sb_{\ell_i}^2}\right) \le 2e^{-u}.\] Take \(u=\log(2m/\eta)\) and union bound over the \(m\) residue classes. With probability at least \(1-\eta\), all residue-class inequalities hold. On that event, \[\begin{align} \left|\sum_{\ell=m}^{k-1}D_\ell\right| &\le \sum_{r=0}^{m-1}\left|\sum_{\ell\equiv r\, (\mathrm{mod}\,m)}D_\ell\right| \\ &\le \sum_{r=0}^{m-1}\sqrt{8u\sum_{\ell\equiv r\, (\mathrm{mod}\,m)}b_\ell^2} \\ &\le \sqrt{8um\sum_{\ell=m}^{k-1}b_\ell^2}, \end{align}\] where the last step is Cauchy-Schwarz.
It remains to bound the square sum. Lemma 4 gives \[b_\ell^2 \le c_H w_{\ell,k}^2 \left(\frac{\Lambda}{\ell-m+K_0}+\frac{\Lambda^2}{(\ell-m+K_0)^2}\right).\] Using ?? –?? , \[\sum_{\ell=m}^{k-1}b_\ell^2 \le \frac{c}{N^2}\left(1+\frac{m}{K_0}\right)\Lambda +\frac{c}{N^3}\left(1+\frac{m}{K_0}\right)^2\Lambda^2.\] Substituting this estimate into the previous display proves ?? . On \(\mathcal{K}_{k-1}\), all indicators \(\mathbf{1}_{\mathcal{K}_{\ell-m}}\) are one, so the sum of \(D_\ell\) is the displayed delayed centered sum. ◻
Lemma 7 (Mixing bias). Assume \(m<k\) and set \(\varepsilon_m:=\varepsilon(m)\), where \(\varepsilon(\cdot)\) is the uniform total-variation mixing profile in Assumption 3. Then, on \(\mathcal{K}_{k-1}\), \[\label{eq:mixing-bias-final} \left|\sum_{\ell=m}^{k-1}\overline{Y}_\ell\right| \le \frac{c_{\mathrm{mix}}\varepsilon_m}{N} \sqrt{N\left(1+\frac{m}{K_0}\right) \left(\Lambda+\frac{\Lambda^2}{N}\left(1+\frac{m}{K_0}\right)\right)},\qquad{(33)}\] where \(c_{\mathrm{mix}}<\infty\) depends only on \(a,\mu,L,A,B,C\).
Proof. Because \(x_{\ell-m}\) is \(\mathcal{F}_{\ell-m}\)-measurable and \(\int h(x_{\ell-m},z)\pi(dz)=0\), the full-filtration Markov property gives \[\begin{align} \overline{Y}_\ell &=w_{\ell,k}\int h(x_{\ell-m},z)\bigl(P^m(Z_{\ell-m},dz)-\pi(dz)\bigr). \end{align}\] On \(\mathcal{K}_{\ell-m}\), Lemma 4 and the dual total-variation bound [eq:tv-dual] imply \[|\overline{Y}_\ell| \le 2\varepsilon_m w_{\ell,k}H\left(\frac{\Lambda}{\ell-m+K_0}\right) =2\varepsilon_m b_\ell.\] Therefore, on \(\mathcal{K}_{k-1}\), \[\left|\sum_{\ell=m}^{k-1}\overline{Y}_\ell\right| \le 2\varepsilon_m\sum_{\ell=m}^{k-1}b_\ell \le 2\varepsilon_m\sqrt{k\sum_{\ell=m}^{k-1}b_\ell^2}.\] The square-sum estimate from the proof of Lemma 6 and \(k\le N\) give ?? . ◻
Lemma 8 (Replacement error). On \(\mathcal{K}_{k-1}\), \[\begin{align} \label{eq:replacement-final} &\left|\sum_{\ell=m}^{k-1}w_{\ell,k}\bigl(h(x_\ell,Z_\ell)-h(x_{\ell-m},Z_\ell)\bigr)\right| \\ &\quad\le c_R\Bigg[ \frac{m}{N} +\frac{m^2}{N^2}\left(1+\log\frac{N}{K_0}\right) +\frac{m\Lambda}{N^2}\left(1+\log\frac{N}{K_0}+\frac{m}{K_0}\right) \notag\\ & +\frac{m\sqrt\Lambda}{N^{3/2}} +\frac{m^2\sqrt\Lambda}{\sqrt{K_0}N^2} \Bigg], \end{align}\qquad{(34)}\] where \(c_R<\infty\) depends only on \(a,\mu,L,L_g,A,B,C\).
Proof. On \(\mathcal{K}_j\), the ABC bound and ?? imply \[\left\lVert G_j\right\rVert \le \sqrt{r\frac{\Lambda}{j+K_0}+C} \le c_G\left(1+\sqrt{\frac{\Lambda}{j+K_0}}\right)\] for a constant \(c_G\) depending only on \(L,A,B,C\). Hence, for \(\ell\ge m\), \[\begin{align} \label{eq:movement-proof} \left\lVert x_\ell-x_{\ell-m}\right\rVert &\le \sum_{j=\ell-m}^{\ell-1}\alpha_j\left\lVert G_j\right\rVert \\ &\le ac_G\sum_{j=\ell-m}^{\ell-1}\frac{1}{j+K_0} \left(1+\sqrt{\frac{\Lambda}{j+K_0}}\right) \notag\\ &\le c\frac{m}{\ell-m+K_0} \left(1+\sqrt{\frac{\Lambda}{\ell-m+K_0}}\right).\notag \end{align}\tag{20}\] The last inequality uses that \(j+K_0\ge \ell-m+K_0\) over the summation range.
By Lemma 4, 19 , and 20 , \[\begin{align} &|h(x_\ell,Z_\ell)-h(x_{\ell-m},Z_\ell)| \\ &\quad\le c_{\mathrm{lip}} \left(1+\sqrt{\frac{\Lambda}{\ell+K_0}}+\sqrt{\frac{\Lambda}{\ell-m+K_0}}\right) \left\lVert x_\ell-x_{\ell-m}\right\rVert \\ &\quad\le c\frac{m}{\ell-m+K_0} \left(1+\sqrt{\frac{\Lambda}{\ell-m+K_0}}+\frac{\Lambda}{\ell-m+K_0}\right). \end{align}\] Thus \[\begin{align} \label{eq:replacement-sum-proof} &\left|\sum_{\ell=m}^{k-1}w_{\ell,k}\bigl(h(x_\ell,Z_\ell)-h(x_{\ell-m},Z_\ell)\bigr)\right| \\ &\quad\le cm\sum_{\ell=m}^{k-1}w_{\ell,k}\left( \frac{1}{t_\ell}+\frac{\sqrt\Lambda}{t_\ell^{3/2}}+\frac{\Lambda}{t_\ell^2} \right),\notag \end{align}\tag{21}\] where \(t_\ell:=\ell-m+K_0\). Since \(\ell+K_0=t_\ell+m\), ?? gives \[w_{\ell,k}\le c\frac{t_\ell+m}{N^2}.\] The elementary estimates \[\begin{align} \sum_{\ell=m}^{k-1}1&\le k\le N, &\sum_{\ell=m}^{k-1}\frac{1}{t_\ell}&\le 1+\log\frac{N}{K_0}, &\sum_{\ell=m}^{k-1}\frac{1}{t_\ell^2}&\le \frac{1}{K_0},\\ \sum_{\ell=m}^{k-1}\frac{1}{\sqrt{t_\ell}}&\le 2\sqrt N, &\sum_{\ell=m}^{k-1}\frac{1}{t_\ell^{3/2}}&\le \frac{2}{\sqrt{K_0}} \end{align}\] therefore imply \[\begin{align} \sum_{\ell=m}^{k-1}\frac{w_{\ell,k}}{t_\ell} &\le \frac{c}{N^2}\left(N+m\left(1+\log\frac{N}{K_0}\right)\right),\\ \sum_{\ell=m}^{k-1}\frac{w_{\ell,k}}{t_\ell^{3/2}} &\le \frac{c}{N^2}\left(\sqrt N+\frac{m}{\sqrt{K_0}}\right),\\ \sum_{\ell=m}^{k-1}\frac{w_{\ell,k}}{t_\ell^2} &\le \frac{c}{N^2}\left(1+\log\frac{N}{K_0}+\frac{m}{K_0}\right). \end{align}\] Substituting these three estimates into 21 proves ?? . ◻
Lemma 9 (Initial window). For every \(m\in\{1,\ldots,k\}\), on \(\mathcal{K}_{k-1}\), \[\label{eq:initial-final} \left|\sum_{\ell=0}^{m-1}w_{\ell,k}h(x_\ell,Z_\ell)\right| \le c_I\left(\frac{\sqrt{m\Lambda}}{N}+\frac{\Lambda\sqrt m}{N^{3/2}}\right),\qquad{(35)}\] where \(c_I<\infty\) depends only on \(a,\mu,L,A,B,C\).
Proof. On \(\mathcal{K}_\ell\), Lemma 4 gives \[|h(x_\ell,Z_\ell)| \le H\left(\frac{\Lambda}{\ell+K_0}\right).\] Because \(\mathcal{K}_{k-1}\subseteq\mathcal{K}_\ell\) for every \(\ell\le k-1\), Cauchy-Schwarz gives, on \(\mathcal{K}_{k-1}\), \[\begin{align} \sum_{\ell=0}^{m-1}w_{\ell,k}|h(x_\ell,Z_\ell)| &\le \sqrt{m\sum_{\ell=0}^{m-1}w_{\ell,k}^2H\left(\frac{\Lambda}{\ell+K_0}\right)^2}. \end{align}\] Using \(H(D)^2\le c_H(D+D^2)\) and ?? –?? , \[\begin{align} \sum_{\ell=0}^{m-1}w_{\ell,k}^2H\left(\frac{\Lambda}{\ell+K_0}\right)^2 &\le c\sum_{\ell=0}^{k-1}w_{\ell,k}^2 \left(\frac{\Lambda}{\ell+K_0}+\frac{\Lambda^2}{(\ell+K_0)^2}\right) \\ &\le c\left(\frac{\Lambda}{N^2}+\frac{\Lambda^2}{N^3}\right). \end{align}\] Taking square roots proves ?? . ◻
12 Proof of Theorem 1: mixing-profile upper bound↩︎
Lemma 10 (One-step induction estimate). There are constants \(c_0,c_1,K_D<\infty\) and a number \(\rho_0\in(0,1)\), depending only on \(a,\mu,L,L_g,A,B,C\), such that the following holds. Fix \(k\ge1\), let \(N=k+K_0\), and choose \(m\in\{1,\ldots,k\}\). Set \[q:=1+\frac{m}{K_0}, \qquad u:=\log\left(\frac{16(m+1)(k+1)^2}{\delta}\right), \qquad \Theta:=muq^2.\] Assume \(K_0\ge K_D\) and \[\label{eq:small-window-step} \frac{\Theta}{N}\le\rho_0, \qquad \frac{m}{N}\left(1+\log\frac{N}{K_0}+\frac{m}{K_0}\right)\le\rho_0.\qquad{(36)}\] If \(m<k\), also assume \[\label{eq:mixing-small-step} \varepsilon(m)\le \frac{\delta}{32N^4}.\qquad{(37)}\] Let \(\Lambda\ge1\), and suppose that the good-event family \((\mathcal{K}_j)_{j=0}^{k-1}\) satisfies 19 . Let \[\eta_k:=\frac{\delta}{8(k+1)^2}.\] Then, outside an event of probability at most \(2\eta_k\), \[\begin{align} \label{eq:one-step-bound} \mathbf{1}_{\mathcal{K}_{k-1}} \Bigg( &\left|\sum_{\ell=0}^{k-1}w_{\ell,k}\left\langle \nabla f(x_\ell),M_{\ell+1}\right\rangle\right| +\left|\sum_{\ell=0}^{k-1}w_{\ell,k}h(x_\ell,Z_\ell)\right| \Bigg) \\ &\le \frac{\Lambda}{4N}+\frac{c_0(1+\Theta)}{N}+\frac{c_1}{N}.\notag \end{align}\qquad{(38)}\]
Proof. Throughout the proof, \(c\) denotes a finite constant depending only on \(a,\mu,L,L_g,A,B,C\); its value may change from line to line. The goal is to prove a single-time bound at the fixed terminal time \(k\). The good-event indicators are included only to make all increment bounds deterministic; on \(\mathcal{K}_{k-1}\) all earlier good events also hold.
12.0.0.1 Martingale-difference perturbation.
The martingale part is controlled by 5. Since \(m\ge1\), \(q\ge1\), and \(\Theta=muq^2\), we have \(\Theta\ge u\). Also \[\log\frac{2}{\eta_k} =\log\frac{16(k+1)^2}{\delta} \le \log\frac{16(m+1)(k+1)^2}{\delta}=u .\] Therefore, outside an event of probability at most \(\eta_k\), \[\begin{align} \label{eq:M-close-new} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=0}^{k-1}w_{\ell,k}\left\langle \nabla f(x_\ell),M_{\ell+1}\right\rangle\right| &\le \frac{c}{N}\sqrt{u\left(\Lambda+\frac{\Lambda^2}{N}\right)} \\ &\le \frac{c}{N}\sqrt{(1+\Theta)\Lambda} +\frac{c\Lambda}{N}\sqrt{\frac{1+\Theta}{N}} .\notag \end{align}\tag{22}\] For the first term we use Young’s inequality in the form \(c\sqrt{(1+\Theta)\Lambda}\le \Lambda/32+c(1+\Theta)\). For the second term, \[\sqrt{\frac{1+\Theta}{N}} \le \sqrt{\frac{1}{K_0}+\frac{\Theta}{N}}.\] By increasing \(K_D\) and then choosing \(\rho_0\) sufficiently small, the condition \(K_0\ge K_D\) and \(\Theta/N\le\rho_0\) make the last display small enough that \[\frac{c\Lambda}{N}\sqrt{\frac{1+\Theta}{N}} \le \frac{\Lambda}{32N}+\frac{c}{N}.\] Consequently the martingale-difference contribution satisfies \[\label{eq:M-final-use} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=0}^{k-1}w_{\ell,k}\left\langle \nabla f(x_\ell),M_{\ell+1}\right\rangle\right| \le \frac{\Lambda}{16N}+\frac{c(1+\Theta)}{N}+\frac{c}{N}.\tag{23}\]
12.0.0.2 Decomposition of the Markovian sum.
If \(m<k\), define \(Y_\ell\) and \(\overline{Y}_\ell\) by ?? . Then \[\sum_{\ell=0}^{k-1}w_{\ell,k}h(x_\ell,Z_\ell) = \sum_{\ell=0}^{m-1}w_{\ell,k}h(x_\ell,Z_\ell) + \sum_{\ell=m}^{k-1}(Y_\ell-\overline{Y}_\ell) + \sum_{\ell=m}^{k-1}\overline{Y}_\ell + \sum_{\ell=m}^{k-1}w_{\ell,k}\{h(x_\ell,Z_\ell)-h(x_{\ell-m},Z_\ell)\}.\] When \(m=k\), the three sums over \(\ell=m,\ldots,k-1\) are empty, so only the initial-window term remains.
12.0.0.3 Centered delayed term.
Assume first that \(m<k\). Since \[\log\frac{2m}{\eta_k} =\log\frac{16m(k+1)^2}{\delta} \le u,\] 6 gives, outside another event of probability at most \(\eta_k\), \[\begin{align} \label{eq:delayed-close-new} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=m}^{k-1}(Y_\ell-\overline{Y}_\ell)\right| &\le \frac{c}{N} \sqrt{muq\left(\Lambda+\frac{\Lambda^2q}{N}\right)} \\ &\le \frac{c}{N}\sqrt{\Theta\Lambda} +c\frac{\Lambda}{N}\sqrt{\frac{\Theta}{N}} .\notag \end{align}\tag{24}\] Here we used \(q\ge1\), \(muq\le muq^2=\Theta\), and \(muq\cdot q=muq^2=\Theta\). The first term is bounded by \(\Lambda/(64N)+c\Theta/N\) by Young’s inequality. The second term is at most \(\Lambda/(64N)\) after decreasing \(\rho_0\), because \(\Theta/N\le\rho_0\). Thus the centered delayed term is bounded by \[\label{eq:delayed-close-final-expanded} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=m}^{k-1}(Y_\ell-\overline{Y}_\ell)\right| \le \frac{\Lambda}{32N}+\frac{c\Theta}{N}.\tag{25}\]
12.0.0.4 Mixing bias.
By 7 and ?? , on \(\mathcal{K}_{k-1}\), \[\left|\sum_{\ell=m}^{k-1}\overline{Y}_\ell\right| \le \frac{c\delta}{N^5} \sqrt{Nq\left(\Lambda+\frac{\Lambda^2q}{N}\right)} .\] Since \(\delta<1\), \(q=1+m/K_0\le1+k/K_0\le N\), and \(\Lambda\ge1\), the right-hand side is at most \[\frac{c}{N^5}\{N\sqrt\Lambda+N\Lambda\} \le \frac{c(1+\Lambda)}{N^4}.\] Increasing \(K_D\) if necessary gives, for all \(N\ge K_D\), \[\label{eq:bias-close-new} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=m}^{k-1}\overline{Y}_\ell\right| \le \frac{\Lambda}{64N}+\frac{c}{N}.\tag{26}\]
12.0.0.5 Replacement term.
We now simplify the deterministic estimate in 8. The first term in ?? is bounded by \(cm/N\le c\Theta/N\), since \(u,q\ge1\). For the second term, use \[1+\log\frac{N}{K_0} \le c\log\{16(m+1)(k+1)^2/\delta\}=cu \le c\frac{\Theta}{m},\] which gives \[\frac{m^2}{N^2}\left(1+\log\frac{N}{K_0}\right) \le c\frac{m\Theta}{N^2} \le c\frac{\Theta}{N}.\] The \(\Lambda\)-linear replacement term is controlled directly by the second small-window condition: \[c\frac{m\Lambda}{N^2} \left(1+\log\frac{N}{K_0}+\frac{m}{K_0}\right) \le c\rho_0\frac{\Lambda}{N} \le \frac{\Lambda}{64N},\] after decreasing \(\rho_0\). The term \(cm\sqrt\Lambda/N^{3/2}\) satisfies \[c\frac{m\sqrt\Lambda}{N^{3/2}} \le \frac{\Lambda}{128N}+c\frac{m^2}{N^2} \le \frac{\Lambda}{128N}+c\frac{\Theta}{N}.\] For the final term, Young’s inequality gives \[c\frac{m^2\sqrt\Lambda}{\sqrt{K_0}N^2} \le \frac{\Lambda}{128N}+c\frac{m^4}{K_0N^3}.\] Because \(m\le N\) and \[\frac{m^2}{K_0} =m\frac{m}{K_0} \le m\left(1+\frac{m}{K_0}\right) \le mq \le mq^2 \le \Theta,\] we have \(m^4/(K_0N^3)\le \Theta/N\). Therefore \[\label{eq:replacement-close-new} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=m}^{k-1}w_{\ell,k}\{h(x_\ell,Z_\ell)-h(x_{\ell-m},Z_\ell)\}\right| \le \frac{\Lambda}{32N}+\frac{c\Theta}{N}.\tag{27}\]
12.0.0.6 Initial window.
Finally, 9 gives \[\mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=0}^{m-1}w_{\ell,k}h(x_\ell,Z_\ell)\right| \le c\frac{\sqrt{m\Lambda}}{N}+c\frac{\Lambda}{N}\sqrt{\frac{m}{N}} .\] The first term is at most \(\Lambda/(64N)+c m/N\le \Lambda/(64N)+c\Theta/N\). The second term is at most \(\Lambda/(64N)\) after decreasing \(\rho_0\), because \(m/N\le\Theta/N\le\rho_0\). Hence the initial window is bounded by \[\label{eq:initial-close-expanded} \mathbf{1}_{\mathcal{K}_{k-1}} \left|\sum_{\ell=0}^{m-1}w_{\ell,k}h(x_\ell,Z_\ell)\right| \le \frac{\Lambda}{32N}+\frac{c\Theta}{N}.\tag{28}\]
Before combining the estimates, we record where the two admissibility requirements are used. The condition \[\Theta/N\le\rho_0\] is used to absorb the stochastic square-root terms in 22 , 24 , and 28 into a small multiple of \(\Lambda/N\), with the remainder of order \((1+\Theta)/N\). The second condition, \[\frac{m}{N}\left(1+\log\frac{N}{K_0}+\frac{m}{K_0}\right)\le\rho_0,\] is used for the replacement term, where the movement of the iterate over one lag window produces the additional factor involving \(m\), \(K_0\), and \(\log(N/K_0)\). Thus the first admissibility condition controls concentration size, while the second controls the deterministic lag-replacement drift.
Combining 25 , 26 , 27 , and 28 controls the Markovian sum. If \(m=k\), the delayed centered, mixing-bias, and replacement bounds are omitted and the same conclusion follows from 28 . Adding the martingale bound 23 proves ?? after enlarging \(c_0\) and \(c_1\). The only probabilistic failures used are the martingale-difference event and the delayed martingale event, each of probability at most \(\eta_k\), so the total failure probability is at most \(2\eta_k\). ◻
Proof of 1. Let \(\rho_0\) and \(K_D\) be the constants from 10. Increase \(K_D\) if necessary so that \(K_D\ge K_{\mathrm{base}}\). Let \(\Gamma\ge1\) be chosen below and define \[\label{eq:lambda-def} \Lambda_k:=2K_0\Delta_0+\Gamma(1+\Theta_k).\tag{29}\] By the monotonicity noted after 9 , the sequences \(m_k,u_k,q_k,\Theta_k\) are nondecreasing in \(k\), so \(\Lambda_k\) is nondecreasing.
Define the single-time and cumulative good events by \[\label{eq:E-def} \mathsf E_k:=\left\{\Delta_k\le \frac{\Lambda_k}{k+K_0}\right\}, \qquad \mathsf E_0:=\Omega, \qquad \mathcal{E}_k:=\bigcap_{j=0}^k\mathsf E_j.\tag{30}\] For target time \(k\ge1\), on \(\mathcal{E}_{k-1}\) we have the envelope required in 19 with \(\Lambda=\Lambda_k\): for \(j=0\), \[\Delta_0\le \Lambda_k/K_0,\] because \(\Lambda_k\ge2K_0\Delta_0\), and for \(1\le j\le k-1\), \[\Delta_j\le \frac{\Lambda_j}{j+K_0}\le \frac{\Lambda_k}{j+K_0}.\] Thus 10 applies with \(m=m_k\) and \(\mathcal{K}_j=\mathcal{E}_j\). If \(m_k<k\), then by definition of \(m_k\) it equals \(\widehat m_k\), and ?? holds. The admissibility assumptions are exactly ?? .
By 2, 3, and 10, outside an event of probability at most \(2\eta_k\), \[\begin{align} \label{eq:pre-close-new} \mathbf{1}_{\mathcal{E}_{k-1}}\Delta_k &\le \frac{K_0\Delta_0+c_{\mathrm{det}}}{N_k} +\frac{\Lambda_k}{4N_k} +\frac{c(1+\Theta_k)}{N_k}, \end{align}\tag{31}\] where \(c_{\mathrm{det}}=LCc_w/2\) and \(c<\infty\) depends only on the model constants. Choose \[\label{eq:Gamma-choice-new} \Gamma\ge4(c+c_{\mathrm{det}}+1).\tag{32}\] Then the numerator on the right side of 31 is bounded by \[\begin{align} K_0\Delta_0+c_{\mathrm{det}}+c(1+\Theta_k)+\frac{1}{4}\{2K_0\Delta_0+\Gamma(1+\Theta_k)\} &\le \frac{3}{2}K_0\Delta_0+\frac{1}{2}\Gamma(1+\Theta_k)\\ &\le 2K_0\Delta_0+\Gamma(1+\Theta_k)=\Lambda_k. \end{align}\] Therefore \[\mathbb{P}(\mathcal{E}_{k-1}\cap\mathsf E_k^c) \le 2\eta_k =\frac{\delta}{4(k+1)^2}.\] The first-failure union bound gives \[\begin{align} \mathbb{P}\left(\bigcup_{k\ge1}\mathsf E_k^c\right) &=\mathbb{P}\left(\bigcup_{k\ge1}(\mathcal{E}_{k-1}\cap\mathsf E_k^c)\right) \\ &\le \sum_{k=1}^\infty\frac{\delta}{4(k+1)^2} \le \delta. \end{align}\] Thus \(\mathsf E_k\) holds for all \(k\ge1\) with probability at least \(1-\delta\). Taking \(C_\star=\Gamma\) proves ?? . ◻
13 Proof of Corollary 1: geometric window calculus↩︎
Lemma 11 (A logarithm-over-linear bound). Let \(r\ge1\) be an integer. Let \(b,s>0\) and assume \[\label{eq:log-linear-condition} 1+\log(b/s)\ge r.\qquad{(39)}\] Then \[\label{eq:log-linear} \sup_{N\ge b}\frac{(1+\log(N/s))^r}{N} =\frac{(1+\log(b/s))^r}{b}.\qquad{(40)}\]
Proof. Set \(y(N)=1+\log(N/s)\). Under ?? , \(y(N)\ge r\) for every \(N\ge b\). For \[\phi(N)=\frac{y(N)^r}{N}\] we have \[\frac{d}{dN}\log\phi(N) =\frac{r}{Ny(N)}-\frac{1}{N} =\frac{1}{N}\left(\frac{r}{y(N)}-1\right)\le0.\] Thus \(\phi\) is nonincreasing on \([b,\infty)\), and the supremum is attained at \(N=b\). ◻
Lemma 12 (Geometric windows are admissible). Fix \(\rho\in(0,1)\). There exists \(K_{\mathrm{win}}(\rho)<\infty\) such that the following holds. Let \(\delta\in(0,e^{-1})\), let \(t_{\mathrm{mix}}\ge1\), and assume ?? . If \[\label{eq:window-K-condition} K_0\ge K_{\mathrm{win}}(\rho)\,t_{\mathrm{mix}}\left(1+\log\frac{et_{\mathrm{mix}}}{\delta}\right)^3,\qquad{(41)}\] then the windows 8 9 satisfy, for every \(k\ge1\), \[\begin{align} \frac{\Theta_k}{N_k}&\le\rho,\label{eq:window-theta}\\ \frac{m_k}{N_k}\left(1+\log\frac{N_k}{K_0}+\frac{m_k}{K_0}\right)&\le\rho.\label{eq:window-replacement} \end{align}\] {#eq: sublabel=eq:eq:window-theta,eq:eq:window-replacement}
Proof. Let \[\ell_0:=1+\log\frac{et_{\mathrm{mix}}}{\delta}, \qquad y_k:=1+\log\frac{N_k}{\delta}.\] Under ?? , the minimal window in 8 satisfies \[\label{eq:m-upper-window-new} m_k\le ct_{\mathrm{mix}}y_k\tag{33}\] for a numerical constant \(c\). Indeed, if \[m\ge \left\lceil t_{\mathrm{mix}}\left(1+\log_2(32N_k^4/\delta)\right)\right\rceil,\] then \(\lfloor m/t_{\mathrm{mix}}\rfloor\ge \log_2(32N_k^4/\delta)\), and hence \(\varepsilon(m)\le\delta/(32N_k^4)\). Also, \[\label{eq:u-upper-window-new} u_k\le c y_k.\tag{34}\] Indeed, \(m_k+1\le ct_{\mathrm{mix}}y_k+1\le \exp(cy_k)\) since \(N_k\ge K_0\ge t_{\mathrm{mix}}\) and \(\delta<e^{-1}\); substituting this into the definition of \(u_k\) gives 34 .
Combining 33 and 34 , \[\begin{align} \label{eq:theta-pre-window} \frac{\Theta_k}{N_k} &=\frac{m_ku_k}{N_k}\left(1+\frac{m_k}{K_0}\right)^2 \\ &\le c\left\{ \frac{t_{\mathrm{mix}}y_k^2}{N_k} +\frac{t_{\mathrm{mix}}^2 y_k^3}{K_0N_k} +\frac{t_{\mathrm{mix}}^3 y_k^4}{K_0^2N_k} \right\}.\notag \end{align}\tag{35}\] By 11, each term is maximized, up to a numerical constant depending only on the logarithmic power, at \(N_k=K_0\). Let \(K_0=Kt_{\mathrm{mix}}\ell_0^3\) with \(K\ge K_{\mathrm{win}}(\rho)\). Then \[1+\log\frac{K_0}{\delta} \le c\{\ell_0+\log K+\log\ell_0\} \le c_K\ell_0,\] where \(c_K\) depends on \(K\) but not on \(t_{\mathrm{mix}}\) or \(\delta\). Substituting this bound into 35 at \(N_k=K_0\) yields \[\frac{\Theta_k}{N_k} \le c\left( \frac{c_K^2}{K\ell_0} +\frac{c_K^3}{K^2\ell_0^3} +\frac{c_K^4}{K^3\ell_0^5} \right).\] The right side tends to zero as \(K\to\infty\), uniformly over \(\ell_0\ge1\), because \(\log K/K^a\to0\) for every \(a>0\). Choosing \(K_{\mathrm{win}}(\rho)\) sufficiently large proves ?? .
For ?? , use 33 and \(\log(N_k/K_0)\le y_k\): \[\frac{m_k}{N_k}\left(1+\log\frac{N_k}{K_0}+\frac{m_k}{K_0}\right) \le c\left\{\frac{t_{\mathrm{mix}}y_k^2}{N_k}+\frac{t_{\mathrm{mix}}^2y_k^2}{K_0N_k}\right\}.\] The same logarithm-over-linear argument bounds the right side by \[c\left(\frac{c_K^2}{K\ell_0}+\frac{c_K^2}{K^2\ell_0^4}\right),\] which is at most \(\rho\) after increasing \(K_{\mathrm{win}}(\rho)\). This proves the lemma. ◻
Proof of 1. Let \(\rho_0,K_D,C_\star\) be the constants from 1. Choose \(K_{\mathrm{geo}}\) large enough so that ?? implies both \(K_0\ge K_{\mathrm{base}}\vee K_D\) and the hypothesis of 12 with \(\rho=\rho_0\). Then 12 gives \[\frac{\Theta_k}{N_k}\le\rho_0, \qquad \frac{m_k}{N_k} \left(1+\log\frac{N_k}{K_0}+\frac{m_k}{K_0}\right) \le\rho_0\] for every \(k\ge1\). These are exactly the admissibility conditions ?? –?? , while the definition of \(m_k\) gives the mixing condition needed in 1. Hence 1 applies and proves ?? .
It remains only to justify the displayed closed-form estimates. Set \[m=\left\lceil t_{\mathrm{mix}}\left(1+\log_2\left(\frac{32N_k^4}{\delta}\right)\right)\right\rceil .\] Then \(\lfloor m/t_{\mathrm{mix}}\rfloor\ge \log_2(32N_k^4/\delta)\). The geometric mixing assumption ?? therefore gives \(\varepsilon(m)\le \delta/(32N_k^4)\). Since \(m_k\) is the minimum of this admissible value and \(k\), we have \(m_k\le m\), which proves ?? . The quantity \(\Theta_k=m_ku_k(1+m_k/K_0)^2\) is monotone in \(m_k\). Replacing \(m_k\) by the upper bound \(M_k\) in both \(u_k=\log(16(k+1)^2(m_k+1)/\delta)\) and \((1+m_k/K_0)^2\) gives ?? .
Finally, 33 and 34 show that \(m_k=O(t_{\mathrm{mix}}\log(N_k/\delta))\) and \(u_k=O(\log(N_k/\delta))\). Hence \(\Theta_k=m_ku_k(1+m_k/K_0)^2\) contributes one polynomial power of \(t_{\mathrm{mix}}\), with additional logarithmic factors from \(u_k\) and \(q_k=1+m_k/K_0\). The offset condition ?? prevents \(q_k\) from creating any further polynomial power of \(t_{\mathrm{mix}}\). Substituting this into ?? gives the stated \(\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))\) leading stochastic order. ◻
14 Proof of Corollary 4: local PL and local oracle regularity↩︎
Proof of Corollary 4. The proof is the same first-failure induction as in 1, but we spell out why only local assumptions are used. Define \(\Lambda_k=2K_0\Delta_0+C_\star(1+\Theta_k)\) and the events \(\mathsf E_k,\mathcal{E}_k\) as in 30 . Up to the first failure of these events, the induction hypothesis gives, for every earlier index \(j\), \[\Delta_j\le \frac{2K_0\Delta_0+C_\star(1+\Theta_j)}{j+K_0}.\] Using the admissibility condition \(\Theta_j/(j+K_0)\le\rho_0\) at the same index, and \(K_0\ge1\), we obtain \[\Delta_j \le 2\Delta_0+C_\star\left(\frac{1}{K_0}+\frac{\Theta_j}{j+K_0}\right) \le 2\Delta_0+C_\star(1+\rho_0) \le R.\] Thus every iterate that appears before the first failure lies in the sublevel set \(\mathcal{S}_R\). On this stopped path, all uses of smoothness, PL, the ABC envelope, and the Lipschitz bound for the oracle are uses of their local versions on \(\mathcal{S}_R\). The Markov mixing assumption is unchanged because it concerns the exogenous chain only. Consequently the proofs of [lem:descent,lem:h-envelope,lem:M-noise,lem:delayed-mart,lem:mixing-bias,lem:replacement,lem:initial,lem:induction-step] apply with the local constants. The same summable first-failure union bound as in 1 gives the stated high-probability inequality. Since the inequality itself keeps \(\Delta_k\le R\), the stopped argument closes and all iterates remain in \(\mathcal{S}_R\) on the resulting event. ◻
15 Proof of Theorem 2: linear mixing-time lower bound↩︎
This appendix proves 2. The proof has four steps. First, Appendix 15.1 verifies that the two-state quadratic construction satisfies the assumptions of the upper-bound theorem. Second, Appendix 15.2 writes the SGD iterate as a linear filter of the Markov chain. Third, Appendix 15.3 proves a variance lower bound and a fourth-moment upper bound for this filter. Finally, Appendix 15.4 combines these moment estimates with a constant-probability argument and translates \(\varepsilon^{-1}\) into the mixing time.
15.1 Verification of the assumptions↩︎
Lemma 13 (The lower-bound instance satisfies the standard assumptions). The instance 10 11 satisfies Assumptions 1–3. Specifically, \(f\) is \(1\)-smooth and \(1\)-PL, \(g(\cdot,z)\) is \(1\)-Lipschitz for both states, the stationary gradient identity holds, and \[\label{eq:lower-abc-bound} \left\lvert g(x,z)\right\rvert^2\le 2\left\lvert x\right\rvert^2+2\sigma^2 =2\left\lVert \nabla f(x)\right\rVert^2+2\sigma^2.\qquad{(42)}\] Thus Assumption [ass:abc] holds with \(A=2\), \(B=0\), and \(C=2\sigma^2\).
Proof. For \(f(x)=x^2/2\), we have \(\nabla f(x)=x\), so \[\left\lvert \nabla f(x)-\nabla f(y)\right\rvert=\left\lvert x-y\right\rvert\] and \(f\) is \(1\)-smooth. Also \[\left\lVert \nabla f(x)\right\rVert^2=x^2=2(f(x)-f^\star),\] so \(f\) is \(1\)-PL. The invariant law of 10 is uniform on \(\{-1,+1\}\), hence \[\int g(x,z)\,\pi(dz) =\frac{x+\sigma}{2}+\frac{x-\sigma}{2}=x=\nabla f(x).\] For each fixed \(z\), \(g(x,z)=x+\sigma z\) is \(1\)-Lipschitz in \(x\). Finally, \[\left\lvert x+\sigma z\right\rvert^2\le 2x^2+2\sigma^2.\] for \(z\in\{-1,+1\}\), proving ?? . The mixing assertion is proved in 14 below. ◻
Lemma 14 (Mixing time of the two-state chain). Let \(\rho=1-2\varepsilon\) with \(\varepsilon\in(0,1/8]\). For the chain 10 , \[\label{eq:two-state-tv} \sup_{z\in\{-1,+1\}}\left\lVert P^t(\cdot\mid z)-\pi\right\rVert_{\mathrm{TV}}=\frac{\rho^t}{2}, \qquad t\ge0.\qquad{(43)}\] Consequently, \[\tau_\rho=\left\lceil\frac{\log 2}{-\log\rho}\right\rceil\] is a valid mixing time in the sense of ?? . Moreover, \[\label{eq:tau-rho-bounds} \frac{\log 2}{4\varepsilon}\le \tau_\rho\le \frac{\log 2}{2\varepsilon}+1.\qquad{(44)}\]
Proof. The transition matrix has eigenvalues \(1\) and \(\rho=1-2\varepsilon\). Starting from \(+1\), \[\mathbb{P}(Z_t=+1\mid Z_0=+1)=\frac{1+\rho^t}{2}, \qquad \mathbb{P}(Z_t=-1\mid Z_0=+1)=\frac{1-\rho^t}{2}.\] The invariant law is \(\pi(+1)=\pi(-1)=1/2\). Therefore the signed measure \(P^t(\cdot\mid +1)-\pi\) has masses \(\rho^t/2\) and \(-\rho^t/2\) on \(+1\) and \(-1\). Under the probability total-variation convention used in this paper, its norm is \(\rho^t/2\). The same calculation holds from \(-1\), proving ?? .
By the definition of \(\tau_\rho\), \(\rho^{\tau_\rho}\le 1/2\). If \(t\ge0\) and \(q=\lfloor t/\tau_\rho\rfloor\), then \(t\ge q\tau_\rho\) and hence \[\frac{\rho^t}{2}\le \rho^{q\tau_\rho}\le 2^{-q}=2^{-\lfloor t/\tau_\rho\rfloor}.\] Thus \(\tau_\rho\) is a valid mixing time.
It remains to prove ?? . For \(u\in(0,1/2]\), \[u\le -\log(1-u)\le 2u.\] With \(u=2\varepsilon\in(0,1/4]\), this gives \[2\varepsilon\le -\log(1-2\varepsilon)\le 4\varepsilon.\] Thus \[\frac{\log 2}{4\varepsilon}\le \frac{\log 2}{-\log\rho}\le \frac{\log 2}{2\varepsilon}.\] Since \(\tau_\rho=\lceil \log 2/(-\log\rho)\rceil\), the stated bounds follow. ◻
15.2 Linear representation of the SGD iterate↩︎
Define \[\label{eq:b-ik-def} b_{i,k}=\alpha_i\prod_{j=i+1}^{k-1}(1-\alpha_j), \qquad \alpha_j=\frac{a}{j+K}, \qquad 0\le i\le k-1,\tag{36}\] with the convention that an empty product equals one.
Lemma 15 (Linear filter representation). For the recursion 12 , \[\label{eq:xk-linear-filter} x_k=-\sigma\sum_{i=0}^{k-1}b_{i,k}Z_i.\qquad{(45)}\]
Proof. The proof is by induction. For \(k=1\), \[x_1=\left(1-\frac{a}{K}\right)x_0-\frac{a\sigma}{K}Z_0 =-\sigma\alpha_0Z_0,\] because \(x_0=0\), which agrees with ?? . Assume ?? holds at time \(k\). Then \[\begin{align} x_{k+1} &= (1-\alpha_k)x_k-\alpha_k\sigma Z_k \\ &= -\sigma\sum_{i=0}^{k-1}\alpha_i \left\{\prod_{j=i+1}^{k-1}(1-\alpha_j)\right\}(1-\alpha_k)Z_i -\sigma\alpha_k Z_k \\ &= -\sigma\sum_{i=0}^{k}\alpha_i \left\{\prod_{j=i+1}^{k}(1-\alpha_j)\right\}Z_i. \end{align}\] This is ?? with \(k\) replaced by \(k+1\). ◻
Lemma 16 (Lower bound on recent weights). Assume \(a\ge2\), \(K\ge\max\{4a,4a^2\}\), and \(k\ge\max\{8K,16a^2\}\). Let \[I_k=\{\lceil k/2\rceil,\lceil k/2\rceil+1,\ldots,k-1\}.\] Then for every \(i\in I_k\), \[\label{eq:recent-weight-lower} b_{i,k}\ge \frac{\beta_a}{k}, \qquad \beta_a=\frac{2a e^{-1}}{3^{a+1}}.\qquad{(46)}\]
Proof. Since \(K\ge4a\), for every \(j\ge0\), \[0\le \alpha_j=\frac{a}{j+K}\le \frac{a}{K}\le \frac{1}{4}.\] For \(0\le u\le1/2\), \(\log(1-u)\ge -u-u^2\). Therefore, for \(i\le k-1\), \[\begin{align} \label{eq:product-log-lower} \log\prod_{j=i+1}^{k-1}(1-\alpha_j) &\ge -\sum_{j=i+1}^{k-1}\frac{a}{j+K} -\sum_{j=i+1}^{k-1}\frac{a^2}{(j+K)^2}. \end{align}\tag{37}\] The first sum is bounded as \[\label{eq:harmonic-bound} \sum_{j=i+1}^{k-1}\frac{1}{j+K} \le \int_{i+K}^{k+K}\frac{du}{u} =\log\frac{k+K}{i+K}.\tag{38}\] For the second sum, using \(i\in I_k\) and \(k\ge16a^2\), \[\label{eq:square-sum-bound} \sum_{j=i+1}^{k-1}\frac{a^2}{(j+K)^2} \le \int_{i+K}^{\infty}\frac{a^2\,du}{u^2} =\frac{a^2}{i+K} \le \frac{2a^2}{k} \le \frac{1}{8} \le 1.\tag{39}\] Combining 37 39 gives \[\label{eq:product-lower} \prod_{j=i+1}^{k-1}(1-\alpha_j) \ge e^{-1}\left(\frac{i+K}{k+K}\right)^a.\tag{40}\] Since \(i\in I_k\) and \(k\ge8K\), \[i+K\ge \frac{k}{2}, \qquad k+K\le \frac{9k}{8}<\frac{3k}{2}, \qquad \frac{i+K}{k+K}\ge \frac{1}{3}.\] Also \(i+K\le k+K\le 3k/2\), so \[\alpha_i=\frac{a}{i+K}\ge \frac{2a}{3k}.\] Using this and 40 in the definition of \(b_{i,k}\) yields \[b_{i,k}\ge \frac{2a}{3k}e^{-1}3^{-a} =\frac{2ae^{-1}}{3^{a+1}}\frac{1}{k}.\] This proves ?? . ◻
15.3 Second and fourth moments↩︎
Let \[\label{eq:Sk-def} S_k=\sum_{i=0}^{k-1}b_{i,k}Z_i,\tag{41}\] so that \(x_k=-\sigma S_k\) by 15. Since the chain starts stationarily, \(\mathbb{E}Z_i=0\) and \[\label{eq:covariance-two-state} \mathbb{E}[Z_iZ_j]=\rho^{\left\lvert i-j\right\rvert}, \qquad i,j\ge0.\tag{42}\]
Lemma 17 (Variance lower bound). Under the conditions of 16, if in addition \(k\ge16/\varepsilon\), then \[\label{eq:variance-lower} \operatorname{Var}(S_k)\ge \frac{\beta_a^2}{128}\frac{1}{\varepsilon k}.\qquad{(47)}\]
Proof. All weights \(b_{i,k}\) are nonnegative because \(\alpha_j\le1/4\). From 42 , \[\label{eq:var-full-sum} \operatorname{Var}(S_k)=\sum_{i=0}^{k-1}\sum_{j=0}^{k-1}b_{i,k}b_{j,k}\rho^{\left\lvert i-j\right\rvert}.\tag{43}\] Restrict the double sum to \(I_k\times I_k\). By 16, \[\label{eq:var-restrict} \operatorname{Var}(S_k) \ge \frac{\beta_a^2}{k^2} \sum_{i\in I_k}\sum_{j\in I_k}\rho^{\left\lvert i-j\right\rvert}.\tag{44}\] Let \(n=\left\lvert I_k\right\rvert\). Since \(I_k\) contains at least \(k/2\) indices, \(n\ge k/2\). Let \[h=\left\lfloor\frac{1}{8\varepsilon}\right\rfloor.\] Because \(\varepsilon\le1/8\), \(h\ge1/(16\varepsilon)\). The condition \(k\ge16/\varepsilon\) implies \(n\ge k/2\ge8/\varepsilon\ge 2h+1\). For every integer \(0\le r\le h\), \[\rho^r=(1-2\varepsilon)^r\ge 1-2\varepsilon r\ge 1-2\varepsilon h\ge \frac{3}{4},\] where we used Bernoulli’s inequality \((1-u)^r\ge1-ur\) for \(u\in[0,1]\). For at least \(n-h\ge n/2\) choices of \(i\in I_k\), the indices \(i,i+1,\ldots,i+h\) all belong to \(I_k\). Hence \[\begin{align} \label{eq:cov-sum-lower} \sum_{i\in I_k}\sum_{j\in I_k}\rho^{\left\lvert i-j\right\rvert} &\ge \sum_{\substack{i\in I_k:\;i+h\le k-1}}\sum_{r=0}^{h}\rho^r \\ &\ge \frac{n}{2}(h+1)\frac{3}{4} \ge \frac{3}{8}\cdot\frac{k}{2}\cdot\frac{1}{16\varepsilon} \ge \frac{k}{128\varepsilon}. \end{align}\tag{45}\] Combining 44 and 45 proves ?? . ◻
Lemma 18 (Fourth moment upper bound). For every deterministic nonnegative sequence \(b_0,\ldots,b_{k-1}\) and the stationary two-state chain 10 , \[\label{eq:fourth-bound} \mathbb{E}\left(\sum_{i=0}^{k-1}b_iZ_i\right)^4 \le 24\left\{\operatorname{Var}\left(\sum_{i=0}^{k-1}b_iZ_i\right)\right\}^2.\qquad{(48)}\]
Proof. Let \(S=\sum_{i=0}^{k-1}b_iZ_i\). We first compute mixed fourth moments. The two-state stationary Markov chain can be represented as \[\label{eq:innovation-representation} Z_i=Z_0\prod_{r=1}^{i}Y_r,\tag{46}\] where \(Z_0\) is a Rademacher random variable, \(Y_1,Y_2,\ldots\) are independent of \(Z_0\), and \[\mathbb{P}(Y_r=1)=1-\varepsilon, \qquad \mathbb{P}(Y_r=-1)=\varepsilon.\] Then \(\mathbb{E}Y_r=1-2\varepsilon=\rho\). If \(i_1\le i_2\le i_3\le i_4\), the product \(Z_{i_1}Z_{i_2}Z_{i_3}Z_{i_4}\) equals \[\left(\prod_{r=i_1+1}^{i_2}Y_r\right) \left(\prod_{r=i_3+1}^{i_4}Y_r\right),\] because all other factors in 46 appear an even number of times and cancel. Therefore \[\label{eq:mixed-fourth} \mathbb{E}[Z_{i_1}Z_{i_2}Z_{i_3}Z_{i_4}] =\rho^{i_2-i_1+i_4-i_3}.\tag{47}\] Since the coefficients \(b_i\) are nonnegative, expanding \(S^4\) and grouping ordered quadruples by their nondecreasing rearrangement gives \[\begin{align} \label{eq:S4-ordering} \mathbb{E}S^4 &\le 24\sum_{0\le i\le j\le \ell\le m\le k-1} b_i b_j b_\ell b_m\rho^{j-i+m-\ell}. \end{align}\tag{48}\] The factor \(24\) is an upper bound on the number of permutations of four indices; if some indices coincide, this only overcounts and preserves the inequality.
Define \[\label{eq:Q-def} Q=\sum_{0\le i\le j\le k-1}b_i b_j\rho^{j-i}.\tag{49}\] The ordered quadruple sum in 48 is bounded by \(Q^2\), because \(Q^2\) sums \(b_i b_j b_\ell b_m\rho^{j-i+m-\ell}\) over all pairs \((i,j)\) and \((\ell,m)\) with \(i\le j\) and \(\ell\le m\), while the ordered quadruple sum restricts to the subset satisfying \(j\le\ell\). Hence \[\label{eq:S4-Q} \mathbb{E}S^4\le24Q^2.\tag{50}\] On the other hand, \[\begin{align} \label{eq:var-Q} \operatorname{Var}(S) &=\sum_{i=0}^{k-1}\sum_{j=0}^{k-1}b_i b_j\rho^{\left\lvert i-j\right\rvert} \\ &=\sum_{i=0}^{k-1}b_i^2+2\sum_{0\le i<j\le k-1}b_i b_j\rho^{j-i} \\ &=Q+\sum_{0\le i<j\le k-1}b_i b_j\rho^{j-i} \ge Q. \end{align}\tag{51}\] Combining 50 and 51 proves ?? . ◻
15.4 Completion of the lower-bound proof↩︎
Proof of 2. The assumptions are verified in 13, and the mixing-time claim is 14. It remains to prove the expectation and probability lower bounds.
By 15, \(x_k=-\sigma S_k\). Since \(f(x)=x^2/2\) and \(f^\star=0\), \[\label{eq:Delta-S} f(x_k)-f^\star=\frac{\sigma^2S_k^2}{2}.\tag{52}\] The chain starts in stationarity, so \(\mathbb{E}S_k=0\) and \(\mathbb{E}S_k^2=\operatorname{Var}(S_k)\). Using 17, \[\begin{align} \label{eq:expectation-proof} \mathbb{E}[f(x_k)-f^\star] &=\frac{\sigma^2}{2}\operatorname{Var}(S_k) \ge \frac{\sigma^2\beta_a^2}{256}\frac{1}{\varepsilon k}. \end{align}\tag{53}\]
For the probability statement, set \(Y=S_k^2\). The fourth-moment estimate in 18 gives \[\label{eq:Y-second} \mathbb{E}Y^2=\mathbb{E}S_k^4\le 24\{\mathbb{E}S_k^2\}^2.\tag{54}\] Applying Paley–Zygmund to the nonnegative random variable \(Y\), with threshold one half of its mean, yields \[\label{eq:paley-step} \mathbb{P}\left(Y\ge\frac{1}{2}\mathbb{E}Y\right) \ge (1-1/2)^2\frac{(\mathbb{E}Y)^2}{\mathbb{E}Y^2} \ge \frac{1}{96}.\tag{55}\] On this event, 52 and 17 imply \[\label{eq:prob-proof-threshold} f(x_k)-f^\star =\frac{\sigma^2Y}{2} \ge \frac{\sigma^2}{4}\operatorname{Var}(S_k) \ge \frac{\sigma^2\beta_a^2}{512}\frac{1}{\varepsilon k}.\tag{56}\] Since \[\beta_a^2=\frac{4a^2e^{-2}}{3^{2a+2}},\] both 53 and 56 hold with the common constant \[c_a=\frac{a^2e^{-2}}{2^{14}3^{2a+2}},\] which is smaller than both \(\beta_a^2/256\) and \(\beta_a^2/512\). The probability constant is \(c_0=1/96\), proving ?? and ?? .
Finally, 14 gives a valid geometric mixing time \(\tau_\rho\) satisfying \(\tau_\rho\le c/\varepsilon\) and \(\tau_\rho\ge c'/\varepsilon\) for universal constants \(c,c'>0\). Equivalently, \(1/\varepsilon\) is bounded below by a universal constant times this valid mixing time. Replacing \(1/\varepsilon\) in the preceding two lower bounds by that constant multiple of \(\tau_\rho\) gives ?? , with \(c'_a\) adjusted by the same universal factor. ◻
16 Proofs for the heavy-tailed extension↩︎
This appendix proves [thm:heavy-upper,cor:heavy-geometric,thm:heavy-lower]. Appendix 16.1 proves the clipped-gradient concentration and deterministic inexact-gradient tools. Appendix 16.2 proves the robust upper bound. Appendix 16.3 derives the transition-budget corollary under geometric mixing. Appendix 16.4 proves the matching heavy-tailed sticky-chain lower bound.
Throughout this appendix, \(c,c_p,c_{\lambda,p}\) denote positive constants depending only on \(p\), unless another dependence is explicitly stated.
16.1 Auxiliary estimates for clipped Markovian blocks↩︎
Lemma 19 (Clipped stationary bias and variance). Fix \(x\in\mathbb{R}^d\) and suppose Assumption 4 holds. Let \(g:=\nabla f(x)\), \(v:=\sigma_pR_p(x)\), and assume \(\lambda\ge2\|g\|_\infty\). For a coordinate \(j\), define \[\psi_j(z,u):=[\mathsf T_\lambda({\mathcal{G}}(x,z,u))]_j, \qquad \bar\psi_j:=\int \mathbb{E}_U[\psi_j(z,U)]\,\pi(dz).\] Then \[\begin{align} |\bar\psi_j-g_j|&\le c_p v^p\lambda^{1-p},\label{eq:clip-bias-coordinate}\\ \int \mathbb{E}_U\big[(\psi_j(z,U)-\bar\psi_j)^2\big] \pi(dz)&\le c_p v^p\lambda^{2-p}. \label{eq:clip-var-coordinate} \end{align}\] {#eq: sublabel=eq:eq:clip-bias-coordinate,eq:eq:clip-var-coordinate}
Proof. Let \((Z,U)\) have the stationary law \(\pi(dz)\) together with the auxiliary randomness of the oracle, and write \[\eta={\mathcal{G}}(x,Z,U)-g, \qquad \eta_j=[\eta]_j .\] The assumption gives \(\mathbb{E}_\pi\|\eta\|^p\le v^p\), hence \(\mathbb{E}_\pi|\eta_j|^p\le v^p\). Since \(\lambda\ge2\|g\|_\infty\), if \(|\eta_j|<\lambda/2\), then \(|g_j+\eta_j|<\lambda\) and clipping does not change the \(j\)th coordinate. Therefore clipping bias can occur only on the event \(\{|\eta_j|\ge\lambda/2\}\). Using Markov’s inequality and the identity \(\mathbb{E}\{|\eta_j|\mathbf{1}_{|\eta_j|\ge a}\}\le a^{1-p}\mathbb{E}|\eta_j|^p\), \[\begin{align} |\bar\psi_j-g_j| &=\left|\mathbb{E}_\pi\{[\mathsf T_\lambda(g+\eta)]_j-(g_j+\eta_j)\}\right| \\ &\le \mathbb{E}_\pi\left[|g_j+\eta_j|\mathbf{1}_{\{|\eta_j|\ge\lambda/2\}}\right] \\ &\le |g_j|\mathbb{P}_\pi(|\eta_j|\ge\lambda/2) +\mathbb{E}_\pi\left[|\eta_j|\mathbf{1}_{\{|\eta_j|\ge\lambda/2\}}\right] \\ &\le |g_j|\frac{\mathbb{E}_\pi|\eta_j|^p}{(\lambda/2)^p} +\frac{\mathbb{E}_\pi|\eta_j|^p}{(\lambda/2)^{p-1}} \le c_p v^p\lambda^{1-p}, \end{align}\] where the first term is also of order \(v^p\lambda^{1-p}\) because \(|g_j|\le\lambda/2\). This proves ?? .
For the second moment, split again according to \(|\eta_j|\le\lambda/2\). On this event the clipped coordinate differs from \(g_j\) by exactly \(\eta_j\). On the complement, both \([\mathsf T_\lambda(g+\eta)]_j\) and \(g_j\) have magnitude at most \(\lambda\) and \(\lambda/2\), respectively, so their difference is bounded by a numerical multiple of \(\lambda\). Hence \[\begin{align} \mathbb{E}_\pi\big([\mathsf T_\lambda(g+\eta)]_j-g_j\big)^2 &\le \mathbb{E}_\pi\big[|\eta_j|^2\mathbf{1}_{\{|\eta_j|\le\lambda/2\}}\big] +c\lambda^2\mathbb{P}_\pi(|\eta_j|>\lambda/2) \\ &\le (\lambda/2)^{2-p}\mathbb{E}_\pi|\eta_j|^p +c\lambda^2\frac{\mathbb{E}_\pi|\eta_j|^p}{(\lambda/2)^p} \le c_p v^p\lambda^{2-p}. \end{align}\] Finally, variance around \(\bar\psi_j\) is no larger than the second moment around any fixed center, so \[\mathbb{E}_\pi[(\psi_j-\bar\psi_j)^2] \le \mathbb{E}_\pi[(\psi_j-g_j)^2] \le c_pv^p\lambda^{2-p}.\] This proves ?? . ◻
Lemma 20 (Consecutive clipped-block concentration). Fix a deterministic point \(x\) satisfying \(\Delta(x)\le\mathcal{R}\), a block length \(b\ge1\), and an integer \(m\in\{1,\ldots,b\}\). Let the Markov chain start from an arbitrary state and let \[Y_i={\mathcal{G}}(x,Z_i,U_i),\qquad i=1,\ldots,b,\] where the auxiliary variables \(U_i\) are conditionally independent given the Markov trajectory. Define \[u:=\log\left(\frac{16d(m+1)}{\eta}\right), \qquad s:=\frac{mu}{b},\] for some \(\eta\in(0,1)\). Suppose \(\varepsilon(m)\le \eta/(8db)\), set \[\lambda=c_{\lambda,p}\sigma_pB_{\mathcal{R}}s^{-1/p},\] with \(c_{\lambda,p}\) sufficiently large, and assume \(\lambda\ge2\sqrt{2L\mathcal{R}}\). Then, with probability at least \(1-\eta\), \[\label{eq:consecutive-block-gradient-error} \left\|\frac{1}{b}\sum_{i=1}^b\mathsf T_\lambda(Y_i)-\nabla f(x)\right\| \le c_p\sqrt d\,\sigma_pB_{\mathcal{R}}s^{\frac{p-1}{p}}.\qquad{(49)}\] The same conclusion holds conditionally on any sigma-field \(\mathcal{A}\) with respect to which \(x\) and the initial Markov state are measurable, provided that after conditioning on \(\mathcal{A}\) the future chain evolves with transition kernel \(P\) from that initial state and the auxiliary variables \((U_i)\) are conditionally independent given the future Markov trajectory, with the same conditional oracle kernel as in 4.
Proof. We first justify the conditional version. After conditioning on such a sigma-field \(\mathcal{A}\), the query point \(x\) and the starting state are deterministic, the future Markov process still has transition kernel \(P\), and the auxiliary variables remain conditionally independent with the prescribed conditional oracle law. Hence all conditional expectations, mixing-bias estimates, and martingale-difference properties below hold under the regular conditional law. It is therefore enough to prove the result for a fixed deterministic starting state. Since \(\Delta(x)\le\mathcal{R}\), 1 gives \(\|\nabla f(x)\|\le\sqrt{2L\mathcal{R}}\). Thus \(R_p(x)\le B_{\mathcal{R}}\). Put \[g:=\nabla f(x), \qquad v:=\sigma_pB_{\mathcal{R}}.\] Then 4 gives the stationary moment bound needed in 19, and the condition \(\lambda\ge2\sqrt{2L\mathcal{R}}\) implies \(\lambda\ge2\|g\|_\infty\).
Fix a coordinate \(j\). Let \(\psi_j\) and \(\bar\psi_j\) be the clipped coordinate and its stationary mean from 19. We first control the centered block average \[S_j:=\frac{1}{b}\sum_{i=1}^b\{\psi_j(Z_i,U_i)-\bar\psi_j\}.\] The first \(m\) samples are not delayed by a full mixing window. Since \(|\psi_j|\le\lambda\) and \(|\bar\psi_j|\le\lambda\), their total contribution is bounded deterministically by \[\left|\frac{1}{b}\sum_{i=1}^{m}\{\psi_j(Z_i,U_i)-\bar\psi_j\}\right| \le \frac{2\lambda m}{b}.\]
For \(i>m\), define \[D_i:=\psi_j(Z_i,U_i)-\bar\psi_j -\mathbb{E}[\psi_j(Z_i,U_i)-\bar\psi_j\mid\mathcal{F}_{i-m}],\] where \(\mathcal{F}_i\) contains the chain and auxiliary variables up to time \(i\). The conditional mean term is small because, given \(\mathcal{F}_{i-m}\), the law of \(Z_i\) is \(P^m(Z_{i-m},\cdot)\), while the auxiliary variable is sampled from the same conditional kernel as in the stationary definition. Since \(\int\mathbb{E}_U\psi_j(z,U)\pi(dz)=\bar\psi_j\), the total-variation inequality [eq:tv-dual] and \(|\psi_j|\le\lambda\) give \[\label{eq:conditional-mean-heavy-block} \left|\mathbb{E}[\psi_j(Z_i,U_i)-\bar\psi_j\mid\mathcal{F}_{i-m}]\right| \le 2\lambda\varepsilon(m).\tag{57}\]
The variables \((D_i)_{i>m}\) are not martingale differences in the ordinary time order. Split the indices \(\{m+1,\ldots,b\}\) into residue classes modulo \(m\). If \(i_1<i_2<\cdots<i_s\) are the indices in one residue class, then \(i_{r+1}-m=i_r\). Hence \[\mathbb{E}[D_{i_{r+1}}\mid\mathcal{F}_{i_r}] =\mathbb{E}[D_{i_{r+1}}\mid\mathcal{F}_{i_{r+1}-m}]=0,\] so this subsequence is a martingale-difference sequence with respect to the filtration \((\mathcal{F}_{i_r})_{r=1}^s\). Moreover, \(|D_i|\le4\lambda\), because both \(\psi_j-\bar\psi_j\) and its conditional mean are bounded by \(2\lambda\).
We also need a conditional variance bound. Since subtracting a conditional mean can only decrease conditional second moment, \[\mathbb{E}[D_i^2\mid\mathcal{F}_{i-m}] \le \mathbb{E}[(\psi_j(Z_i,U_i)-\bar\psi_j)^2\mid\mathcal{F}_{i-m}].\] The function \((\psi_j-\bar\psi_j)^2\) is bounded by \(4\lambda^2\). Combining the stationary variance bound in 19 with [eq:tv-dual] gives \[\label{eq:cond-var-heavy-block} \mathbb{E}[D_i^2\mid\mathcal{F}_{i-m}] \le c_pv^p\lambda^{2-p}+8\lambda^2\varepsilon(m).\tag{58}\]
Apply Freedman’s inequality separately on each residue class, using range bound \(4\lambda\) and the variance bound 58 . Let \(I_r\subseteq\{m+1,\ldots,b\}\) denote the indices in residue class \(r\). For a fixed residue class, Freedman’s inequality gives, with probability at least \(1-2e^{-u}\), \[\left|\sum_{i\in I_r}D_i\right| \le c\sqrt{u |I_r|\left(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\right)} +c\lambda u .\] Taking a union bound over the at most \(m\) residue classes, this holds for every residue class simultaneously with probability at least \(1-2me^{-u}\). On this event, \[\begin{align} \left|\sum_{i=m+1}^bD_i\right| &\le \sum_{r=0}^{m-1}\left|\sum_{i\in I_r}D_i\right| \\ &\le c\sum_{r=0}^{m-1} \sqrt{u |I_r|\left(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\right)} +c\lambda m u . \end{align}\] By Cauchy–Schwarz, \[\begin{align} \sum_{r=0}^{m-1} \sqrt{|I_r|\left(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\right)} &\le \sqrt{m\sum_{r=0}^{m-1}|I_r|\left(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\right)} \\ &\le \sqrt{mb\left(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\right)} . \end{align}\] Therefore \[\begin{align} \label{eq:residue-heavy-bound} \left|\sum_{i=m+1}^b D_i\right| &\le c\sqrt{mu\,b\left(v^p\lambda^{2-p}+\lambda^2\varepsilon(m)\right)} +c\lambda m u . \end{align}\tag{59}\] The factor \(m\) under the square root is the price of the residue-class union and summation, not a loss of samples: the total number of summands remains \(b-m\).
Combining the initial-window bound, the accumulated conditional-mean bound from 57 , and 59 , and then dividing by \(b\), yields for the fixed coordinate \[\begin{align} |S_j| &\le c\left[ \sqrt{\frac{mu}{b}v^p\lambda^{2-p}} +\lambda\sqrt{\frac{mu}{b}\varepsilon(m)} +\frac{\lambda m u}{b} +\frac{\lambda m}{b} +\lambda\varepsilon(m)\right] \end{align}\] with probability at least \(1-2me^{-u}\). Since \(u\ge1\) and \(\varepsilon(m)\le\eta/(8db)\le1/b\le mu/b\), the last four terms are bounded by a constant multiple of \(\lambda mu/b=\lambda s\). Therefore \[|S_j| \le c\left[\sqrt{s v^p\lambda^{2-p}}+\lambda s\right].\] Adding the stationary clipping bias from 19 gives \[\left|\frac{1}{b}\sum_{i=1}^b[\mathsf T_\lambda(Y_i)]_j-g_j\right| \le c_p\left[ \sqrt{s v^p\lambda^{2-p}}+ \lambda s+v^p\lambda^{1-p}\right].\] With \(\lambda=c_{\lambda,p}v s^{-1/p}\), each of the three terms on the right is of order \(v s^{(p-1)/p}\), after choosing \(c_{\lambda,p}\) sufficiently large. Finally, \(2dme^{-u}\le\eta\) by the definition of \(u\), so a union bound over the \(d\) coordinates gives coordinatewise control simultaneously. Taking the Euclidean norm multiplies the coordinate bound by at most \(\sqrt d\), proving ?? . ◻
Lemma 21 (PL descent with deterministic gradient errors). Assume that \(f\) is \(L\)-smooth and \(\mu\)-PL. Let \(J\ge1\) be an integer and let \[x_{r+1}=x_r-\frac{1}{4L}(\nabla f(x_r)+e_r)\] for \(0\le r<J\). Suppose that \(\|e_r\|\le\epsilon\) for all \(0\le r<J\). Then \[\label{eq:det-inexact-rate} \Delta(x_J) \le \left(1-\frac{\mu}{16L}\right)^J\Delta(x_0) +\frac{8\epsilon^2}{\mu}.\qquad{(50)}\]
Proof. Fix one step and write \(g_r:=\nabla f(x_r)\). By \(L\)-smoothness and the update rule, \[\begin{align} \Delta(x_{r+1}) &\le \Delta(x_r)-\frac{1}{4L}\langle g_r,g_r+e_r\rangle +\frac{L}{2}\left\|\frac{1}{4L}(g_r+e_r)\right\|^2 \\ &= \Delta(x_r)-\frac{1}{4L}\|g_r\|^2 -\frac{1}{4L}\langle g_r,e_r\rangle +\frac{1}{32L}\|g_r+e_r\|^2 . \end{align}\] Using \(\|g_r+e_r\|^2\le2\|g_r\|^2+2\|e_r\|^2\) and \(-\langle g_r,e_r\rangle\le \|g_r\|\|e_r\|\le \frac{1}{2}\|g_r\|^2+\frac{1}{2}\|e_r\|^2\), \[\Delta(x_{r+1}) \le \Delta(x_r)-\frac{1}{16L}\|g_r\|^2+\frac{5}{16L}\|e_r\|^2.\] Enlarging constants in the harmless direction, and using \(\|e_r\|\le\epsilon\), \[\Delta(x_{r+1}) \le \Delta(x_r)-\frac{1}{16L}\|g_r\|^2+\frac{\epsilon^2}{2L}.\] The PL inequality gives \(\|g_r\|^2\ge2\mu\Delta(x_r)\), hence \[\Delta(x_{r+1}) \le \left(1-\frac{\mu}{8L}\right)\Delta(x_r)+\frac{\epsilon^2}{2L} \le \left(1-\frac{\mu}{16L}\right)\Delta(x_r)+\frac{\epsilon^2}{2L}.\] Iterating this affine recursion for \(J\) steps yields \[\Delta(x_J) \le \left(1-\frac{\mu}{16L}\right)^J\Delta(x_0) +\frac{\epsilon^2}{2L} \,\sum_{t=0}^{J-1}\left(1-\frac{\mu}{16L}\right)^t.\] The geometric sum is at most \(16L/\mu\), so the residual term is at most \(8\epsilon^2/\mu\), proving ?? . ◻
16.2 Proof of Theorem 3: robust upper bound↩︎
Proof of 3. Let \[\label{eq:heavy-epsilon-star} \epsilon_\nabla:=c_p\sqrt d\,\sigma_pB_{\mathcal{R}}s_{\rm ht}^{\frac{p-1}{p}},\tag{60}\] where the constant is the one from 20. We enlarge the constant \(c_p\) in the statement, if necessary, so that the admissibility condition ?? implies \[\label{eq:heavy-stay-radius} \frac{8\epsilon_\nabla^2}{\mu} \le \frac{c_p d\sigma_p^2B_{\mathcal{R}}^2}{\mu}s_{\rm ht}^{\vartheta_p} \le \frac{\mathcal{R}}{4}.\tag{61}\]
We prove that all block gradient estimates are accurate by a stopped induction. Let \(\mathcal{F}_r^{\rm pre}\) be the sigma-field just before the \(r\)th block is sampled. Define \[\mathcal{H}_r:=\left\{ \Delta(x_s)\le\mathcal{R}\text{ for every }0\le s\le r, \quad \|\widehat g_s-\nabla f(x_s)\|\le\epsilon_\nabla \text{ for every }0\le s<r \right\}, \qquad 0\le r\le N.\] This definition intentionally includes the current radius condition \(\Delta(x_r)\le\mathcal{R}\), which is needed before applying the block concentration lemma at the query point \(x_r\). The initial stopped event \(\mathcal{H}_0\) is deterministic and true because \(\mathcal{R}\ge4\Delta_0+4\) implies \(\Delta(x_0)=\Delta_0\le\mathcal{R}/4\le\mathcal{R}\).
The stopped event \(\mathcal{H}_r\) serves two purposes. The radius condition \(\Delta(x_s)\le\mathcal{R}\) is needed to apply 20 at the next query point, because the clipping scale is chosen using \(B_{\mathcal{R}}\). The gradient-error condition is needed to invoke the deterministic inexact-gradient PL lemma, 21. The proof therefore alternates between these two ingredients: concentration gives the next accurate block gradient estimate, and deterministic PL descent keeps the next iterate inside the radius.
Suppose \(\mathcal{H}_r\) holds. Then \(x_r\) is \(\mathcal{F}_r^{\rm pre}\)-measurable and \(\Delta(x_r)\le\mathcal{R}\). During the next block the algorithm holds this point fixed and observes \(b\) consecutive Markovian oracle samples. Every one of these samples is included in the average \(\widehat g_r\); the lag \(m\) is used only to decompose the proof into an initial window and delayed residue classes, not to discard or thin the block. Conditional on \(\mathcal{F}_r^{\rm pre}\), this is exactly the setting of the conditional version of 20, with arbitrary deterministic initial Markov state and failure probability \(\eta=\delta/(4N)\). The logarithmic factor in that lemma is \[\log\frac{16d(m+1)}{\eta} =\log\frac{64dN(m+1)}{\delta}=u_{\rm ht}.\] Moreover, ?? gives \[\varepsilon(m)\le \frac{\delta}{64dNb}=\frac{\eta}{16db}\le\frac{\eta}{8db},\] so the lemma’s mixing requirement is satisfied. Therefore, on \(\mathcal{H}_r\), \[\label{eq:conditional-heavy-failure-new} \mathbb{P}\left( \left.\|\widehat g_r-\nabla f(x_r)\|>\epsilon_\nabla\;\right|\;\mathcal{F}_r^{\rm pre} \right) \le \frac{\delta}{4N}.\tag{62}\]
Let \(\mathcal{A}_r:=\{\|\widehat g_r-\nabla f(x_r)\|\le\epsilon_\nabla\}\). Multiplying 62 by \(\mathbf{1}_{\mathcal{H}_r}\) and taking expectations gives \[\mathbb{P}(\mathcal{H}_r\cap\mathcal{A}_r^c)\le\frac{\delta}{4N}.\] Thus \[\label{eq:all-heavy-estimates-new} \mathbb{P}\left(\bigcup_{r=0}^{N-1}(\mathcal{H}_r\cap\mathcal{A}_r^c)\right) \le \frac{\delta}{4}.\tag{63}\] On the complement of this event, the induction closes. Indeed, assume \(\mathcal{H}_r\) holds. Then \(\mathcal{A}_r\) also holds. The event \(\mathcal{H}_r\) already contains the radius bounds for \(x_0,\ldots,x_r\) and the gradient-error bounds for blocks \(0,\ldots,r-1\); adding \(\mathcal{A}_r\) gives the gradient-error bound for block \(r\). Hence the first \(r+1\) gradient errors are all bounded by \(\epsilon_\nabla\). Applying 21 to those \(r+1\) updates gives \[\Delta(x_{r+1}) \le \Delta_0+\frac{8\epsilon_\nabla^2}{\mu} \le \frac{\mathcal{R}}{4}+\frac{\mathcal{R}}{4} \le \mathcal{R},\] where we used \(\mathcal{R}\ge4\Delta_0\) and 61 . Thus the radius bounds hold for all \(0\le s\le r+1\), and the gradient-error bounds hold for all \(0\le s<r+1\). Therefore \(\mathcal{H}_{r+1}\) holds. Starting from the deterministic true event \(\mathcal{H}_0\), induction gives \(\mathcal{H}_N\) with probability at least \(1-\delta/4\), hence at least \(1-\delta\).
On the event \(\mathcal{H}_N\), all outer iterates remain in the radius-\(\mathcal{R}\) sublevel set and all gradient errors are bounded by \(\epsilon_\nabla\). Applying 21 over all \(N\) outer steps yields \[\Delta(x_N) \le \left(1-\frac{\mu}{16L}\right)^N\Delta_0 +\frac{8\epsilon_\nabla^2}{\mu}.\] Substituting 60 and absorbing the numerical factor into the statement constant \(c_p\) gives ?? . The radius conclusion is part of \(\mathcal{H}_N\). ◻
16.3 Proof of Corollary 3: geometric transition-budget rate↩︎
Proof of 3. The choice of \(m\) in ?? gives \[\left\lfloor\frac{m}{t_{\mathrm{mix}}}\right\rfloor \ge \log_2\left(\frac{64dNT}{\delta}\right).\] Hence the geometric mixing condition ?? implies \[\varepsilon(m) \le \frac{\delta}{64dNT} \le \frac{\delta}{64dNb},\] because \(b\le T\). Thus the mixing admissibility condition of 3 holds. The number of Markov transitions used is exactly \(Nb\), and the definition \(b=\lfloor T/N\rfloor\) gives \(Nb\le T\).
It remains to translate \(s_{\rm ht}=mu_{\rm ht}/b\) into a transition-budget expression. Since \(b=\lfloor T/N\rfloor\) and the hypothesis \(m\le b\) implies \(b\ge1\), we have \(b\ge T/(2N)\). The choices in ?? imply \[m\le ct_{\mathrm{mix}}\log\left(\frac{64dNT}{\delta}\right), \qquad u_{\rm ht} =\log\left(\frac{64dN(m+1)}{\delta}\right) \le \mathrm{polylog}(T,1/\delta,d,t_{\mathrm{mix}},L/\mu).\] Therefore \[s_{\rm ht} =\frac{mu_{\rm ht}}{b} \le c\frac{t_{\mathrm{mix}}N}{T}\, \mathrm{polylog}(T,1/\delta,d,t_{\mathrm{mix}},L/\mu).\] The chosen number of outer iterations satisfies \[\left(1-\frac{\mu}{16L}\right)^N \le \exp\left(-\frac{\mu N}{16L}\right) \le (eT)^{-2} \le \frac{1}{T},\] up to an immaterial numerical constant. Substituting these estimates into ?? gives the first term \(\widetilde{O}(\Delta_0/T)\) and the second term in ?? . All additional factors are logarithmic in the quantities listed in the corollary. ◻
16.4 Proof of Theorem 4: sticky-chain lower bound↩︎
Proof of 4. The lower bound is for any algorithm whose decisions are measurable with respect to the oracle transcript and its own internal randomness. The algorithm is not told the sign \(s\in\{+,-\}\) used below. Thus, on events where the two oracle transcripts are identical, the algorithm must produce the same output under the two instances when its internal randomness is coupled.
Let \(q=\tau/(8n)\). Since \(n\ge8\tau\), we have \(q\le1/64\). Set \[A=\sigma_p q^{-1/p}, \qquad \theta=qA=\sigma_p q^{(p-1)/p}.\] Define two refresh distributions on \(\mathbb{R}\): under \(Q_+\), the value is \(A\) with probability \(q\) and \(0\) otherwise; under \(Q_-\), the value is \(-A\) with probability \(q\) and \(0\) otherwise. Their means are \(\pm\theta\). Moreover, \[\mathbb{E}_{Q_s}|Z-s\theta|^p \le 2^{p-1}\left(\mathbb{E}_{Q_s}|Z|^p+|\theta|^p\right) \le 2^{p-1}\left(qA^p+(qA)^p\right) \le c_p\sigma_p^p,\] so the centered stationary \(p\)th moment is at most a constant multiple of \(\sigma_p^p\).
For each sign \(s\in\{+,-\}\), define a sticky Markov chain as follows. At each transition, with probability \(1/\tau\) the chain refreshes from \(Q_s\), and with probability \(1-1/\tau\) it keeps its current value. The invariant law is \(Q_s\). From any starting state, after \(m\) steps the probability of not having refreshed is \((1-1/\tau)^m\); once a refresh occurs, the state has law \(Q_s\). Hence the total-variation distance to stationarity is at most \((1-1/\tau)^m\), so the chain has a valid geometric mixing time at most \(c\tau\) for a universal constant \(c\).
Consider the quadratic objective \[f_s(x)=\frac{1}{2}(x-s\theta)^2\] and the oracle output, at query point \(x_t\), \[Y_t=x_t-Z_t.\] Under the invariant law \(Q_s\), \(\mathbb{E}Z_t=s\theta\), hence \[\mathbb{E}[Y_t\mid x_t]=x_t-s\theta=\nabla f_s(x_t).\] The finite-moment condition in 4 follows from the centered-moment bound above, with moment scale enlarged by a universal constant.
The chain is initialized at the fixed nonstationary state \(Z_0=0\). Let \(\mathcal{N}\) be the event that no nonzero refresh occurs during the first \(n\) observed transitions. In one transition, a nonzero refresh occurs with probability \((1/\tau)q\), so under either sign \[\mathbb{P}_s(\mathcal{N}) =(1-q/\tau)^n =\left(1-\frac{1}{8n}\right)^n \ge e^{-1/4},\] after adjusting the universal constant in the lower bound. On \(\mathcal{N}\), all observed Markov states are zero. Consequently the complete oracle transcript is identical under \(Q_+\) and \(Q_-\): every oracle output is \(Y_t=x_t\), and the algorithm’s internal randomness can be coupled identically in the two instances.
Let \(\widehat x_n\) be the algorithm’s output on this common transcript. For every real number \(y\), at least one of the two distances to \(\theta\) and \(-\theta\) is at least \(\theta\): \[\mathbf{1}\{|y-\theta|\ge\theta\} +\mathbf{1}\{|y+\theta|\ge\theta\} \ge1.\] Averaging this inequality over the common transcript on \(\mathcal{N}\) and over the algorithm’s randomness gives the two-point testing bound \[\max_{s\in\{+,-\}} \mathbb{P}_s\left((\widehat x_n-s\theta)^2\ge\theta^2\right) \ge \frac{1}{2}\min_{s\in\{+,-\}}\mathbb{P}_s(\mathcal{N}) \ge \frac{1}{2}e^{-1/4}.\] Since \(f_s(\widehat x_n)-f_s^\star=\frac{1}{2}(\widehat x_n-s\theta)^2\), for at least one sign, \[\mathbb{P}_s\left(f_s(\widehat x_n)-f_s^\star\ge \frac{\theta^2}{2}\right) \ge \frac{1}{2}e^{-1/4}.\] Finally, \[\theta^2 =\sigma_p^2q^{2(p-1)/p} =\sigma_p^2\left(\frac{\tau}{8n}\right)^{2(p-1)/p}.\] Absorbing numerical constants into \(c\) and \(c_0\) proves ?? . ◻