stat.MLSep 17, 2025
SaveOn the Rate of Gaussian Approximation for Online Linear Regression Problems
Organizations: HSE University · CMAP, CNRS, École Polytechnique · Université Paris-Saclay
Abstract
In this paper, we consider the problem of Gaussian approximation for the online linear regression task. We derive the corresponding rates for the setting of a constant stepsize and study the explicit dependence of the convergence rate on the problem dimension and quantities related to the design matrix. When the number of iterations is known in advance, our results yield a normal approximation rate of order , provided that the sample size is large enough.
Figures & tables
Figure 1: Case 1: Kolmogorov distance between the empirical distribution of the projected last iterate of SGD and the Gaussian limit: (a) linear scale, (b) logarithmic scale.
Figure 2: Case 1: Kolmogorov distance between the empirical distribution of the projected last iterate of SGD and the Gaussian limit rescaled by : (a) linear scale, (b) logarithmic scale.
Figure 3: Case 2: Kolmogorov distance between the empirical distribution of the projected last iterate of SGD and the Gaussian limit: (a) linear scale, (b) logarithmic scale.
Figure 4: Case 2: Kolmogorov distance between the empirical distribution of the projected last iterate of SGD and the Gaussian limit rescaled by : (a) linear scale, (b) logarithmic scale.
More in this topic
Linear Regression
Linear regression models how outcomes depend on features through weighted sums, supporting prediction, inference, and analysis of learning algorithms.
See all 84 papersIn this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent , a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of . The nonlinear bias contributes even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error on this example takes order iterations for the best choice . Achieving both Gaussian approximation and relative mean variance-estimation errors at most uniformly over the model class requires at least order iterations for every fixed .
Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design
We consider the parameter estimation problem in logistic regression with Gaussian design: the estimation of a fixed unknown parameter () from i.i.d. samples , where and . Our main aim is to characterize the finite-sample estimation performance and convergence behavior of gradient descent (GD) on the maximum likelihood objective (i.e., the logistic loss). Under small stepsize and initialization, we show that GD linearly converges to a small neighborhood of achieving an error of order . This substantially goes beyond existing theoretical results that lack non-asymptotic estimation error rate and exhibit much slower parameter convergence. We also establish a faster local linear convergence to the same statistical error under a large stepsize. The main technical component is to show that the gradient of the logistic loss satisfies a certain approximate invertibility condition (AIC). To that end, we uniformly control the deviation of the gradient from its population counterpart by covering and peeling arguments, and then show that the population GD is a contraction by a delicate analysis based on the eigenvalues of population Hessian matrices. Finally, we build upon the recent work Matsumoto and Mazumdar (2025) and devise a novel efficient estimator that attains a sharper rate in high dimensions. This indicates that the existing non-asymptotic guarantees exhibit sub-optimal dependence on , and that in many regimes is the tight estimation error rate. Numerical examples are provided to corroborate our theoretical results.
Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD
We prove a sharp Gaussian approximation for the invariant law of constant-stepsize SGD with bounded additive noise generated by an exogenous uniformly ergodic Markov chain. For a smooth, strongly convex objective with a Lipschitz Hessian and nondegenerate long-run noise covariance, the centered iterate normalized by the square root of the stepsize is -close in 1-Wasserstein distance to its limiting Gaussian. The proof combines blockwise Gaussian comparison with long-run contraction. A four-state example gives a matching lower bound although the one-time noise marginal is symmetric and every nonzero-lag autocovariance vanishes. In this example, an adjacent third-order mixed moment produces the leading correction.