Unbiased least squares regression via averaged stochastic gradient descent
<|reference_start|>Unbiased least squares regression via averaged stochastic gradient descent: We consider an on-line least squares regression problem with optimal solution $\theta^*$ and Hessian matrix H, and study a time-average stochastic gradient descent estimator of $\theta^*$. For $k\ge2$, we provide an unbiased estimator of $\theta^*$ 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 $\theta^*$. 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.<|reference_end|>
@article{kahalé2024unbiased,
    title={Unbiased least squares regression via averaged stochastic gradient
  descent},
    author={Nabil Kahal'e},
    journal={arXiv preprint arXiv:2406.18623},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.18623},
    primaryClass={stat.ML cs.LG stat.ME}
}