We consider the least-squares regression problem and provide a detailed
asymptotic analysis of the performance of averaged constant-step-size
stochastic gradient descent (a.k.a. least-mean-squares). In the strongly-convex
case, we provide an asymptotic expansion up to explicit exponentially decaying
terms. Our analysis leads to new insights into stochastic approximation
algorithms: (a) it gives a tighter bound on the allowed step-size; (b) the
generalization error may be divided into a variance term which is decaying as
O(1/n), independently of the step-size $\gamma$, and a bias term that decays as
O(1/$\gamma$ 2 n 2); (c) when allowing non-uniform sampling, the choice of a
good sampling density depends on whether the variance or bias terms dominate.
In particular, when the variance term dominates, optimal sampling densities do
not lead to much gain, while when the bias term dominates, we can choose larger
step-sizes that leads to significant improvements.

本文考虑了最小二乘回归问题，提出了平均恒定步长随机梯度下降（也称最小均方误差）的性能的详细渐近分析。在强凸情况下，我们提供了一个高度渐近展开式。我们的分析提供了对随机逼近算法的新见解。

常值步长最小均方：偏差 - 方差权衡与最优抽样分布

Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and  Optimal Sampling Distributions

A non-parametric extension of control variates is presented. These leverage
gradient information on the sampling density to achieve substantial variance
reduction. It is not required that the sampling density be normalised. The
novel contribution of this work is based on two important insights; (i) a
trade-off between random sampling and deterministic approximation and (ii) a
new gradient-based function space derived from Stein's identity. Unlike
classical control variates, our estimators achieve super-root-$n$ convergence,
often requiring orders of magnitude fewer simulations to achieve a fixed level
of precision. Theoretical and empirical results are presented, the latter
focusing on integration problems arising in hierarchical models and models
based on non-linear ordinary differential equations.

本研究提出了一种基于梯度信息的采样密度的非参数控制变量扩展方法，能够取得显著的方差降低效果，不要求采样密度归一化，相对于传统控制变量法能够更快速地达到固定精度，能够应用于层次模型和基于非线性常微分方程的模型中。