stat.MLSep 17, 2025

On the Rate of Gaussian Approximation for Online Linear Regression Problems

Authors: Marina Sheshukova, Alain Durmus, Marat Khusainov, Sergey Samsonov

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 dd and quantities related to the design matrix. When the number of iterations nn is known in advance, our results yield a normal approximation rate of order log⁡n/n\sqrt{\log{n}/n}, provided that the sample size nn is large enough.

Figures & tables

Explore similar work

Oct 31, 2026

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

In 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 γ∈(1/2,1)γ\in(1/2,1), a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order n1/2−γ+nγ−1n^{1/2-γ}+n^{γ-1} in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of γγ. The nonlinear bias contributes n1/2−γn^{1/2-γ} even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order n−(1−γ)/2n^{-(1-γ)/2} 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 ε\varepsilon on this example takes order ε−4\varepsilon^{-4} iterations for the best choice γ=3/4γ=3/4. Achieving both Gaussian approximation and relative mean variance-estimation errors at most ε\varepsilon uniformly over the model class requires at least order ε−6\varepsilon^{-6} iterations for every fixed γγ.
Jun 19, 2026

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 θ∗∈Rdθ^*\in \mathbb{R}^d (∥θ∗∥2≥1\|θ^*\|_2\ge 1) from nn i.i.d. samples {(xi,yi)}i=1n\{(x_i,y_i)\}_{i=1}^n, where xi∼N(0,Id)x_i\sim N(0,I_d) and yi∣xi∼Bernoulli(1/(1+exp⁡(−xi⊤θ∗)))y_i|x_i \sim {\rm Bernoulli}(1/(1+\exp(-x_i^\top θ^*))). 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 O(1)O(1) stepsize and 00 initialization, we show that GD linearly converges to a small neighborhood of θ∗θ^* achieving an ℓ2\ell_2 error of order O(∥θ∗∥25d/n)O(\sqrt{\|θ^*\|_2^5d/n}). 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 Θ(∥θ∗∥2)Θ(\|θ^*\|_2) 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 ∥θ∗∥2\|θ^*\|_2, and that in many regimes Θ(∥θ∗∥2d/n)Θ(\sqrt{\|θ^*\|_2d/n}) is the tight estimation error rate. Numerical examples are provided to corroborate our theoretical results.
Sep 30, 2026

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 O(α)O(\sqrtα)-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.