PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical Inference for Model Parameters in Stochastic Gradient Descent

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

arXiv:1610.08637v4stat.ML

TL;DR

The paper studies how to perform statistical inference for parameters estimated by SGD, addressing limitations of work focused mainly on optimization error and convergence. It proposes two covariance estimators for averaged SGD and a debiased high-dimensional regression estimator, obtaining asymptotically exact intervals and tests under stated conditions. The methods are designed for computationally efficient, online-compatible inference, with a stated scope boundary for generalized linear models.

  • Problem

    Statistical inference for individual parameters based on SGD has largely remained unexplored, despite SGD's computational and storage advantages.

  • Method

    The paper proposes plug-in and batch-means covariance estimators for averaged SGD and uses RADAR to construct debiased estimators in high-dimensional linear regression.

  • Results

    The proposed covariance estimators are consistent and enable asymptotically exact confidence intervals and hypothesis tests.

  • Takeaways & Limitations

    The methods provide computationally efficient inference based on SGD, including a batch-means option using only SGD iterates and a one-pass high-dimensional regression procedure.

  • Takeaways & Limitations

    The stated extension from high-dimensional linear regression to generalized linear models remains future work.

Abstract

from arXiv · show

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.

1 Introduction

This paper addresses the largely unexplored problem of statistical inference for model parameters estimated by SGD, beyond optimization convergence. It develops online-compatible covariance estimators for averaged SGD and extends inference to high-dimensional linear regression.

  • Motivation: SGD uses one data pass, O(d) per iteration, and no dataset storage, making it suitable for online data.Averaged SGD achieves O(1/n) convergence for smooth, strongly convex objectives.
  • Motivation: The paper targets coordinate-wise confidence intervals and hypothesis tests for the true parameters, which existing SGD work has largely not addressed.The proposed inference can test whether x*_j = c and identify a range containing x*_j.
  • Fixed-dimensional inference: Asymptotic normality of the averaged iterate is insufficient for inference without consistently estimating its asymptotic covariance A^-1SA^-1.The standard sample covariance estimator requires storing all data because the final average iterate is unavailable until SGD terminates.
  • Fixed-dimensional inference: The plug-in estimator constructs online estimates of the Hessian and gradient covariance, yielding a consistent asymptotic-covariance estimator.Its Hessian terms are evaluated at successive SGD iterates, avoiding storage of each iterate and sample.
  • Fixed-dimensional inference: The batch-means estimator uses increasing-size batches of SGD iterates and consistently estimates covariance without Hessians or their inverses.Increasing batch sizes address the time-inhomogeneous Markov structure and correlation decay of SGD iterates.
  • Estimator trade-offs: Both estimators support asymptotically exact confidence intervals, while the plug-in method converges faster and batch means can store only diagonal estimates.Batch means is attractive for limited computation, legacy SGD implementations, and settings where only coordinate-wise uncertainty is needed.
  • High-dimensional inference: For high-dimensional linear regression, the paper uses RADAR to construct asymptotically normal debiased coefficient estimators despite proximal SGD's non-normal averaged iterate.This supports one-pass computation of sparse coefficients and confidence intervals for online data.

2 Background

The paper develops statistical inference for averaged SGD by estimating its asymptotic covariance, extending beyond prior convergence and asymptotic-normality results. Under strong convexity and diminishing step sizes, averaged SGD supports confidence intervals based on this covariance.

  • Averaged SGD: For step sizes ηi = ηi−α with α ∈(1/2, 1), the averaged iterate satisfies the asymptotic-normality result used for inference.The supplied background identifies this step-size range as the condition under which the limiting distribution result applies.
  • Averaged SGD: Averaged SGD has a limiting distribution centered at the true minimizer x∗, with asymptotic covariance A−1SA−1.Here A is the Hessian of the population loss at x∗, while S is the covariance of the stochastic gradient at x∗.
  • Inference target: Confidence intervals for coordinate x∗j use the averaged iterate and an estimator of the corresponding diagonal element of A−1SA−1.The interval is formed as ¯xn,j ± zq/2ˆσjj/√n, with zq/2 the standard-normal quantile.
  • Efficiency: In well-specified likelihood models, A = S = I(x∗), so the limiting covariance becomes I−1 and averaged SGD is asymptotically efficient.In misspecified models, the covariance instead has the sandwich form A−1SA−1.
  • Examples: The motivating examples include linear regression and logistic regression, with SGD recursions derived from their respective loss functions.For linear regression, the population gradient is A(x−x∗) and the Hessian is A; logistic regression supplies a general-loss example.

3 Assumptions and Error Bounds

The fixed-dimensional analysis assumes a strongly convex, smooth population loss and controlled stochastic-gradient moments. Under these conditions, the SGD errors satisfy moment and decay bounds that support covariance estimation.

  • Assumptions: The population loss F is assumed continuously differentiable, strongly convex, and Lipschitz-gradient, with an existing Hessian at x∗.Strong convexity ensures λmin(∇2F(x∗)) ≥ µ, a key condition for parameter estimation and inference.
  • Assumptions: The stochastic-gradient noise ξn is a martingale difference with conditional covariance expanding around S and bounded fourth conditional moment.These conditions control the noise near x∗ and provide the moments needed for variance-estimator analysis.
  • Dimension dependence: The analysis tracks dimension through Cd, which depends on constants such as the gradient smoothness, noise moments, and tr(S).For linear and logistic regression, Cd grows linearly in d.
  • Error bounds: The step sizes and initialization are constrained relative to Cd, including ηiCd ≤ cµ and ∥x0−x∗∥2 = O(Cd).When d is constant, the paper notes that a burn-in period can accommodate the step-size condition.
  • Error bounds: With diminishing step sizes ηn = ηn−α, the SGD error ∆n satisfies conditional-moment bounds under the stated assumptions.The bounds extend earlier convergence results to fourth moments because variance estimation requires controlling a variance of a variance estimator.

4 Estimators for Asymptotic Covariance

The paper proposes plug-in and batch-means estimators for the asymptotic covariance of averaged SGD. The plug-in method is faster but needs Hessian information, whereas batch means uses only SGD iterates and remains suitable for asymptotically exact inference.

  • Plug-in estimator: The plug-in estimator separately estimates A and S, then combines them as eA−1n eSn eA−1n to estimate A−1SA−1.A thresholded estimator eAn ensures invertibility, and the estimates can be updated online when Hessian information is available.
  • Plug-in estimator: The plug-in estimator requires Hessian computation, its inverse, and an additional Hessian-Lipschitz assumption.This requirement may be unavailable in legacy SGD implementations that expose only the iterates.
  • Plug-in estimator: Under the stated assumptions, the thresholded plug-in estimator is consistent and has an error rate dominated by O(n−α) when Cd is constant.The theorem applies with diminishing step sizes ηi = ηi−α and bounded initialization.
  • Batch-means estimator: The batch-means estimator splits SGD iterates into M + 1 batches, discards the initial burn-in batch, and treats later batch means as samples.The construction addresses strong correlation between neighboring iterates and can be updated without storing all batch means.
  • Inference: Despite its slower convergence rate, the batch-means estimator yields asymptotically exact confidence intervals.This makes it an alternative when computation, storage, or Hessian access is limited.

5 High-dimensional Linear Regression

For high-dimensional linear regression, the paper develops one-pass stochastic optimization for debiased coefficient inference, avoiding restrictive screening conditions and supporting online data.

  • Problem: High-dimensional inference targets sparse regression coefficients when d can be comparable to or larger than n.The model assumes a sparse true parameter and sub-Gaussian covariates.
  • Motivation: Lasso screening requires a strong beta-min condition and treats sparsity as a constant, motivating a direct one-pass inference approach.The proposed method is intended to avoid these screening restrictions.
  • Method: The resulting procedure constructs a debiased estimator and confidence intervals for every regression coefficient in one pass over the data.The algorithm updates the design and optimization iterates sequentially, then forms the debiased estimator from the final outputs.
  • Method: RADAR estimates the sparse regression parameter and inverse covariance using stochastic optimization rather than deterministic convex optimization.The method uses RADAR because it provides the optimal convergence rate in ℓ1-norm and applies stochastic updates to both estimation problems.
  • Practical implications: The method has total per-iteration complexity O(d^2), is computationally more efficient than deterministic alternatives, and applies to online data.The comparison notes that node-wise Lasso requires d optimization problems, whereas the proposed approach uses one data pass.
  • Results: The normalized debiased estimator converges uniformly to N(0, 1), validating asymptotic pointwise confidence intervals and component-wise p-values.The theorem supports inference uniformly over sparse parameters and coefficient indices.

6 Numerical Simulations

The simulations evaluate confidence-interval estimators in low- and high-dimensional regression. The plug-in estimator generally attains coverage near the nominal 95%, while batch-means and high-dimensional methods trade some coverage for computational or storage advantages.

  • Low-dimensional cases: The experiments evaluate plug-in and batch-means confidence intervals for linear and logistic regression across covariance structures and dimensions.Performance is measured by average coverage rate and interval length, with oracle intervals reported for comparison.
  • Low-dimensional cases: Nearly 95% average coverage is achieved by the plug-in estimator in both linear and logistic regression.For linear regression, plug-in intervals are usually longer than batch-means and oracle intervals; for logistic regression, their lengths also increase with dimension.
  • Low-dimensional cases: About 92% coverage is achieved by batch-means intervals in linear regression when M = n^0.25 or M = n^0.3.Batch-means intervals are usually shorter than plug-in intervals and may be computationally more efficient because they use only SGD iterates.
  • Low-dimensional cases: About 90% coverage is achieved by batch-means intervals in logistic regression, with average lengths usually smaller than oracle lengths.Different batch counts produce comparable coverage rates, indicating limited sensitivity to M in these experiments.
  • High-dimensional cases: About 90% average coverage is achieved for sparse high-dimensional linear regression with s0 = 3, while about 88% is achieved for s0 = 15.Coverage is slightly better on active coordinates than on inactive coordinates, and interval lengths are slightly smaller than oracle lengths.
  • High-dimensional cases: Comparable reliable coverage is obtained with deterministic optimization, with rates closer to nominal levels than those using stochastic RADAR.The authors attribute undercoverage in Table 3 to estimation error in the diagonals of the precision-related matrix product.

7 Conclusions and Future Works

The paper develops inference for SGD in fixed-dimensional settings and high-dimensional linear regression. Its estimators support asymptotically exact inference, while extensions to generalized linear models and broader SGD settings remain open.

  • Contributions: Two consistent estimators of the asymptotic variance of the averaged SGD iterate enable asymptotically exact confidence intervals and hypothesis tests.The batch-means estimator is computationally more efficient because it uses only SGD iterates.
  • Contributions: The paper also studies statistical inference based on SGD for high-dimensional linear regression.This extends the inference framework beyond the fixed-dimensional averaged-SGD setting.
  • Future work: An extension to generalized linear models is identified as an interesting problem for future work.The stated future direction marks a scope boundary for the current high-dimensional inference results.
  • Future work: Consistency of batch-means estimation for implicit SGD and inference for more challenging optimization problems, including non-convex problems, are also left open.These directions are presented as future research questions.

A Verifying assumptions for two examples

The appendix verifies the paper’s assumptions for linear and logistic regression examples. It establishes positive definiteness, moment and smoothness properties, and dimension-dependent bounds needed by the theoretical results.

  • Assumption verification: For the linear and logistic examples, the appendix checks the assumptions used by the main theoretical results.The verification is carried out on Examples 2.1 and 2.2.
  • Linear regression: The linear-regression example has LF = 1, tr(S) = O(d), Σ1 = 0, Σ2 = O(d^2), Σ3 = O(d^2), and Σ4 = O(d^4).These quantities verify the required smoothness and moment bounds under the stated Gaussian setup.
  • Dimension dependence: For Gaussian designs, the dimension constant is shown to satisfy Cd = O(d).The appendix derives this scaling for the example-specific assumptions.
  • Logistic regression: The logistic-regression example satisfies the assumptions when the covariates have bounded eighth moments, positive density, and the iterates are bounded.The appendix also derives dimension-dependent bounds for the corresponding quantities.
  • Positive definiteness: Strictly positive data density and bounded iterates ensure that the Hessian of the population loss has a strictly positive minimum eigenvalue.This supplies the strong-convexity condition required in the analysis.

B.1 Proof of Lemma 3.1

This appendix proves moment bounds for SGD and its linear oracle sequence under the paper’s assumptions. These bounds support the convergence and covariance-estimation results used in the main analysis.

  • Proof of Lemma 3.1: Lemma 3.1 derives the fourth-moment bounds needed to establish Assumption 3.2.The proof combines bounded Hessian moments, bounded fourth moments of ∇f(x*, ζ), and inequalities including Jensen’s and Cauchy–Schwarz.
  • Moment bounds: The SGD error recursion is controlled using strong convexity, Young’s inequality, Hölder’s inequality, and discrete Gronwall’s inequality.These steps yield bounds for the error moments under decreasing step sizes.
  • Moment bounds: For step sizes ηn = ηn^-α with α ∈ (0, 1), the analysis establishes bounds governed by dimension-dependent constants and the initial error.The resulting inequalities apply for sufficiently large n under the stated assumptions.
  • Linear oracle sequence: The linear oracle sequence satisfies a corresponding second-moment bound of order n^-α(Cd + ||U0||2^2 + ||Δ0||2^2).Its recursion is analyzed using the same type of contraction and noise bounds as the SGD error sequence.
  • Consistency of An: The proof decomposes An − A into empirical fluctuation and iterate-deviation terms to establish consistency of An.The two terms are bounded using independence, smoothness assumptions, and the previously established moment bounds.

C.2 Proof of Theorem 4.2 for consistency of the plug-in estimator

The proof establishes consistency of the thresholded plug-in estimator under the stated assumptions, using matrix perturbation, batch approximations, and linear-oracle comparisons.

  • Matrix perturbation bounds control the inverse-matrix error needed to prove plug-in consistency.The proof begins with an inverse perturbation inequality for B = A + E and uses Weyl’s inequality.
  • The thresholded plug-in estimator converges to the asymptotic covariance matrix under Assumptions 3.1, 3.2, and 4.1.The result applies when initialized from any bounded x0.
  • When Cd is constant, the right-hand side of the consistency bound is dominated by O(n−α).Here α ∈(0, 1) defines the stepsize sequence ηi = ηi−α.
  • Technical lemmas approximate batch indices, batch lengths, stepsize sums, and geometric sequences for non-asymptotic error analysis.These approximations support bounds involving the number of batches M and sample size N.
  • The linear-oracle analysis decomposes noise into an i.i.d. component and a martingale-difference component, then bounds their covariance contributions.The proof compares the resulting quantities with the target covariance A−1SA−1.

D.3 Proof of Lemma 4.7

The proof of Lemma 4.7 bounds the batch-means estimator’s deviation from the asymptotic covariance for the linear oracle sequence.

  • Lemma 4.7 concerns the batch-means estimator for fixed dimension with stepsize ηi = ηi−α and α ∈(1/2, 1).The result applies to the sequence Un with any bounded U0.
  • The proof rewrites the batch-means estimator using mean identities and separates terms inherited from the linear-oracle approximation.Lemma D.5 supplies the main approximation, while the remaining estimator term is bounded separately.
  • Approximations from Lemmas D.1 and D.2 control batch-related quantities and lower-order terms.Collecting these terms yields the claimed inequality for sufficiently large N and M.

D.4 Consistency proof of Batch-Means Estimator

The batch-means estimator is shown to remain consistent when applied to the original SGD iterates rather than only the linear oracle sequence.

  • Theorem 4.3 states that the batch-means estimator is consistent under Assumptions 3.1 and 3.2 for α ∈(1/2, 1).The estimator may be initialized by any bounded x0.
  • The proof compares batch and overall mean differences for the SGD sequence and decomposes their discrepancy into several terms.The linear-oracle result from Lemma 4.7 provides the principal covariance control.
  • The proof concludes by combining the bounds and using lower-order convergence arguments to obtain the stated consistency result.The same stepsize form also appears in the associated plug-in covariance result.
  • Bounds from Lemmas 3.2 and D.2 control the remaining terms, including geometric-sequence contributions.Markov-inequality arguments are used in the accompanying plug-in consistency analysis.

E.1 Proof of Proposition 5.1

The proof of Proposition 5.1 establishes high-probability control of the sparse estimator and the nodewise regression quantities used for debiasing.

  • Proposition 5.1 provides a high-probability bound for the estimator bxn under Assumption 5.1 and the specified algorithm parameters.The analysis uses the number of epochs Kn and the regularization parameter λKn.
  • The total iteration count is bounded by s2(log d)2Kn, linking computational cost to sparsity, dimension, and the number of epochs.The bound follows from the epoch construction.
  • The parameter set B(s) restricts x∗ to vectors with at most s nonzero coordinates.Convergence of ∥bxn −x∗∥1 follows from the cited sparse-estimation result.
  • Row sparsity of Ω implies that each population nodewise-regression solution (γj)∗ is sj-sparse.This sparsity supports bounds for the estimated rows bΩj.
  • Sub-Gaussian assumptions and concentration inequalities control the nodewise estimation errors uniformly over coordinates.The proof combines these bounds with sparsity conditions such as s = o(√(n/log d)).

F More Simulations

Additional simulations examine confidence-interval performance under Toeplitz and Equi Corr covariance designs as correlation varies. Coverage is broadly stable in small dimensions, while larger dimensions show slightly lower coverage and longer intervals as correlation increases.

  • Toeplitz covariance: Toeplitz simulations vary the correlation parameter r from 0.4 to 0.6 and evaluate coverage rates, average interval lengths, and standard errors for nominal 95% confidence intervals.The covariance matrix uses Σ_i,j = r^|i−j|.
  • Toeplitz covariance: When d is small, coverage rates remain similar as r increases in the Toeplitz design.
  • Toeplitz covariance: When d is large, increasing r slightly decreases coverage rates and increases average interval lengths, consistently with oracle lengths.
  • Equi Corr covariance: Equi Corr simulations show a similar pattern, with r varied from 0.1 to 0.3 and the minimum eigenvalue of Σ decreasing as r increases.The reported comparisons support robustness with respect to the minimum eigenvalue of the covariance matrix.
  • Additional models: Logistic-regression analogues of these covariance-design comparisons are reported in Tables 7 and 8.
Loading 1610.08637v4…