# Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model

arXiv: https://arxiv.org/abs/2006.08212 · HTML: https://mlsanity.com/paper/2006.08212/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 39)

- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Model Collapse Demystified: The Case of Regression](https://mlsanity.com/paper/2402.07712/) (2024)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law](https://mlsanity.com/paper/2505.19227/) (2025)
- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta](https://mlsanity.com/paper/2206.11124/) (2022)
- [Improved Scaling Laws in Linear Regression via Data Reuse](https://mlsanity.com/paper/2506.08415/) (2025)
- [Capacity dependent analysis for functional online learning algorithms](https://mlsanity.com/paper/2209.12198/) (2022)
- [Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions](https://mlsanity.com/paper/2202.00992/) (2022)
- [Accelerated SGD for Non-Strongly-Convex Least Squares](https://mlsanity.com/paper/2203.01744/) (2022)
- [Provable Generalization of Overparameterized Meta-learning Trained with SGD](https://mlsanity.com/paper/2206.09136/) (2022)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization](https://mlsanity.com/paper/2403.07264/) (2024)
- [Non-reversible Parallel Tempering for Deep Posterior Approximation](https://mlsanity.com/paper/2211.10837/) (2022)
- [Risk Bounds of Accelerated SGD for Overparameterized Linear Regression](https://mlsanity.com/paper/2311.14222/) (2023)
- [Double-descent curves in neural networks: a new perspective using Gaussian processes](https://mlsanity.com/paper/2102.07238/) (2021)
- [On the Double Descent of Random Features Models Trained with SGD](https://mlsanity.com/paper/2110.06910/) (2021)
- [Kernelized Diffusion maps](https://mlsanity.com/paper/2302.06757/) (2023)
- [The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms](https://mlsanity.com/paper/2405.19585/) (2024)
- [Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descent](https://mlsanity.com/paper/2407.02322/) (2024)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)
- [SGD with memory: fundamental properties and stochastic acceleration](https://mlsanity.com/paper/2410.04228/) (2024)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)

## Abstract (arXiv)

In the context of statistical supervised learning, the noiseless linear model assumes that there exists a deterministic linear relation Y = langle θ_*, X rangle between the random output Y and the random feature vector Phi(U), a potentially non-linear transformation of the inputs U. We analyze the convergence of single-pass, fixed step-size stochastic gradient descent on the least-square risk under this model. The convergence of the iterates to the optimum θ_* and the decay of the generalization error follow polynomial convergence rates with exponents that both depend on the regularities of the optimum θ_* and of the feature vectors Phi(u). We interpret our result in the reproducing kernel Hilbert space framework. As a special case, we analyze an online algorithm for estimating a real function on the unit interval from the noiseless observation of its value at randomly sampled points; the convergence depends on the Sobolev smoothness of the function and of a chosen kernel. Finally, we apply our analysis beyond the supervised learning setting to obtain convergence rates for the averaging process (a.k.a. gossip algorithm) on a graph depending on its spectral dimension.