Online covariance estimation for stochastic gradient descent under Markovian sampling

We investigate the online overlapping batch-means covariance estimator for Stochastic Gradient Descent (SGD) under Markovian sampling. Under state-dependent Markovian sampling we prove a convergence rate of O(n−(1−2/α0)/8 log n), α0≥16/3 where d is the dimensionality, n denotes observations or SGD iterations, and α0 is a constant related to the mixing properties of the Markov chain. The slower mixing of the state-dependent Markov chain results in a slower rate compared to the i.i.d. case, which we illustrate with a simple example. However, under state-independent Markovian sampling, we obtain the rate O(d n−1/8) matching the best-known convergence rate for independent and identically distributed (i.i.d.) data. Our analysis overcomes significant challenges arising from Markovian sampling, leading to 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 l2 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.