We consider stochastic gradient descent (SGD) for least-squares regression with potentially several passes over the data. While several passes have been widely reported to perform practically better in terms of predictive performance on unseen data, the existing theoretical analysis of SGD suggests that a single pass is statistically optimal. While this is true for low-dimensional easy problems, we show that for hard problems, multiple passes lead to statistically optimal predictions while single pass does not; we also show that in these hard models, the optimal number of passes over the data increases with sample size. In order to define the notion of hardness and show that our predictive performances are optimal, we consider potentially infinite-dimensional models and notions typically associated to kernel methods, namely, the decay of eigenvalues of the covariance matrix of the features and the complexity of the optimal predictor as measured through the covariance matrix. We illustrate our results on synthetic experiments with non-linear kernel methods and on a classical benchmark with a linear model.

本篇论文研究了随机梯度下降算法在多次迭代时对于最小二乘回归的预测能力，理论分析表明虽然单次迭代可以实现统计上的最优，但对于难题来说，多次迭代可以实现统计上的最优。我们的研究基于无限维模型，关注特征协方差矩阵的特征值衰减和最优预测器的复杂度等基于核方法的概念，研究结果得到了人工合成和真实数据上的验证。

通过多次迭代在复杂学习问题上使用随机梯度下降的统计最优性