Statistical Inference for Model Parameters in Stochastic Gradient Descent

Xi Chen, Jason D. Lee, Xin T. Tong, Yichen Zhang

Abstract

The stochastic gradient descent (SGD) algorithm has been widely used in statistical estimation for large-scale data due to its computational and memory efficiency. While most existing works focus on the convergence of the objective function or the error of the obtained solution, we investigate the problem of statistical inference of true model parameters based on SGD when the population loss function is strongly convex and satisfies certain smoothness conditions. Our main contributions are two-fold. First, in the fixed dimension setup, we propose two consistent estimators of the asymptotic covariance of the average iterate from SGD: (1) a plug-in estimator, and (2) a batch-means estimator, which is computationally more efficient and only uses the iterates from SGD. Both proposed estimators allow us to construct asymptotically exact confidence intervals and hypothesis tests. Second, for high-dimensional linear regression, using a variant of the SGD algorithm, we construct a debiased estimator of each regression coefficient that is asymptotically normal. This gives a one-pass algorithm for computing both the sparse regression coefficients and confidence intervals, which is computationally attractive and applicable to online data.

Introduction

Stochastic Gradient Descent (SGD) is the undisputed workhorse of modern machine learning, prized for its ability to handle massive datasets by processing one sample at a time. However, while the optimization community has a solid understanding of how fast SGD converges to a solution, the statistical community has lacked efficient ways to perform inference on that solution. In practical terms, if SGD estimates a feature's weight as 0.5, we need to know the level of certainty—is the true value likely between 0.49 and 0.51, or could it be anywhere from 0.1 to 0.9?

Standard statistical tools for calculating these confidence intervals usually require multiple passes over the entire dataset or heavy matrix calculations (like inverting a large Hessian matrix), which negate SGD's speed and memory advantages. This paper bridges the gap between optimization and statistics by providing "online" uncertainty estimates that are as computationally efficient as the SGD algorithm itself.

Methodology

Foundations: Polyak-Ruppert Averaging

The authors build their work on the classical result of Polyak-Ruppert averaging. This theory demonstrates that if one averages the iterates of SGD, the resulting estimate follows an asymptotic normal distribution centered at the true parameter. To construct a valid confidence interval, however, one must estimate the variance of that distribution—specifically the "sandwich covariance" matrix, $A^{-1}SA^{-1}$, where $A$ is the Hessian of the loss function and $S$ is the covariance of the gradients.

Proposed Estimators

The paper introduces two primary methods for estimating this variance in a fixed-dimension setting:

  1. The Plug-in Estimator: This method directly calculates the Hessian and the gradient covariance as the algorithm runs. While highly accurate, it is considered "intrusive" because it requires access to the internal second derivatives of the loss function, which may not be available in all software implementations.
  2. The Batch-Means Estimator: This is a "black-box" approach that only monitors the sequence of parameters produced by SGD. Because consecutive SGD steps are highly correlated, the authors utilize a novel technique: dividing iterates into batches of increasing size ($n_k \propto k^{\alpha/(1-\alpha)}$). This growth addresses the shrinking step size of SGD, ensuring that batches further apart in time are effectively independent. This allows for a consistent variance estimate without ever calculating a Hessian.

High-Dimensional Inference

For scenarios where the number of features ($d$) exceeds the number of samples ($n$), the authors extend their framework using a variant of SGD called RADAR. By combining RADAR with a "debiasing" technique, they provide valid confidence intervals for sparse models (such as Lasso) in a single pass over the data. This is a significant improvement over traditional debiasing methods, which often require solving $d$ separate optimization problems.

Experimental Evaluation

The proposed methods were evaluated using simulated datasets for linear and logistic regression across various dimensions and covariance structures (Identity, Toeplitz, and Equicorrelation).

  • Coverage Accuracy: In fixed-dimension tests ($d$ up to 200), the Plug-in estimator consistently achieved near-perfect 95% coverage. The Batch-means estimator was slightly more conservative, typically providing 90-93% coverage, but with significantly lower computational overhead.
  • Efficiency: While the Plug-in estimator converges faster to the true variance, the Batch-means estimator is more memory-efficient, as it can be configured to store only the diagonal elements of the covariance matrix.
  • High-Dimensional Performance: In the $d > n$ scenario ($d=500, n=100$), the RADAR-based debiased estimator achieved approximately 90% coverage for active parameters, proving the viability of one-pass high-dimensional inference.

Conclusion and Future Work

This research provides a robust framework for performing statistical inference alongside SGD optimization. The batch-means estimator, in particular, offers a non-intrusive way for practitioners to wrap existing SGD implementations and generate confidence intervals in real-time.

Currently, the theoretical guarantees rely on the objective function being strongly convex, which may not apply to the non-convex landscapes of deep neural networks. Future research directions include extending these methods to Generalized Linear Models (GLMs) and exploring ways to relax convexity requirements to accommodate more complex machine learning architectures.

Summary updated

Abstract

The stochastic gradient descent (SGD) algorithm has been widely used in statistical estimation for large-scale data due to its computational and memory efficiency. While most existing works focus on the convergence of the objective function or the error of the obtained solution, we investigate the problem of statistical inference of true model parameters based on SGD when the population loss function is strongly convex and satisfies certain smoothness conditions. Our main contributions are two-fold. First, in the fixed dimension setup, we propose two consistent estimators of the asymptotic covariance of the average iterate from SGD: (1) a plug-in estimator, and (2) a batch-means estimator, which is computationally more efficient and only uses the iterates from SGD. Both proposed estimators allow us to construct asymptotically exact confidence intervals and hypothesis tests. Second, for high-dimensional linear regression, using a variant of the SGD algorithm, we construct a debiased estimator of each regression coefficient that is asymptotically normal. This gives a one-pass algorithm for computing both the sparse regression coefficients and confidence intervals, which is computationally attractive and applicable to online data.
BibTeX
@article{chen2020statistical,
  author = {Xi Chen and Jason D. Lee and Xin T. Tong and Yichen Zhang},
  title = {{Statistical Inference for Model Parameters in Stochastic Gradient Descent}},
  journal = {The Annals of Statistics},
  year = {2020},
  doi = {10.1214/18-aos1801},
}
Figure