Unbiased least squares regression via averaged stochastic gradient descent

We consider an online least squares regression problem with optimal solution [Formula: see text] and Hessian matrix [Formula: see text], and study a time-average stochastic gradient descent estimator of [Formula: see text]. For [Formula: see text], we provide an unbiased estimator of [Formula: see text] that is a modification of the time-average estimator and runs with an expected number of time-steps of order k, with [Formula: see text] 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 [Formula: see text]. 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 [Formula: see text] or [Formula: see text]. 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 .