Unbiased Least Squares Regression via Averaged Stochastic Gradient Descent

We consider an online least squares regression problem with optimal solution ${\mathit{\theta }}^{*}$ and Hessian matrix $\mathbf{H}$, and study a time-average stochastic gradient descent estimator of ${\mathit{\theta }}^{*}$. For $k\ge 2$, we provide an unbiased estimator of ${\mathit{\theta }}^{*}$ that is a modification of the time-average estimator and 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 polylogarithmic function of the smallest eigenvalue of $\mathbf{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 $\mathbf{H}$ or ${\mathit{\theta }}^{*}$. We describe an “average-start” version of our estimators with similar properties. Our approach is based on randomized multilevel Monte Carlo methods. Numerical experiments confirm our theoretical findings.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2024.0660.