Accelerating Stochastic Gradient Descent using Predictive Variance Reduction
Stochastic gradient descent is popular for large scale optimization but has slow convergence asymptotically due to the inherent variance. To remedy this problem, we introduce an explicit variance reduction method for stochastic gradient descent which we call stochastic variance reduced gradient (SVRG). For smooth and strongly convex functions, we prove that this method enjoys the same fast convergence rate as those of stochastic dual coordinate ascent (SDCA) and Stochastic Average Gradient (SAG). However, our analysis is significantly simpler and more intuitive. Moreover, unlike SDCA or SAG, our method does not require the storage of gradients, and thus is more easily applicable to complex problems such as some structured prediction problems and neural network learning.
This work proposes a new algorithm that perturbs a 
      constant-step size stochastic gradient iteration. The perturbation is 
      based on a previous full-gradient evaluation, and allows the method to 
      achieve a linear convergence rate that is faster than the rate obtained by 
      deterministic gradient methods. The paper proposes a nice 
      approach, that does indeed address the memory problems with using 
      alternate approaches like SDCA and SAG. There is a nice discussion of how 
      all three algorithms essentially force the variance of the estimator to go 
      to zero as the solution is approached. After equation (6): 
      Normally, strong-convexity is defined with gamma strictly greater than 0. 
      Also, the gradient method has a linear convergence rate with eta < 2/L. 
      The citation style is wrong, and the bibliography needs to be 
      cleaned up. Note that the SAG and SDCA papers were published in NIPS'12 
      and ICML'13 conferences, respectively. Is is probably worth 
      explicitly noting somewhere the requirement that eta < 1/2L in Theorem 
      1. The proof is indeed much simpler than the SAG proof. However, 
      in the strongly-convex case I don't think that it is obviously simpler 
      than the SDCA proof. But it is probably worth pointing out that the SDCA 
      method is for a special case of (1). Because the method requires 
      full passes through the data, it doesn't really seem appropriate to call 
      it a stochastic gradient method. Indeed, on the first pass through the 
      data the method doesn't change the parameters, so it will start out a full 
      pass behind the basic SGD method. A better name might be a hybrid method 
      or a mixed method. Related to the above, it is worthwhile to add a 
      sentence to the paper contrasting the new approach with the 
      closely-related approaches that use growing sample-sizes, like Friedlander 
      and Schmidt ["Hybrid Deterministic-Stochastic Methods for Data Fitting"] 
      and Byrd et al. ["Sample size selection in optimization methods for 
      machine learning"]. To complement Section 4, it might be 
      worthwhile to try to write the new method as well as SAG as special cases 
      of a more general algorithm. (In SAG, \nabla \phi_{i_t}(\tilde{w}) is 
      replaced by \nabla \phi_{i_t} (w_{i_t}) where w_{i_it} is some previous 
      iteration, and mu is updated at each iteration rather than after every m 
      iterations). It seems like there are numerous variations on this family 
      that would give linear convergence. The paper should say how eta 
      and m were set in the experiments. Although the algorithm does 
      indeed achieve a rate similar to SDCA and SAG in terms of number of 
      examples, the rate achieved appears to be slower in general. For example, 
      using the example on page 5 where L/gamma=n, it requires m=8n to have 
      alpha=1/2 with the step size of 1/4L. So the algorithm requires 10 passes 
      through the data on each iteration to achieve this rate (or 9 passes if a 
      memory is used). If you are allowed to do 10 passes through the data of 
      SDCA in this setting, you would get a faster rate of alpha=(1-1/2n)^10n 
      for the same number of points visited as the new algorithm. (the 
      rate of SDCA is 1 - n\lambda/n(n\lambda+L) = 1-1/2n if lambda=L/n) 
      The last sentence of Section 3 should be accompanied by a citation 
      or more details. Otherwise, it should be left out. Regarding 
      Section 4, note that there are other works discussing the relationship 
      between primal gradient methods and dual coordinate-wise methods. For 
      example, see Bach's "Duality between subgradient and conditional gradient 
      methods". I found the experimental evaluation of the proposed 
      method to be quite weak, only comparing to the SGD method in a regime 
      where 200 or 500 passes through the data set are performed. This does not 
      seem like the regime where SGD would be the method of choice, particularly 
      for the convex objective. Given this setting, and given that the method is 
      a hybrid-type strategy, it would make more sense to also compare to 
      competitive methods (like an L-BFGS or non-linear conjugate gradient code) 
      and other hybrid methods (such as those cited above), since these would be 
      the logical competitors. For the first experiment, it would also 
      be informative to compare directly to SDCA or SAG, and simply say that 
      their memory requirements do not allow them to be used in the second 
      experiment. For Figure 3, it would be informative to plot the 
      sub-optimality on a log-scale, to empirically verify that the method is 
      converging linearly.