mlsanityData to 7 Oct 2026

Online covariance estimation for stochastic gradient descent under Markovian sampling

arXiv 2308.01481 ↗First posted 3 Aug 2023math.ST cs.LG math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

We investigate the online overlapping batch-means covariance estimator for Stochastic Gradient Descent (SGD) under Markovian sampling. Convergence rates of order Obig(√d,n-1/8(log n)1/4big) and Obig(√d,n-1/8big) are established under state-dependent and state-independent Markovian sampling, respectively, where d is the dimensionality and n denotes observations or SGD iterations. These rates match the best-known convergence rate for independent and identically distributed (i.i.d) data. Our analysis overcomes significant challenges that arise due to Markovian sampling, leading to the introduction of additional error terms and complex dependencies between the blocks of the batch-means covariance estimator. Moreover, we establish the convergence rate for the first four moments of the ℓ2 norm of the error of SGD dynamics under state-dependent Markovian data, which holds potential interest as an independent result. Numerical illustrations provide confidence intervals for SGD in linear and logistic regression models under Markovian sampling. Additionally, our method is applied to the strategic classification with logistic regression, where adversaries adaptively modify features during training to affect target class classification.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 44 of its 89 references that are in the map. First posted on arXiv 3 Aug 2023.

Builds on

44 of 89 references.

References · 44

  1. 2020Performative Predictioncited by 318
  2. 2015Strategic Classificationcited by 256
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  5. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  6. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  7. 2020Stochastic Optimization for Performative Predictioncited by 92
  8. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  9. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  10. 2020Stochastic optimization with decision-dependent distributionscited by 65
  11. 2018On Markov Chain Gradient Descentcited by 63
  12. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
32 more
  1. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  2. 2021Quantifying Uncertainty in Deep Spatiotemporal Forecastingcited by 48
  3. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  4. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
  5. 2021Statistical Inference with M-Estimators on Adaptively Collected Datacited by 40
  6. 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
  7. 2021State Dependent Performative Prediction with Stochastic Approximationcited by 38
  8. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  9. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  10. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  11. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  12. 2014Optimum Statistical Estimation with Strategic Data Sourcescited by 28
  13. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  14. 2017Statistical inference using SGDcited by 21
  15. 2021Near-optimal inference in adaptive linear regressioncited by 20
  16. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 18
  17. 2020Statistical Inference for Online Decision Making via Stochastic Gradient Descentcited by 17
  18. 2021Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methodscited by 14
  19. 2023Asymptotic normality and optimality in nonsmooth stochastic approximationcited by 14
  20. 2018HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximationcited by 13
  21. 2023Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimatorcited by 12
  22. 2021Bootstrapping the error of Oja's algorithmcited by 11
  23. 2017Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradientscited by 9
  24. 2020Model updating after interventions paradoxically introduces biascited by 9
  25. 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
  26. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  27. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  28. 2023Statistical Inference with Stochastic Gradient Methods under φ-mixing Datacited by 6
  29. 2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
  30. 2023Fairness Uncertainty Quantification: How certain are you that the model is fair?cited by 4
  31. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  32. 2023A Central Limit Theorem for Algorithmic Estimator of Saddle Pointcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 1.

7 papers.

  1. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  2. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 8
  3. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
  4. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  5. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
  6. 2025Online Statistical Inference of Constrained Stochastic Optimization via Random Scalingcited by 0
  7. 2026Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regressioncited by 0