Research map / Optimization / Nonconvex and smooth optimization
How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Approximates the rescaled finite-time distribution of stochastic approximation iterates by time-varying Gaussians via Stein's method on a discrete Ornstein-Uhlenbeck process (DOUG), giving Wasserstein-1 rates O~(sqrt(alpha_k)) with matching lower bounds.
Problem
Characterizing the finite-time distribution of rescaled stochastic approximation iterates, which is intractable in general, in order to obtain useful tail bounds and quantify the rate of asymptotic normality.
Approach
Approximate the rescaled SA iterate by a sequence of Gaussians with recursively defined covariance; analyze an auxiliary discrete O-U process (DOUG) with general additive noise via Stein's method for weighted sums, then couple SA to DOUG to handle multiplicative noise.
Key results
- Wasserstein-1 distance between rescaled SA iterate and time-varying Gaussian is O~(sqrt(alpha_k)) for diminishing step sizes, with matching Omega(sqrt(alpha_k)) lower bounds.
- For xi in [2/3,1) the time-varying Gaussian approximation is sharper than the asymptotic Gaussian; the asymptotic Gaussian rate is min(xi/2, 1-xi) in the exponent.
- Simulations on linear SA with exponential noise match the theoretical rates; Laplace and uniform noise empirically suggest an improved O(alpha_k) rate.
Surprising findings
- Empirical convergence rate for symmetric noise (Laplace, uniform) appears to improve to O(alpha_k), beyond the general rate.
Limitations
- Theory for xi<2/3 does not cleanly resolve the bottleneck; the bound does not match simulation there.
- Stationary-distribution result for constant step size is left as future work.
- Analysis is for linear-drift local approximation and requires bounded third moments of the additive noise.
Experimental setup
Datasets: synthetic linear SA with exponential, Laplace and uniform noise
Metrics: Wasserstein-1 distance estimated log-log slope
Baselines: asymptotic normality results for SA MSE bounds for SA (Chen et al.) Wasserstein bounds for SA with Markovian noise (contemporary work)
Builds on: Stein's method for Gaussian approximation Berry-Esseen theorem Unadjusted Langevin Algorithm analysis Kantorovich-Rubinstein duality
Closest papers by meaning
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.88)
- The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.88)
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging (NeurIPS 2025 · similarity 0.86)
- Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity (ICML 2025 · similarity 0.86)
- Generalization of noisy SGD in unbounded non-convex settings (ICML 2025 · similarity 0.86)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.