  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.
