Barzilai-Borwein Step Size for Stochastic Gradient Descent
One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization methods, the common practice in SGD is either to use a diminishing step size, or to tune a step size by hand, which can be time consuming in practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to automatically compute step sizes for SGD and its variant: stochastic variance reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective functions. As a by-product, we prove the linear convergence result of SVRG with Option I proposed in [10], whose convergence result has been missing in the literature. Numerical experiments on standard data sets show that the performance of SGD-BB and SVRG-BB is comparable to and sometimes even better than SGD and SVRG with best-tuned step sizes, and is superior to some advanced SGD variants.
The authors give a new analysis of SVRG. It allows using "Option I" (taking the final iterate of the inner iteration), as is done in practice. They also propose to use a scaled version of Barzilai-Borwein to set the step-sizse for SVRG (and heuristically argue that this could also be useful for classic stochastic gradient methods too). Their experiments show that this adaptive step-size is competitive with fixed step-sizes.  
Note that I increased my score in light of the experiments discussed in the author response.   I previously reviewed this paper for ICML. Below I've included some quotes from my ICML review that are still relevant. But first, I'll comment on some of the changes and lack of changes after the previous round of reviewing:  1. The authors have removed most of the misleading statements and included extra references and discussion, which I think makes the paper much better.  2. One reviewer brought up how the quadratic dependence on some of the problem constants is inferior to existing results. I'm ok with this as having an automatic step-size is a big advantage, but the paper should point out explicitly that the bound is looser. (This reviewer also pointed out that achieving a "bad" rate under Option I is easy to establish, although in this case I agree with the authors that this contribution is novel).  3. The paper is *still* missing an empirical comparison with the existing heuristics that people use to tune the step-size. The SAG line-search is now discussed in the introduction (and note that this often works better than the "best tuned step size" since it can increase the step-size as it approaches the solution) but there is no experimental comparison and the MISO line-search heuristic is still not even discussed. To me this is a strange omission: if the proposed method actually works better than these methods then including these comparisons only makes the paper stronger. Even if the proposed method works similarly to existing methods, it still makes the paper stronger because it shows that we now have a theoretically-justified way to get the same performance. Not including these comparisons is not only incomplete scholarship, but it makes the reader think there is something to hide. (I'm not saying there is something to hide, I'm just saying there are only good reasons to include these experiments and only bad reasons not to!)  4. One reviewer pointed out a severe restriction on the condition number in the previous submission, which has been fixed.  --- Comments from old review ---  Summary:  The authors give a new analysis of SVRG. It allows using "Option I" (taking the final iterate of the inner iteration), as is done in practice. They also propose to use a scaled version of Barzilai-Borwein to set the step-sizse for SVRG (and heuristically argue that this could also be useful for classic stochastic gradient methods too). Their experiments show that this adaptive step-size is competitive with fixed step-sizes.  Clarity:  The paper is very clearly-written and easy to understand (though many grammar issues remain).  Significance:  Although several heuristic adaptive step-size strategies exist in the literature, this is the first theoretically-justified method. It sill depends on constants that we don't know in general, but I believe is a step towards black-box SG methods.  Details:  Independent of the SVRG/SG results, the authors give a nice way to bound the step-size for the BB method.  Normally, BB leads to a much faster rate than using a constant step-size, but in the SVRG setting your theory/experiments are just showing that it does as well as the best step-size (which is good, but it isn't better than the best step size).  Finally, the paper would be much stronger if it compared to the two existing strategies that are used in practice: 1. The line-search of Le Roux et al.  where they increase/decrease an estimate of L. 2. The line-search of Mairal where he empirically tries to find the best step-size.  However, I don't think that the proposed approach would actually work better than both of these methods (but these older approaches don't have any theory).