Optimal Approximation for the Least Squares Regression Problem in the Non-Strongly Convex Setting

Accelerated SGD for Non-Strongly-Convex Least Squares

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 while accelerating the forgetting of the initial conditions to our new algorithm is based on a simple modification of the accelerated gradient descent.We provide convergenceresults for both the averaged and the last iterate of the algorithm.