论文标题
非额外凸的加速SGD
Accelerated SGD for Non-Strongly-Convex Least Squares
论文作者
论文摘要
我们考虑在非凸出凸设置中最小二乘回归问题的随机近似。我们提出了第一种实用算法，该算法以依赖问题的噪声来达到最佳预测错误率，为$ O（d/t）$，同时加速忘记初始条件到$ O（d/t^2）$。我们的新算法基于对加速梯度下降的简单修改。我们为算法的平均和最后一个迭代提供收敛结果。为了描述这些新界限的紧密性，我们在无噪声设置中提出了一个匹配的下限，从而显示了我们算法的最佳性。
We consider stochastic approximation for the least squares regression problem in the non-strongly convex setting. We present the first practical algorithm that achieves the optimal prediction error rates in terms of dependence on the noise of the problem, as $O(d/t)$ while accelerating the forgetting of the initial conditions to $O(d/t^2)$. Our new algorithm is based on a simple modification of the accelerated gradient descent. We provide convergence results for both the averaged and the last iterate of the algorithm. In order to describe the tightness of these new bounds, we present a matching lower bound in the noiseless setting and thus show the optimality of our algorithm.
