Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of O(1/ √ n) after n iterations. We consider and analyze two algorithms that achieve a rate of O(1/n) for classical supervised learning problems. For least-squares regression, we show that averaged stochastic gradient descent with constant step-size achieves the desired rate. For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running-time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments showing that they often outperform existing approaches.
The paper presents novel results on how to achieve 
      fast convergence rates O(1/n) in on-line learning via stochastic 
      approximation with requiring strong convexity of the loss function and 
      without having to rely on well-conditioned data matrices. This addresses 
      one of the most interesting open questions in on-line learning, namely how 
      to achieve convergence rates closer to the theoretical limit for the 
      practically most relevant settings (least squares and logistic 
      regression). In my opinion, the paper makes a number of remarkable 
      contributions towards this goal: (i) Theorem 1: a fast convergence result 
      for constant-step size least squares methods with averaging iterates, and 
      an analysis of convergence of higher order moments and (ii) a clever way 
      on how to extend this from the linear case to the more general case (of 
      M-estimators) via the notion of "support points". While the fully 
      satisfactory exploitation of the latter idea seems to require future work 
      (the two phase method seems somewhat less appealing from a practical point 
      of view and the the algorithm who choses support points on the fly is not 
      known to converge), I feel this is already worth publishing in order to 
      make these ideas accessible to a broader audience.