# Unbiased least squares regression via averaged stochastic gradient descent

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 26 Jun 2024.

## Builds on (most cited first, 11 of 11)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [Unbiased inference for discretely observed hidden Markov model diffusions](https://mlsanity.com/paper/1807.10259/) (2018)
- [Unbiased Monte Carlo: posterior estimation for intractable/infinite-dimensional models](https://mlsanity.com/paper/1411.7713/) (2014)

## Built on by (most cited first, 1 of 1)

- [Stochastic gradient descent with initial regularization](https://mlsanity.com/paper/2608.22953/) (2026)

## Abstract (arXiv)

We consider an on-line least squares regression problem with optimal solution θ^* and Hessian matrix H, and study a time-average stochastic gradient descent estimator of θ^*. For k≥2, we provide an unbiased estimator of θ^* that is a modification of the time-average estimator, runs with an expected number of time-steps of order k, with O(1/k) expected excess risk. The constant behind the O notation depends on parameters of the regression and is a poly-logarithmic function of the smallest eigenvalue of H. We provide both a biased and unbiased estimator of the expected excess risk of the time-average estimator and of its unbiased counterpart, without requiring knowledge of either H or θ^*. We describe an "average-start" version of our estimators with similar properties. Our approach is based on randomized multilevel Monte Carlo. Our numerical experiments confirm our theoretical findings.