Optimal Learning for Multi-pass Stochastic Gradient Methods
We analyze the learning properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. In particular, we consider the square loss and show that for a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on a unifying approach, encompassing both batch and stochastic gradient methods as special cases.
This paper establishes optimal rates (up to log factors here and throughout this review) using multi-pass mini-batch SGM. Most results hold with moderately high probability (failure probability $1  - 1/m$), and it appears that all the guarantees are valid only for $m$ ``large enough'' (greater than $m_0$), which might not be known without additional information related to the capacity.  In the case of b = 1 (non-mini-batch), optimal rates are obtained by a method which depends on the capacity only through the stopping time (Corollary 3.3). Corollary 3.5 appears to be suboptimal; it is similar to Corollary 3.5 but involves taking $b = \sqrt{m}$. Corollaries 3.6 and 3.8 have stopping times ostensibly independent of the capacity, but either the learning rate (Corollary 3.6) or the batch size (Corollary 3.8) depend on the capacity. Corollary 3.9 is similar to Corollary 3.3 in the sense of providing a guarantee for a method that depends on the capacity only through the stopping time, but this later result now uses $b = m$, corresponding to a batch-like multi-pass SGM method.  Some experimental results exhibit the expected behavior from the bias and sample error.
This work provides a strong contribution in that it apparently is the first work to net optimal rates (up to log factors) for SGM, and moreover, it also handles a mini-batch analysis which includes the (full) batch method as a special case. Such rates previously had been established only for the (batch) ridge regression method.  My interpretation of what all the results actually show is given in the Summary.  I find the current solution of relying on cross-validation for adaptation to be a bit of an inelegant cop-out (even if there is a theoretically-supported method for using it); given that several of your corollaries provide a guarantee where $\zeta$ and $\gamma$ enter the picture only through $T^*$, can you provide a self-monitoring method that decides when to stop? In particular, I find the most exciting results to be Corollaries 3.3 and 3.9, as only the stopping time depends on the (unknown) capacity parameters, and so such an online stopping mechanism might be possible.  An issue with all of the results is that they are only valid for ``large enough'' $m$, which cannot be verified without knowing the unknown capacity parameters. I am somewhat willing to overlook this weakness, however, as it may be unavoidable.  It would have been useful if the authors briefly sketched, in the main paper, how they proved bounds on each of the three components in their error decomposition. Even a few sentences for each would suffice (given the space constraints, much more may be tricky). As I explain below, this will help both with the clarity of the technical portion and the impact of this work. I did not actually get much out of the experimental results near the end, so I would argue for partially cutting them in favor of giving readers more information about the technical novelty of your results and particular sub-results that might be reused in other works. This could help boost the impact of your work. At a minimum, the current way the Appendix reads is somewhat adversarial. For starters, the appendix is not searchable. It appears that it is just a sequence of images, which is rather annoying. Using 'pdfjam' in the future should lead to a proper splitting of PDFs without sacrificing the text-encoding. But most importantly, if you provide proof sketches in the appendix, then readers will have some idea of the overall argument, and this will help serve as a guide to the proofs. This will help with technical reuse so that other works can continue in this line. In its current state, the appendix is more or less a barrage of proofs without much indication of the overall strategy (I mean this constructively!). I therefore found the proofs very hard to check (although I read some of the initial proofs and they appear to be correct), and this certainly correlates to the results being hard to adapt.