Statistical inference for Linear Stochastic Approximation with Markovian Noise

Alexey Naumov; Eric Moulines; Marina Sheshukova; Sergey Samsonov

REVIEW 2 major objections 6 minor 1 cited by

Statistical inference for Linear Stochastic Approximation with Markovian Noise

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves explicit, non-asymptotic rates — $O(n^{-1/4})$ for Gaussian approximation and $O(n^{-1/10})$ for bootstrap confidence intervals — for Polyak–Ruppert averaged linear stochastic approximation iterates driven by Markovian…

desk verdict Strong theory contribution with correctable statement-level defects in the main text; worth reviewing carefully. read the letter →

arxiv 2505.19102 v1 pith:3ORFSKVW submitted 2025-05-25 stat.ML cs.LGmath.OCmath.STstat.TH

Sergey Samsonov , Marina Sheshukova , Eric Moulines , Alexey Naumov This is my paper · ORCID

classification stat.MLcs.LGmath.OCmath.STstat.TH MSC 62L2060F0562F4060J05

keywords linearstochasticapproximationBerry–EsseenboundsPolyak–RuppertaveragingMarkoviannoisemultipliersubsamplebootstrapconfidenceintervalstemporaldifferencelearningoverlappingbatchmeans

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Stochastic approximation algorithms — including temporal-difference learning, the workhorse of reinforcement learning — are usually analyzed under independent noise, yet in practice their data comes from a dependent Markov chain. This paper asks how fast the Polyak–Ruppert averaged iterates of a linear stochastic approximation (LSA) scheme converge to their Gaussian limit when the noise is Markovian, and whether a bootstrap can build valid confidence intervals at a known finite-sample rate. The paper's answer: the projected averaged error is within $O((\log n)^{5/2}n^{-1/4})$ of a Gaussian in Kolmogorov distance, and the multiplier subsample bootstrap reproduces the true sampling distribution to within $O(\log n \cdot n^{-1/10})$ with probability at least $1 - 1/n$. If correct, these are the first non-asymptotic guarantees for bootstrap-based confidence intervals in stochastic approximation with Markov noise, so a practitioner obtains an explicit accuracy certificate for the interval rather than an appeal to asymptotic normality.

What carries the argument

The argument turns on four devices. First, the Poisson equation of the chain: with $\hat\varepsilon(z) = \sum_{k\ge 0} P^k\varepsilon(z)$ solving $\hat\varepsilon - P\hat\varepsilon = \varepsilon$, the averaged error is rewritten as a martingale-difference sum plus remainder terms, so a quantitative martingale central limit theorem applied at $p = \log n$ yields the Gaussian approximation. Second, a perturbation expansion $\theta_k - \theta^* = \Gamma_{1:k}(\theta_0-\theta^*) + J_k^{(0)} + H_k^{(0)}$ separates the linear-in-noise term $J_k^{(0)}$, which is analyzed exactly, from higher-order corrections $H_k^{(0)}$; the products $\Gamma_{1:k}$ are exponentially stable in the $Q$-norm of the Lyapunov equation $\bar A^\top Q + Q\bar A = P$, which makes the corrections small provided $k_0$ dominates $(\log n)^{1/\gamma}$ (Assumption A3). Third, the bootstrap statistic is exactly Gaussian conditional on the data, with variance $\hat\sigma^2_\theta(u)$; Proposition 2 shows this variance equals an overlapping batch-mean estimate of the noise's asymptotic variance plus a controlled remainder, and a concentration bound for that quadratic statistic controls the error. Fourth, a comparison lemma for one-dimensional Gaussians converts the variance error into a distributional error. Balancing the Gaussian-approximation error against the variance-estimation error fixes the optimal hyperparameters $b_n = \lceil n^{4/5}\rceil$ and $\gamma = 3/5$, and that balance is what produces the $n^{-1/10}$ rate of Theorem 2.

What would settle it

Simulate the Garnet TD benchmark described in the paper (or any LSA problem satisfying A1–A2) at increasing sample sizes $n$, using $b_n = \lceil n^{4/5}\rceil$ and $\alpha_k = c_0/(k+k_0)^{3/5}$ with $k_0$ fixed per A3, and estimate $\sup_x |P(\sqrt{n}u^\top(\bar\theta_n-\theta^*) \le x) - P_b(\bar\theta_{n,b_n}(u) \le x)|$ by Monte Carlo across many independent runs. If the log-log slope of this error against $n$ is materially worse than $-1/10$ (after removing the $\log n$ factor), the rate in Theorem 2 is contradicted; a cheaper check targets Corollary 2, where the overlapping batch-mean variance error's log-log slope should be about $-1/8$ when $\gamma = 1/2+\epsilon$.

Watch

Extended reading notes

Core claim

The paper's central claim is that statistical inference for Polyak–Ruppert averaged linear stochastic approximation is feasible under Markov noise with explicit finite-sample accuracy. For any unit direction $u$, Corollary 1 bounds the Kolmogorov distance between $\sqrt{n}u^\top(\bar\theta_n - \theta^*)/\sigma(u)$ and the standard normal by $O((\log n)^{5/2}n^{-1/4})$ when step sizes decay as $\alpha_k = c_0/(k+k_0)^{3/4}$, with Theorem 1 first establishing the same control against the data-dependent variance $\sigma^2_n(u)$. Theorem 2 then certifies the multiplier subsample bootstrap: for block size $b_n = \lceil n^{4/5}\rceil$, step-size exponent $\gamma = 3/5$, and with probability at least $1-1/n$, $\sup_x |P(\sqrt{n}(\bar\theta_n-\theta^*)^\top u \le x) - P_b(\bar\theta_{n,b_n}(u) \le x)| \lesssim \log n \cdot n^{-1/10}$, so confidence intervals for $u^\top\theta^*$ built from the bootstrap hold up to that error. As a byproduct of the same variance analysis, the authors recover the classical $O(n^{-1/8})$ rate, up to logarithmic factors, for overlapping batch-mean estimation of the asymptotic variance $\sigma^2(u)$.

Load-bearing premise

The load-bearing premise is that the step-size offset $k_0$ is tuned before any data is seen to exceed a constant times $(\log n)^{1/\gamma}$, with the constant depending on how quickly the underlying Markov chain forgets its past and on the geometry of the linear system — so the total sample size $n$ and the problem constants must be known in advance, and the schedule cannot be chosen adaptively.

Editorial extensions

If this is right

Confidence intervals for $u^\top\theta^*$ built from the multiplier subsample bootstrap carry an explicit accuracy certificate: with block size $\lceil n^{4/5}\rceil$, step-size exponent $3/5$, and probability at least $1 - 1/n$, the coverage error relative to the exact sampling distribution is $O(\log n \cdot n^{-1/10})$.
The Gaussian-approximation rate $O((\log n)^{5/2}n^{-1/4})$ matches, up to logarithms, the previous $O(\log n \cdot n^{-1/4})$ convex-distance bound that was restricted to TD learning under Markov noise [84], and it improves the general-LSA Markov-noise rate of [74], which gives only order $n^{-1/12}$ in Kolmogorov distance.
Overlapping batch-mean estimation of the asymptotic variance $\sigma^2(u)$ for LSA under Markov noise attains the classical $n^{-1/8}$ rate up to $n^{\epsilon}$ factors, the rate previously established for batch-mean estimators in i.i.d.-noise SGD [16]; this requires the step-size exponent $\gamma$ to sit close to $1/2$, which is exactly why the bootstrap's optimal schedule differs from the varian
For temporal-difference learning with linear function approximation in policy evaluation, all standing assumptions are verified with explicit constants (Proposition 4), so Theorem 2's $n^{-1/10}$ bootstrap guarantee applies to TD as implemented in practice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A plugin corollary the authors do not state as a theorem: because the bootstrap statistic is Gaussian conditional on the data, their proof reduces bootstrap validity to variance estimation plus a Gaussian comparison, so a normal confidence interval using the same overlapping batch-mean variance estimate should achieve the same $n^{-1/10}$ coverage accuracy without resampling.
The requirement of Assumption A3 that $n$ be known before the run could likely be relaxed by a doubling-horizon schedule — restart the averaging with $k_0$ set for the doubled horizon whenever the budget grows — preserving the rates up to a logarithmic factor and yielding a streaming procedure; the paper does not discuss this.
Theorem 1 is stated for one-dimensional projections, but the authors note that only the control of the remainder term prevents a multivariate statement; a multivariate Berry–Esseen version in convex distance, with rate degrading polynomially in dimension, appears reachable with the same Poisson-equation decomposition.
The optimal step-size exponent depends on the inferential target: $3/4$ for pure Gaussian approximation (Remark 1), near $1/2$ for variance estimation (Corollary 2), and $3/5$ for bootstrap coverage (Theorem 2) — so the 'best' schedule is set by the intended use of the iterates, not by their convergence.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know about arXiv:2505.19102. First, it is a real contribution: the first non-asymptotic Berry-Esseen bound (n^{-1/4}, Kolmogorov) for Polyak-Ruppert averaged LSA with Markov noise, and the first non-asymptotic validity rate (n^{-1/10}) for the multiplier subsample bootstrap in that setting. The proof structure - Poisson decomposition, martingale CLT, remainder moment bounds, Gaussian comparison - is coherent, and the appendix is serious. Second, the manuscript as printed has at least two statement-level defects that a referee must insist be fixed. Theorem 1's Eq (9) contains terms n^{gamma-1/2} and a bare initial-condition term; for the recommended gamma=3/4, these do not vanish. The appendix Proposition 5 has the correct n^{1/2-gamma} exponents, so Eq (9) is likely a typo, but as printed it cannot be verified. More load-bearing, Section 4's Proposition 2 defines the batch means from epsilon alone and claims that the estimated variance equals the resulting estimator plus a small remainder. That OBM estimator cannot be consistent for the asymptotic variance which includes the inverse of the averaged matrix; the matrix factor is missing. The appendix F.1 uses the corrected definition, so the intended argument is probably repairable, but the proof of Theorem 2 does not follow from the Section 4 definitions.

The paper does several things well. It positions itself accurately against [74] (n^{-1/12} Kolmogorov via Wasserstein), [84] (TD-only), and [69,72] (iid noise). The authors explicitly flag the restriction that k0 must be chosen knowing n in advance. The numerical experiment is minimal, but the paper is theoretical and the simulation is just an illustration.

The main soft spots, beyond the statement-level defects: the proof depends heavily on a large body of same-author lemmas and a concurrent arXiv paper for concentration of overlapping batch means. That is not improper, but it makes the paper hard to verify without assembling six references. The constants are problem-dependent and not fully explicit; acceptable for this line of work. The results are for one-dimensional projections only; the d-dimensional extension is left open.

Overall: central arguments hold up if the appendix corrections are taken as intended. This deserves a serious referee, not a desk reject. I would send it out and expect heavy revision, primarily to align the main text with the appendix and fix Eq (9).

Referee Report

2 major / 6 minor

Summary. The paper develops non-asymptotic distributional inference for Polyak–Ruppert averaged linear stochastic approximation (LSA) iterates when the noise sequence (Z_k) is a uniformly geometrically ergodic Markov chain. Under assumptions A1–A3 (boundedness and centering of the observations, Hurwitz mean matrix, step sizes α_k = c0/(k+k0)^γ with k0 chosen depending on n), Theorem 1 and Corollary 1 give a Berry–Esseen bound in Kolmogorov distance for the projected error √n u^T(θbar_n − θ*), of order n^{−1/4} up to logarithmic factors at γ = 3/4. Section 4 analyzes a multiplier subsample bootstrap with overlapping batch means: Proposition 2 reduces the bootstrap variance to an OBM statistic plus a remainder, Proposition 3 provides moment bounds for the OBM estimator, and Theorem 2 claims bootstrap validity at rate n^{−1/10} (up to log n) with block length b_n = ⌈n^{4/5}⌉ and γ = 3/5. Section 5 specializes the results to TD learning with linear function approximation, with numerical coverage experiments on a Garnet problem. The proofs combine Poisson-equation martingale decompositions, quantitative martingale CLTs, remainder moment bounds, and Gaussian comparison.

Significance. If the stated results hold, the paper provides the first non-asymptotic guarantee for the coverage accuracy of bootstrap-based confidence intervals in stochastic approximation with Markov noise, at an explicit polynomial rate (n^{−1/10}), together with an n^{−1/4} Kolmogorov-rate Berry–Esseen bound that improves on existing Wasserstein-based rates in this setting. The proof strategy is a genuine derivation rather than a fitted claim: the Gaussian and bootstrap bounds are obtained from a Poisson-equation decomposition, a quantitative martingale CLT, and explicit moment bounds for the remainder terms, with constants expressed through defined problem parameters; the appendix also includes reproducible code for the experiments. The reuse of the authors' earlier Lyapunov and OBM concentration results is appropriate and clearly cited. The main caveat is that the current main text of Section 4 states Propositions 2 and 3 with an incorrect definition (see Major Comment 1), so the significance of the bootstrap result rests on the corrected version in Appendix F.1.

major comments (2)

[Section 4, Proposition 2 (and Appendix F.1)] The main text defines Wbar_{b_n,t} = b_n^{−1} Σ_{ℓ=t+1}^{t+b_n} ε(Z_ℓ) and Wbar_n = n^{−1} Σ_{ℓ=1}^{n−1} ε(Z_ℓ), so that σ^2_ε-hat(u) is an overlapping batch mean (OBM) statistic for u^T Σ_ε u. However, block means of LSA iterates satisfy θbar_{b_n,t} − θ* ≈ −Abar^{−1} εbar_{b_n,t}, so the OBM estimator of the target variance σ^2(u) = u^T Abar^{−1} Σ_ε Abar^{−T} u must be built from Abar^{−1}ε(Z), not from ε(Z). The appendix proof of Proposition 2 indeed uses the corrected definitions Wbar_{b_n,t} = −(1/b_n) Σ_{k=1}^{b_n−1} Abar^{−1}ε(Z_{k+t}) and Wbar_n = −(1/n) Σ_{k=1}^{n−1} Abar^{−1}ε(Z_k). As printed, the identity σ^2_θ-hat(u) = σ^2_ε-hat(u) + R_var(u) is false with a remainder of the claimed magnitude, since R_var(u) would have to contain the non-vanishing deterministic term u^T(Abar^{−1}Σ_ε Abar^{−T} − Σ_ε)u. This is load-bearing: the proof of Theorem 2 identifies σ^2_θ-hat with the OBM estimator of σ^2(u) via Propositions 2 and 3, so the main text must be corrected to match Appendix F.1, and the statements of Propositions 2 and 3 must be re-examined under the corrected definition.
[Theorem 1, Eq. (9)] As printed, B_n contains the term C_D^1 ‖θ_0 − θ*‖ with no factor decaying in n, and the terms C_D^3 (log n)^2 / n^{γ−1/2} and C_D^4 (log n)^{5/2} / n^{γ−1/2} diverge at γ = 3/4 (they scale as n^{1/4}). This contradicts Remark 1, which states that γ = 3/4 is the optimal choice and yields rate n^{−1/4}, and it contradicts Proposition 5 in Appendix C, whose final bound is (C_D^1 ‖θ_0 − θ*‖ + C_D^2) n^{−1/2} + C_D^3 (log n)^2 n^{1/2−γ} + C_D^4 (log n)^{5/2} n^{1/2−γ}. As printed, Theorem 1 and Corollary 1 do not assert a vanishing error, so Eq. (9) must be corrected: the n^{−1/2} factor should multiply the initial-condition term, and the exponents in the last two terms should be 1/2 − γ.

minor comments (6)

[Section 3 (after A3)] Since k_0 must be chosen as g(a, t_mix, c0, C_A, κ_Q, α_∞)(log n)^{1/γ}, the step-size schedule depends on the total sample size n before the data are collected; the authors acknowledge this, but the paper would benefit from a remark on how the rates degrade if k_0 is fixed in advance (for example, via a doubling or burn-in scheme).
[Theorem 2, proof sketch] The displayed rates in the in-text proof are difficult to parse and appear to have exponent/sign errors (for instance, a term of the form b_n^{1/2} n^{1−γ/2} would diverge for γ = 3/5); please align the displayed formula with the derivation in Appendix F.3 and with the stated n^{−1/10} rate.
[Section 4 (before Proposition 2)] The notation for the block means is inconsistent (Wbar_{b_n,t} in the definition of σ^2_ε-hat(u) versus Wbar_{n,b_n,t} in the displayed formula), and the summation ranges differ between the main text and Appendix F.1; please unify the notation and index ranges.
[Appendix H, Lemma 36] The bound relies on 'Theorem 4.4.3' from [32], but the reference entry is incomplete and the year '2015' appears to be a reprint date; please replace this with a standard incomplete-gamma inequality or give a complete citation.
[Table 2] The caption and column headers do not state how the oracle coverage based on σ^2(u) is computed in the Garnet experiment, nor what 'OBM estimation' refers to in this table; a brief protocol sentence would improve reproducibility.
[Section 5, Proposition 4] The proof text refers to 'the noise-level condition 2', but no numbered condition 2 appears in the manuscript; please update the cross-reference.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: Gaussian and bootstrap bounds are proved, not fitted; same-author citations are independent support; the printed Proposition 2 mismatch is a correctness issue, not circularity.

full rationale

The central derivation chain is self-contained rather than circular. Theorem 1's Gaussian approximation is obtained by expanding the LSA error into a linear statistic W plus remainder terms D1, D2, applying a martingale central limit theorem (Proposition 13) and explicit moment bounds on D; the Gaussian limit is not inserted by assumption, and sigma_n(u) is computed from the same coefficients Q_l appearing in the expansion. Corollary 1 then controls the comparison between sigma_n(u) and sigma(u) via an explicit bound (Lemma 9), so the n^{-1/4} Kolmogorov rate is derived rather than assumed. Theorem 2's bootstrap validity is likewise a three-step chain: Corollary 1 for Gaussian approximation, Lemma 20 for Gaussian comparison, and the variance-estimation step |hat_sigma_theta^2 - sigma^2|. That variance step is proved through the decomposition hat_sigma_theta^2 = hat_sigma_epsilon^2 + R_var, with the appendix (F.1) defining the block means with bar A^{-1} epsilon, the correct object for Sigma_infty, and bounding R_var via Lemmas 15-19. Thus the target variance sigma^2(u)=u^top bar A^{-1} Sigma_epsilon bar A^{-top} u is not put in by definition; it is identified through an expansion of the LSA block means. The main-text statement of Proposition 2 defines bar W from epsilon without bar A^{-1}; as printed it is internally inconsistent with the appendix proof, but this is a correctness/consistency defect, not circularity. The paper also relies on same-author prior results: [69] for the Lyapunov contraction (Proposition 1), [26] for random matrix-product stability (Proposition 10), [25] for Rosenthal inequalities (Lemma 24), and [51] for overlapping-batch-mean concentration (Proposition 3). These are cited theorems with their own assumptions (A1/A2) that do not include the paper's bootstrap or Berry-Esseen conclusions; they are not uniqueness theorems invoked to forbid alternatives, and no ansatz is smuggled in via citation. The choices b_n = ceil(n^{4/5}) and gamma = 3/5 are obtained by optimizing the proved upper bound, not by fitting to the target distribution. Assumption A3 requires k0 to depend on n and problem constants; the paper explicitly acknowledges this tuning limitation, but it is an assumption on the algorithm's input, not a definitional identification of a predicted quantity with a fitted one.

Assumptions & free parameters 4 free parameters · 8 assumptions · 0 invented entities

No new physical or mathematical entities are introduced. The free parameters are algorithm tuning choices, not fitted constants. The central proof relies on standard martingale and Lyapunov machinery plus two same-author black-box results ([51] and technical lemmas from [23,25,26]); these are independent theorems whose assumptions do not include the target result.

free parameters (4)

gamma (step-size exponent) = 3/5 (Theorem 2), 3/4 (Remark 1), 1/2+epsilon (Corollary 2)
Hand-chosen to balance terms in the bound; not fitted to data, but the theorem's rate and the trade-off depend on it.
b_n (block length) = ceil(n^{4/5}) (Theorem 2), ceil(n^{3/4}) (Corollary 2)
Chosen to optimize the variance-estimation versus Gaussian-approximation trade-off; the bootstrap proof requires b_n to grow at least like n^gamma.
c0 (step-size scale) = <= 1/(2a), otherwise unspecified
Constrained by the Lyapunov contraction condition; no exact value is needed for the results.
k0 (burn-in offset) = >= g(a,tmix,c0,...)(log n)^{1/gamma}
Must be chosen with knowledge of n and problem constants; controls decay of the initial-condition term and matrix-product stability.

assumptions (8)

domain assumption A1: the Markov chain (Z_k) is uniformly geometrically ergodic with dtv(P^k(z,.), P^k(z',.)) <= (1/4)^{ceil(k/tmix)}.
Used throughout for Poisson equation solvability, Rosenthal and McDiarmid inequalities, and coupling arguments; without it the remainder terms D1 and D2 cannot be controlled.
domain assumption A2: the noise epsilon(z) and matrices A(z) are bounded, -Abar is Hurwitz, and lambda_min(Sigma_epsilon) > 0.
Gives existence and uniqueness of theta*, Lyapunov contraction in Q-norm, boundedness of the Poisson solution, and a well-defined asymptotic covariance Sigma_infinity.
ad hoc to paper A3/A'3: step sizes alpha_k = c0/(k+k0)^gamma with gamma in [1/2,1), c0 <= 1/(2a), and k0 >= g(...)(log n)^{1/gamma}.
Imposed to make the initial-condition term and product-stability estimates small; requires knowing n and problem constants in advance.
standard math Lyapunov equation: for -Abar Hurwitz, there exists Q > 0 solving Abar^T Q + Q Abar = P with contraction ||I - alpha Abar||_Q <= 1 - alpha a.
Proposition 1, with a proof sketched in Appendix E.3; classical Lyapunov theory.
standard math Quantitative Berry-Esseen for martingale difference sequences, as in Bolthausen [12] and Fan [28].
Used in Proposition 13 to obtain the O(n^{-1/4}) and O(n^{-1/2}) terms in the Gaussian approximation bound.
domain assumption Concentration inequality for overlapping batch means of Markov chains, [51, Theorem 1].
Black-box cited result by the same authors; supplies Proposition 3. Its assumptions are A1/A2 and do not include the paper's target bootstrap claim.
standard math Berbee coupling for beta-mixing sequences, used to construct nearly independent copies Z*_jm+i.
Used in the proof of Proposition 9 to bound the term J^(1)_k via block coupling and mixing coefficient control.
domain assumption TD1: P_pi is uniformly geometrically ergodic; TD2: design matrix Sigma_phi is non-degenerate and the feature map is bounded.
Needed to instantiate LSA assumptions for the TD learning application in Section 5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Statistical inference for Linear Stochastic Approximation with Markovian Noise." pith.science (2026). https://pith.science/paper/3ORFSKVW

@misc{pith2026250519102,
  author       = {Pith},
  title        = {Pith review of: Statistical inference for Linear Stochastic Approximation with Markovian Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3ORFSKVW}},
  note         = {Machine review of arXiv:2505.19102}
}

abstract

In this paper we derive non-asymptotic Berry-Esseen bounds for Polyak-Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields $\mathcal{O}(n^{-1/4})$ convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the non-asymptotic validity of a multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of bootstrap-based confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order $\mathcal{O}(n^{-1/8})$ up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization
stat.ML 2026-04 unverdicted novelty 6.0 of 10

Q-learning with PD2Z/LD2Z step sizes admits sharp non-asymptotic bounds, a tail Polyak–Ruppert CLT, and a time-uniform Gaussian approximation, establishing a best-of-both-worlds rate-and-bias tradeoff.

Reference graph

Works this paper leans on

94 extracted references · 68 canonical work pages · cited by 1 Pith paper

[74]

Gaussian approximatio n and multiplier bootstrap for stochastic gradient descent

Marina Sheshukova, Sergey Samsonov, Denis Belomestny , Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian approximatio n and multiplier bootstrap for stochastic gradient descent. arXiv preprint arXiv:2502.06719 , 2025

arXiv 2025
[84]

On the relationship between batch means, overlapping means and spectral estimation

Peter D Welch. On the relationship between batch means, overlapping means and spectral estimation. In Proceedings of the 19th conference on Winter simulation , pages 320–323, 1987

work page 1987
[1]

High-dimensional central limit theorems for linear functionals of online lea st-squares sgd

Bhavya Agrawalla, Krishnakumar Balasubramanian, and P romit Ghosal. High-dimensional central limit theorems for linear functionals of online lea st-squares sgd. arXiv preprint arXiv:2302.09727, 2023

arXiv 2023
[2]

On a per turbation approach for the analysis of stochastic tracking algorithms

Raﬁk Aguech, Eric Moulines, and Pierre Priouret. On a per turbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization , 39(3):872–899, 2000

2000
[3]

Andreas Anastasiou, Krishnakumar Balasubramanian, an d Murat A. Erdogdu. Normal approx- imation for stochastic gradient descent via non-asymptoti c rates of martingale CLT. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learn- ing Theory, volume 99 of Proceedings of Machine Learning Research, pages 115–137. PM...

2019
[4]

On the generat ion of markov decision processes

TW Archibald, KIM McKinnon, and LC Thomas. On the generat ion of markov decision processes. Journal of the Operational Research Society , 46(3):354–361, 1995

1995
[5]

A martingale decomp osition for quadratic forms of Markov chains (with applications)

Yves F Atchadé and Matias D Cattaneo. A martingale decomp osition for quadratic forms of Markov chains (with applications). Stochastic Processes and their Applications , 124(1):646– 677, 2014

2014
[6]

Barsov and V

S. Barsov and V . Ulyanov. Estimates for the closeness of G aussian measures. Dokl. Akad. Nauk SSSR, 291(2):273–277, 1986

1986

Show all 94 references

[7]

V . Bentkus. On the dependence of the Berry–Esseen bound o n dimension. Journal of Statistical Planning and Inference, 113(2):385–402, 2003

2003
[8]

Benveniste, M

A. Benveniste, M. Métivier, and P . Priouret. Adaptive algorithms and stochastic approxima- tions, volume 22. Springer Science & Business Media, 2012

2012
[9]

Edgeworth expan sions of suitably normalized sample mean statistics for atomic markov chains

Patrice Bertail and Stéphan Clémençon. Edgeworth expan sions of suitably normalized sample mean statistics for atomic markov chains. Probability Theory and Related Fields , 130(3):388– 414, 2004

2004
[10]

Bhandari, D

J. Bhandari, D. Russo, and R. Singal. A ﬁnite time analys is of temporal difference learning with linear function approximation. In Conference On Learning Theory , pages 1691–1692, 2018

2018
[11]

Bolthausen

E. Bolthausen. The berry-esseén theorem for strongly m ixing harris recurrent markov chains. Zeitschrift für W ahrscheinlichkeitstheorie und V erwandte Gebiete, 60(3):283–289, 1982

1982
[12]

Bolthausen

E. Bolthausen. Exact Convergence Rates in Some Marting ale Central Limit Theorems. The Annals of Probability, 10(3):672 – 688, 1982

1982
[13]

The berry-esseen theorem for functi onals of discrete markov chains

Erwin Bolthausen. The berry-esseen theorem for functi onals of discrete markov chains. Zeitschrift für W ahrscheinlichkeitstheorie und verwandte Gebiete, 54(1):59–73, 1980

1980
[14]

Stochastic Approximation: A Dynamical Systems Viewpoint

Vivek S Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint . Cambridge University Press, 2008

2008
[15]

Statistical infere nce for online decision making via stochastic gradient descent

Haoyu Chen, Wenbin Lu, and Rui Song. Statistical infere nce for online decision making via stochastic gradient descent. Journal of the American Statistical Association , 116(534):708– 719, 2021

2021
[16]

Lee, Xin T

Xi Chen, Jason D. Lee, Xin T. Tong, and Yichen Zhang. Stat istical inference for model param- eters in stochastic gradient descent. The Annals of Statistics , 48(1):251 – 273, 2020

2020
[17]

Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensiona l random vectors

Victor Chernozhukov, Denis Chetverikov, and Kengo Kat o. Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensiona l random vectors. Ann. Statist. , 41(6):2786–2819, 2013

2013
[18]

Central limit theorems and boot- strap in high dimensions

Victor Chernozhukov, Denis Chetverikov, and Kengo Kat o. Central limit theorems and boot- strap in high dimensions. Annals of Probability, 45(4):2309–2352, 2017. 11

2017
[19]

Strong consistency and other properti es of the spectral variance estimator

Halim Damerdji. Strong consistency and other properti es of the spectral variance estimator. Management Science, 37(11):1424–1440, 1991

1991
[20]

The tot al variation distance between high-dimensional gaussians with the same mean

Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The tot al variation distance between high-dimensional gaussians with the same mean. arXiv preprint arXiv:1810.08693 , 2018

2018 arXiv
[21]

Br idging the gap between constant step size stochastic gradient descent and Markov chains

A ymeric Dieuleveut, Alain Durmus, and Francis Bach. Br idging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics , 48(3):1348 – 1382, 2020

2020
[22]

R. Douc, E. Moulines, P . Priouret, and P . Soulier.Markov chains. Springer Series in Operations Research and Financial Engineering. Springer, 2018

2018
[23]

Finite-time high- probability bounds for Polyak–Ruppert averaged iterates o f linear stochastic approximation

Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time high- probability bounds for Polyak–Ruppert averaged iterates o f linear stochastic approximation. Mathematics of Operations Research, 50(2):935–964, 2025

2025
[24]

Tight high probability bounds for linear stochastic ap proximation with ﬁxed stepsize

Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Sam sonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic ap proximation with ﬁxed stepsize. In M. Ranzato, A. Beygelzimer, K. Nguyen, P . S. Liang, J. W . V aughan, and Y . Dauphin, editors,...

2021
[25]

Rosenthal-type inequalities for linear statistics of mark ov chains

Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Sam sonov, and Marina Sheshukova. Rosenthal-type inequalities for linear statistics of mark ov chains. arXiv preprint arXiv:2303.05838, 2023

2023
[26]

On the stability of random matrix product with markovian noise: Ap plication to linear stochastic ap- proximation and td learning

Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Sam sonov, and Hoi-To Wai. On the stability of random matrix product with markovian noise: Ap plication to linear stochastic ap- proximation and td learning. In Mikhail Belkin and Samory Kp otufe, editors, Proceedings of Thirt...

2021
[27]

Bootstrap methods: another look at the j ackknife

Bradley Efron. Bootstrap methods: another look at the j ackknife. In Breakthroughs in statistics: Methodology and distribution, pages 569–593. Springer, 1992

1992
[28]

Exact rates of convergence in some marting ale central limit theorems

Xiequan Fan. Exact rates of convergence in some marting ale central limit theorems. Journal of Mathematical Analysis and Applications , 469(2):1028–1044, 2019

2019
[29]

Online bootstrap con ﬁdence intervals for the stochastic gradient descent estimator

Y uan Fang, Jing Xu, and Lijun Y ang. Online bootstrap con ﬁdence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research , 19(78):1–21, 2018

2018
[30]

Flegal and Galin L

James M. Flegal and Galin L. Jones. Batch means and spect ral variance estimators in Markov chain Monte Carlo. Ann. Statist., 38(2):1034–1070, 04 2010

2010
[31]

G. Fort. Central limit theorems for stochastic approxi mation with controlled Markov chain dynamics. ESAIM: PS, 19:60–80, 2015

2015
[32]

Neue herleitung und explizite restab schätzung der riemann-siegel-formel

Wolfgang Gabcke. Neue herleitung und explizite restab schätzung der riemann-siegel-formel. 2015

2015
[33]

Off-policy lear ning with eligibility traces: a survey

Matthieu Geist, Bruno Scherrer, et al. Off-policy lear ning with eligibility traces: a survey. J. Mach. Learn. Res., 15(1):289–333, 2014

2014
[34]

Matrix concentration for products

De Huang, Jonathan Niles-Weed, Joel A Tropp, and Rachel Ward. Matrix concentration for products. F oundations of Computational Mathematics, pages 1–33, 2021

2021
[35]

Quantitative limit theor ems and bootstrap approximations for empirical spectral projectors

Moritz Jirak and Martin Wahl. Quantitative limit theor ems and bootstrap approximations for empirical spectral projectors. 2022. arXiv:2202.08669

2022 arXiv
[36]

Effective Berry-Esseen and concent ration bounds for Markov chains with a spectral gap

Benoît Kloeckner. Effective Berry-Esseen and concent ration bounds for Markov chains with a spectral gap. Ann. Appl. Probab., 29(3):1778–1807, 2019

2019
[37]

Actor-critic algorit hms

Vijay Konda and John Tsitsiklis. Actor-critic algorit hms. Advances in neural information processing systems, 12, 1999. 12

1999
[38]

The jackknife and the bootstrap for gener al stationary observations

Hans R Kunsch. The jackknife and the bootstrap for gener al stationary observations. The annals of Statistics, 17(3):1217–1241, 1989

1989
[39]

Stochastic approximation and recursive algorithms and applications, volume 35

Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003

2003
[40]

C.r Lakshminarayanan and Csaba Szepesvari. Linear sto chastic approximation: How far does constant step-size and iterate averaging go? In Amos Storke y and Fernando Perez-Cruz, ed- itors, Proceedings of the Twenty-First International Conference on Artiﬁcial Intelligence and St...

2018
[41]

Online stati stical inference for nonlinear stochas- tic approximation with Markovian data

Xiang Li, Jiadong Liang, and Zhihua Zhang. Online stati stical inference for nonlinear stochas- tic approximation with Markovian data. arXiv preprint arXiv:2302.07690 , 2023

2023 arXiv
[42]

A statistical analysis of Polyak-Ruppert averaged Q-learning

Xiang Li, Wenhao Y ang, Jiadong Liang, Zhihua Zhang, and Michael I Jordan. A statistical analysis of Polyak-Ruppert averaged Q-learning. In International Conference on Artiﬁcial Intelligence and Statistics , pages 2207–2261. PMLR, 2023

2023
[43]

Statistical infe rence with Stochastic Gradient Meth- ods under φ-mixing Data

Ruiqi Liu, Xi Chen, and Zuofeng Shang. Statistical infe rence with Stochastic Gradient Meth- ods under φ-mixing Data. arXiv preprint arXiv:2302.12717 , 2023

2023
[44]

Multiplier subsample bootstr ap for statistics of time series

Ruru Ma and Shibin Zhang. Multiplier subsample bootstr ap for statistics of time series. J. Statist. Plann. Inference, 233:Paper No. 106183, 15, 2024

2024
[45]

Exact converge nce rates in the central limit theorem for a class of martingales

Mohamed El Machkouri and Lahcen Ouchti. Exact converge nce rates in the central limit theorem for a class of martingales. Bernoulli, 13(4):981–999, 2007

2007
[46]

Overlapping batch m eans: Something for nothing? Technical report, Institute of Electrical and Electronics Engineers (IEEE), 1984

Marc S Meketon and Bruce Schmeiser. Overlapping batch m eans: Something for nothing? Technical report, Institute of Electrical and Electronics Engineers (IEEE), 1984

1984
[47]

Conver gence rate and averaging of nonlin- ear two-time-scale stochastic approximation algorithms

Abdelkader Mokkadem, Mariane Pelletier, et al. Conver gence rate and averaging of nonlin- ear two-time-scale stochastic approximation algorithms. The Annals of Applied Probability , 16(3):1671–1702, 2006

2006
[48]

On linear stochastic approximation: Fine-grained polyak- ruppert and non-asymptotic concen- tration

Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Pete r L Bartlett, and Michael I Jordan. On linear stochastic approximation: Fine-grained polyak- ruppert and non-asymptotic concen- tration. In Conference on Learning Theory , pages 2947–2997. PMLR, 2020

2020
[49]

Optimal and instance-dependent guarantees for markovian linear stoch astic approximation

Wenlong Mou, Ashwin Pananjady, Martin J Wainwright, an d Peter L Bartlett. Optimal and instance-dependent guarantees for markovian linear stoch astic approximation. arXiv preprint arXiv:2112.12770, 2021

2021 arXiv
[50]

Non-asymptotic analys is of stochastic approximation algo- rithms for machine learning

Eric Moulines and Francis Bach. Non-asymptotic analys is of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems , 24:451–459, 2011

2011
[51]

A no te on concentration inequali- ties for the overlapped batch mean variance estimators for M arkov chains

Eric Moulines, Alexey Naumov, and Sergey Samsonov. A no te on concentration inequali- ties for the overlapped batch mean variance estimators for M arkov chains. arXiv preprint arXiv:2505.08456, 2025

2025 arXiv
[52]

Bootstrap conﬁdence sets for spectral projectors of sample covariance

Alexey Naumov, Vladimir Spokoiny, and Vladimir Ulyano v. Bootstrap conﬁdence sets for spectral projectors of sample covariance. Probability Theory and Related Fields , 174(3- 4):1091–1132, 2019

2019
[53]

Robust stochas- tic approximation approach to stochastic programming

Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, an d Alexander Shapiro. Robust stochas- tic approximation approach to stochastic programming. SIAM Journal on optimization , 19(4):1574–1609, 2009

2009
[54]

Osekowski

A. Osekowski. Sharp Martingale and Semimartingale Inequalities. Monograﬁe Matematyczne
[55]

Finite time analysis of temporal difference learning with linear function approxi mation: Tail averaging and regulari- sation

Gandharv Patil, LA Prashanth, Dheeraj Nagaraj, and Doi na Precup. Finite time analysis of temporal difference learning with linear function approxi mation: Tail averaging and regulari- sation. In International Conference on Artiﬁcial Intelligence and St atistics, pages 5438–54...

2023
[56]

Concentration inequalities for Markov chains by Marton couplings and spectral methods

Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20(none):1 – 32, 2015

2015
[57]

V . Petrov. Sums of Independent Random V ariables . Ergebnisse der Mathematik und ihrer Grenzgebiete. 2. Folge. Springer Berlin Heidelberg, 1975

1975
[58]

Optimum Bounds for the Distributions of Martingales in Banach Spaces

Iosif Pinelis. Optimum Bounds for the Distributions of Martingales in Banach Spaces. The Annals of Probability, 22(4):1679 – 1706, 1994

1994
[59]

Acceleration of s tochastic approximation by averaging

Boris T Polyak and Anatoli B Juditsky. Acceleration of s tochastic approximation by averaging. SIAM journal on control and optimization , 30(4):838–855, 1992

1992
[60]

Making gradient descent optimal for strongly convex stochastic optimization

Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan . Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning , pages 1571–1578, 2012

2012
[61]

Online bootstrap inference for policy evaluation in reinforcement learning

Pratik Ramprasad, Y uantong Li, Zhuoran Y ang, Zhaoran W ang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer . Statist. Assoc., 118(544):2901–2914, 2023

2023
[62]

E. Rio. Asymptotic Theory of W eakly Dependent Random Processes. Springer, 2017

2017
[63]

Rosenthal

H. Rosenthal. On the subspaces of Lp (p > 2) spanned by sequences of independent random variables. Israel J. Math., 8:273–303, 1970

1970
[64]

Fundamentals of Stein’s method

Nathan Ross. Fundamentals of Stein’s method. Probab. Surv., 8:210–293, 2011

2011
[65]

Onlin e covariance estimation for stochas- tic gradient descent under Markovian sampling

Abhishek Roy and Krishnakumar Balasubramanian. Onlin e covariance estimation for stochas- tic gradient descent under Markovian sampling. arXiv preprint arXiv:2308.01481 , 2023

2023 arXiv
[66]

The bayesian bootstrap

Donald B Rubin. The bayesian bootstrap. The annals of statistics , pages 130–134, 1981

1981
[67]

Efﬁcient estimations from a slowly conv ergent robbins-monro process

David Ruppert. Efﬁcient estimations from a slowly conv ergent robbins-monro process. Tech- nical report, Cornell University Operations Research and I ndustrial Engineering, 1988

1988
[68]

On quantitative bounds in the mean marti ngale central limit theorem

Adrian Röllin. On quantitative bounds in the mean marti ngale central limit theorem. Statistics & Probability Letters, 138:171–176, 2018

2018
[69]

Gaussian Approximation and Multiplier Bootstrap for P olyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning

Sergey Samsonov, Eric Moulines, Qi-Man Shao, Zhuo-Son g Zhang, and Alexey Nau- mov. Gaussian Approximation and Multiplier Bootstrap for P olyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning . In Advances in Neural Informa- tion Processing Sy...
[70]

Improved High- Probability Bounds for the Temporal Difference Learning Al gorithm via Exponential Stabil- ity

Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Er ic Moulines. Improved High- Probability Bounds for the Temporal Difference Learning Al gorithm via Exponential Stabil- ity. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Th...
[71]

Berry–Esseen bounds f or multivariate nonlinear statis- tics with applications to M-estimators and stochastic grad ient descent algorithms

Qi-Man Shao and Zhuo-Song Zhang. Berry–Esseen bounds f or multivariate nonlinear statis- tics with applications to M-estimators and stochastic grad ient descent algorithms. Bernoulli, 28(3):1548–1576, 2022

2022
[72]

Birkhäuser Basel, 1 edition, 2012. 13

2012
[73]

Bootstrap conﬁde nce sets under model misspeciﬁca- tion

Vladimir Spokoiny and Mayya Zhilova. Bootstrap conﬁde nce sets under model misspeciﬁca- tion. The Annals of Statistics , 43(6):2653 – 2675, 2015. 14

2015
[75]

Srikant and L

R. Srikant and L. Ying. Finite-Time Error Bounds For Lin ear Stochastic Approximation and TD Learning. In Conference on Learning Theory , 2019

2019
[76]

Rates of Convergence in the Central Limit The orem for Markov Chains, with an Application to TD Learning

R Srikant. Rates of Convergence in the Central Limit The orem for Markov Chains, with an Application to TD Learning. arXiv preprint arXiv:2401.15719 , 2024

2024
[77]

R. S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction . The MIT Press, second edition, 2018

2018
[78]

S Sutton

R. S Sutton. Learning to predict by the methods of tempor al differences. Machine learning , 3(1):9–44, 1988

1988
[79]

Probability in High Dimension

Ramon V an Handel. Probability in High Dimension . APC 550 Lecture Notes, Princeton University, 2016

2016
[80]

J. N. Tsitsiklis and B. V an Roy. An analysis of temporal- difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674–690, May 1997

1997
[81]

Watkins and P

C.topher J.C.H. Watkins and P . Dayan. Technical note: Q -learning. Machine Learning , 8(3):279–292, May 1992

1992
[82]

Online Covariance Ma trix Estimation in Stochastic Gradient Descent

Xi Chen Wanrong Zhu and Wei Biao Wu. Online Covariance Ma trix Estimation in Stochastic Gradient Descent. Journal of the American Statistical Association , 118(541):393–404, 2023

2023
[83]

Statistical Inference for Temporal Difference Learning with Linear Function Approximation

Weichen Wu, Gen Li, Y uting Wei, and Alessandro Rinaldo. Statistical Inference for Temporal Difference Learning with Linear Function Approximation. arXiv preprint arXiv:2410.16106 , 2024

2024 arXiv
[85]

Rates of convergence for empirical processes of stationary mixing sequences

Bin Y u. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 94–116, 1994

1994
[86]

Uncert ainty quantiﬁcation for Markov chains with application to temporal difference learning

Weichen Wu, Y uting Wei, and Alessandro Rinaldo. Uncert ainty quantiﬁcation for Markov chains with application to temporal difference learning. arXiv preprint arXiv:2502.13822 , 2025

2025 arXiv
[88]

Onli ne Bootstrap Inference with Noncon- vex Stochastic Gradient Descent Estimator

Y anjie Zhong, Todd Kuffner, and Soumendra Lahiri. Onli ne Bootstrap Inference with Noncon- vex Stochastic Gradient Descent Estimator. arXiv preprint arXiv:2306.02205 , 2023. 15 A Constants Constant name Description Reference CRm,1 = 60e, CRm,2 = 60 Martingale Rosenthal consta...

2023 arXiv
[89]

Z ∗ jm+i is independent of Fk (j+1)m+i := σ{Z(j+1)m+i, . . . , Zk}
[90]

Pξ(Z ∗ jm+i ⁄= Zjm+i) ≤ 2 (1/4)⌈m/tmix⌉
[91]

We control β-mixing coefﬁcient via total variation distance, see [22, Theorem F.3.3]

Z ∗ jm+i and Zjm+i have the same distribution, (38) The existence of the random variables Z ∗ jm+i is guaranteed by Berbee’s lemma, see e.g [62, Lemma 5.1], together with the fact that uniformly geometrically e rgodic Markov chains are a special in- stance of β-mixing processe...
[92]

+ 0.5(σ2 1/σ2 2 − 1) = 0 .5(σ − log(1 + σ)), where σ = σ2 1/σ2 2 − 1. If σ > −2/3 hence, KL(P1, P2) ≤ 0.5σ2 ≤ 0.5δ2 If σ ≤ −2/3 then TV(P1, P2) ≤ 1 ≤ (3/2)|σ| ≤ (3/2)δ It remains to apply the Pinsker inequality sup x∈R |P(ξ1 ≤ x) − P(ξ2 ≤ x)| ≤ TV(P1, P2) ≤ √ KL(P1, P2) /2 ≤ 3...
[93]

for any p ≥ 2 k∑ i=1 αp i ≤ cp 0 pγ − 1 ,
[94]

, k} k∑ i=m+1 αi ≥ c0 2(1 − γ) ((k + k0)1−γ − (m + k0)1−γ) , Proof

for any m ∈ {0, . . . , k} k∑ i=m+1 αi ≥ c0 2(1 − γ) ((k + k0)1−γ − (m + k0)1−γ) , Proof. To proof 1, note that k∑ i=1 αi ≤ c0 ∫ k+k0 k0 dx xγ ≤ c0 1 − γ ((k + k0)1−γ − k1−γ 0 ) , To proof 2, note that k∑ i=1 αp i ≤ cp 0 ∫ +∞ 1 dx xpγ ≤ cp 0 pγ − 1 , To proof 3, note that for ...
[4547]

PMLR, 30 Jun–03 Jul 2024

2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [74]

Gaussian approximatio n and multiplier bootstrap for stochastic gradient descent

Marina Sheshukova, Sergey Samsonov, Denis Belomestny , Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian approximatio n and multiplier bootstrap for stochastic gradient descent. arXiv preprint arXiv:2502.06719 , 2025

arXiv 2025

[2] [84]

On the relationship between batch means, overlapping means and spectral estimation

Peter D Welch. On the relationship between batch means, overlapping means and spectral estimation. In Proceedings of the 19th conference on Winter simulation , pages 320–323, 1987

work page 1987

[3] [1]

High-dimensional central limit theorems for linear functionals of online lea st-squares sgd

Bhavya Agrawalla, Krishnakumar Balasubramanian, and P romit Ghosal. High-dimensional central limit theorems for linear functionals of online lea st-squares sgd. arXiv preprint arXiv:2302.09727, 2023

arXiv 2023

[4] [2]

On a per turbation approach for the analysis of stochastic tracking algorithms

Raﬁk Aguech, Eric Moulines, and Pierre Priouret. On a per turbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization , 39(3):872–899, 2000

2000

[5] [3]

Andreas Anastasiou, Krishnakumar Balasubramanian, an d Murat A. Erdogdu. Normal approx- imation for stochastic gradient descent via non-asymptoti c rates of martingale CLT. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learn- ing Theory, volume 99 of Proceedings of Machine Learning Research, pages 115–137. PM...

2019

[6] [4]

On the generat ion of markov decision processes

TW Archibald, KIM McKinnon, and LC Thomas. On the generat ion of markov decision processes. Journal of the Operational Research Society , 46(3):354–361, 1995

1995

[7] [5]

A martingale decomp osition for quadratic forms of Markov chains (with applications)

Yves F Atchadé and Matias D Cattaneo. A martingale decomp osition for quadratic forms of Markov chains (with applications). Stochastic Processes and their Applications , 124(1):646– 677, 2014

2014

[8] [6]

Barsov and V

S. Barsov and V . Ulyanov. Estimates for the closeness of G aussian measures. Dokl. Akad. Nauk SSSR, 291(2):273–277, 1986

1986