Unbiased least squares regression via averaged stochastic gradient descent
This work provides an incremental improvement in optimization methods for regression, offering unbiased estimators with theoretical guarantees for practitioners in machine learning and statistics.
The paper tackles the problem of online least squares regression by proposing an unbiased estimator for the optimal solution using a modified time-average stochastic gradient descent, achieving an expected excess risk of O(1/k) with computational efficiency dependent on regression parameters and Hessian eigenvalues.
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\ge2$, 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.