We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves jointly the optimal prediction error rates for least-squares regression, both in terms of forgetting of initial conditions in O(1/n2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small while the "optimal" terms above are large. In order to characterize the tightness of these new bounds, we consider an application to non- parametric regression and use the known lower bounds on the statistical performance (without computational limits), which happen to match our bounds obtained from a single pass on the data and thus show optimality of our algorithm in a wide variety of particular trade-offs between bias and variance.

提出一种基于平均加速正则梯度下降的算法，通过细化初值和Hessian矩阵的假设，最优地优化回归问题，并证明其在偏差与方差之间具有最优性、大数据时初始化影响可达到O（1/n2）以及对于维度d的依赖程度为O（d/n）。

普通最小二乘回归的更快、更好、更坚强的收敛速率