# Online Covariance Estimation in Nonsmooth Stochastic Approximation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 7 Feb 2025.

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

- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (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)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Stochastic Optimization under Distributional Drift](https://mlsanity.com/paper/2108.07356/) (2021)
- [Asymptotic normality and optimality in nonsmooth stochastic approximation](https://mlsanity.com/paper/2301.06632/) (2023)
- [Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization](https://mlsanity.com/paper/2108.11832/) (2021)
- [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth](https://mlsanity.com/paper/2205.00064/) (2022)

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

- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [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)
- [Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction](https://mlsanity.com/paper/2604.21203/) (2026)

## Abstract (arXiv)

We consider applying stochastic approximation (SA) methods to solve nonsmooth variational inclusion problems. Existing studies have shown that the averaged iterates of SA methods exhibit asymptotic normality, with an optimal limiting covariance matrix in the local minimax sense of H'ajek and Le Cam. However, no methods have been proposed to estimate this covariance matrix in a nonsmooth and potentially non-monotone (nonconvex) setting. In this paper, we study an online batch-means covariance matrix estimator introduced in Zhu et al.(2023). The estimator groups the SA iterates appropriately and computes the sample covariance among batches as an estimate of the limiting covariance. Its construction does not require prior knowledge of the total sample size, and updates can be performed recursively as new data arrives. We establish that, as long as the batch size sequence is properly specified (depending on the stepsize sequence), the estimator achieves a convergence rate of order O(√dn-1/8+varepsilon) for any varepsilon>0, where d and n denote the problem dimensionality and the number of iterations (or samples) used. Although the problem is nonsmooth and potentially non-monotone (nonconvex), our convergence rate matches the best-known rate for covariance estimation methods using only first-order information in smooth and strongly-convex settings. The consistency of this covariance estimator enables asymptotically valid statistical inference, including constructing confidence intervals and performing hypothesis testing.