# Online covariance estimation for stochastic gradient descent under Markovian sampling

arXiv: https://arxiv.org/abs/2308.01481 · HTML: https://mlsanity.com/paper/2308.01481/

## Key facts

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

## Builds on (most cited first, 30 of 44)

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Quantifying Uncertainty in Deep Spatiotemporal Forecasting](https://mlsanity.com/paper/2105.11982/) (2021)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Statistical Inference with M-Estimators on Adaptively Collected Data](https://mlsanity.com/paper/2104.14074/) (2021)
- [State Dependent Performative Prediction with Stochastic Approximation](https://mlsanity.com/paper/2110.00800/) (2021)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Optimum Statistical Estimation with Strategic Data Sources](https://mlsanity.com/paper/1408.2539/) (2014)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [Near-optimal inference in adaptive linear regression](https://mlsanity.com/paper/2107.02266/) (2021)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Statistical Inference for Online Decision Making via Stochastic Gradient Descent](https://mlsanity.com/paper/2010.07341/) (2020)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)

## Built on by (most cited first, 7 of 7)

- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling](https://mlsanity.com/paper/2505.18327/) (2025)
- [Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression](https://mlsanity.com/paper/2604.10814/) (2026)

## 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.