Answers are grounded in this paper and cite their sources.
Analysis reveals unbiased estimators reduce excess risk in least squares regression, suggesting improved accuracy with 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 .
No takes yet. Share an insight, caveat, or question.
Nabil Kahale (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: