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

• URL: http://arxiv.org/abs/2604.10814v1
• Date: Sun, 12 Apr 2026 20:49:33 GMT
• Title: Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
• Abstract summary: We study online covariance matrix estimation for Polyak-Ruppert averaged gradient descent (SGD)<n>The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.
• Score: 12.805268849262243
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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(d^2)$ 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 $Θ(n^{-(1-α)/2})$ for Hessian-free covariance estimation from the SGD trajectory: a Le Cam lower bound gives $Ω(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.

Related papers

• EGGROLL, Unrolled: Understanding and Improving Low-Rank Evolution Strategies at Scale [9.562123195246393]
  EGGROLL makes evolution strategies practical for LLMs by replacing dense Gaussian weight perturbations with low-rank Gaussian products.<n>We analyze the error of its finite-population estimator.<n>LOO-ROLL, a leave-one-out estimator, preserves the finite-rank population field while replacing EGGROLL's two antithetic evaluations per direction by one.
  arXiv  Detail & Related papers  (2026-09-10T01:58:02Z)
• Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design [28.74829605004241]
  We characterize the finite-sample estimation performance and convergence behavior of gradient descent (GD) on the maximum likelihood objective (i.e., the logistic loss)<n>We show that GD linearly converges to a small neighborhood of $*$ achieving an $ell$ error of order $O(sqrt|*|5d/n)$.<n>We also establish a faster local linear convergence to the same statistical error under a large $(|*|_2)$ stepsize.
  arXiv  Detail & Related papers  (2026-06-19T18:43:41Z)
• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  We study the feedback in a Gaussian single-index model with $r*(x) = *(langle *, xrangle)$ and $x sim N(0, I_d)$.<n>We analyze a two-stage neural reward model that first learns the hidden direction $*$ from reward-weighted samples and then fits the readout layer by weighted ridge regression.
  arXiv  Detail & Related papers  (2026-05-23T22:00:38Z)
• Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions [3.6997773420183866]
  We develop new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method.<n>Unlike unbiased estimators such as mini-batching, developing biased variants faces a fundamental technical challenge.<n>We show that the best oracle complexities for the $n$-finite-sum and expectation settings are $mathcalO(n2/3-2)$ and $mathcalO(-10/3)$, respectively, when employing loopless-SVRG or SAGA.
  arXiv  Detail & Related papers  (2026-03-16T17:39:25Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$ [7.884611719110979]
  Gradient Descent (SGD) has become a cornerstone method in modern data science.<n>In this work, we establish emphnon-asymptotic Berry--Esseen bounds for linear functionals of online least-squares SGD.
  arXiv  Detail & Related papers  (2025-10-22T16:25:49Z)
• Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
  We study population convergence guarantees of gradient descent (SGD) for smooth convex objectives in the regime, where the noise at optimum is zero or near zero.<n>For a well-tuned stepsize we obtain a near optimal $widetildeO (1/T + sigma_star/sqrtT)$ rate for the last iterate.
  arXiv  Detail & Related papers  (2025-07-15T12:52:47Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• TIC-TAC: A Framework for Improved Covariance Estimation in Deep Heteroscedastic Regression [109.69084997173196]
  Deepscedastic regression involves jointly optimizing the mean and covariance of the predicted distribution using the negative log-likelihood. Recent works show that this may result in sub-optimal convergence due to the challenges associated with covariance estimation. We study two questions: (1) Does the predicted covariance truly capture the randomness of the predicted mean? Our results show that not only does TIC accurately learn the covariance, it additionally facilitates an improved convergence of the negative log-likelihood.
  arXiv  Detail & Related papers  (2023-10-29T09:54:03Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
  We develop machinery to design efficiently computable and consistent estimators. For sparse regression, we achieve consistency for optimal sample size $ngsim (klog d)/alpha2$. In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix.
  arXiv  Detail & Related papers  (2021-11-04T15:59:44Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms. Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
  arXiv  Detail & Related papers  (2020-03-05T01:56:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.