# Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 12 Apr 2026.

## Builds on (most cited first, 10 of 10)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (2021)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation](https://mlsanity.com/paper/1802.04876/) (2018)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Covariance Estimators for the ROOT-SGD Algorithm in Online Learning](https://mlsanity.com/paper/2212.01259/) (2022)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [On the Utility of Equal Batch Sizes for Inference in Stochastic Gradient Descent](https://mlsanity.com/paper/2303.07706/) (2023)

## Abstract (arXiv)

We study online covariance matrix estimation for Polyak--Ruppert averaged stochastic gradient descent (SGD). The online batch-means estimator of Zhu, Chen and Wu (2023) achieves an operator-norm convergence rate of O(n-(1-α)/4), which yields O(n-1/8) at the optimal learning-rate exponent α rightarrow 1/2^+. A rigorous per-block bias analysis reveals that re-tuning the block-growth parameter improves the batch-means rate to O(n-(1-α)/3), achieving O(n-1/6). The modified estimator requires no Hessian access and preserves O(d2) memory. We provide a complete error decomposition into variance, stationarity bias, and nonlinearity bias components. A weighted-averaging variant that avoids hard truncation is also discussed. We establish the minimax rate Theta(n-(1-α)/2) for Hessian-free covariance estimation from the SGD trajectory: a Le Cam lower bound gives Omega(n-(1-α)/2), and a trajectory-regression estimator--which estimates the Hessian by regressing SGD increments on iterates--achieves O(n-(1-α)/2), matching the lower bound. The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.