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.

在这篇研究中，我们考虑了一个具有最优解 θ* 和 Hessian 矩阵 H 的在线最小二乘回归问题，并研究了 θ* 的时间平均随机梯度下降估计器。我们提供了 θ* 的无偏估计器，它是时间平均估计器的修改版本，在 k 阶数量级的时间步骤内运行，具有 O (1/k) 的预期超出风险。O 记号后的常数依赖于回归的参数，是 H 的最小特征值的多对数函数。我们提供了时间平均估计器和其无偏对应物的预期超出风险的有偏和无偏估计器，而不需要对 H 或 θ* 有任何了解。我们描述了我们的估计器的 “平均起始” 版本，具有类似的性质。我们的方法基于随机多级蒙特卡罗。我们的数值实验证实了我们的理论发现。