Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure
Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite sum, and the main candidate for optimization is the stochastic gradient descent method (SGD). In this paper, we introduce a variance reduction approach for these settings when the objective is composite and strongly convex. The convergence rate outperforms SGD with a typically much smaller constant factor, which depends on the variance of gradient estimates only due to perturbations on a single example.
Summary of the paper
====================
The paper considers the setting of finite-sum problems where each individual function undergoes a random pertuerbation. The authors devise an adapation of the finite-sums algorithm MISO\Finito, called S-MISO, for this setting, and provide a convergence analysis based on the noise (and the analytic) parameters of the model, along with supporting experiments on various datasets from different domains.
Evaluation
==========
The algorithm devised by the authors seems to effectively exploit the extra structure offered by this setting (in comparison to the generic stochastic optimization setting) - both theoretically where S-MISO is proven to improve upon SGD in a factor dependent on the overall variance and the average individual variance, and empirically, where S-MISO is shown to outperform SGD (designed for generic stochastic problems) and N-SAGA (designed for related settings). This setting subsumes important applications where data augmentation\perturbation have been proven successful (particularly, image and text classification), rendering it meaningful and interesting. 
On the flip side, the convergence analysis is somewhat loosely stated (e.g., the use of epsilon bar) and there are highly non-trivial user-specified parameters which have to be determined and carefully tuned. Moreover, although the expected performance on multi-layer network are considered in the body of the paper, they are not addressed appropriately in Section 4 where supporting experiments are presented (only 2-layers networks) - I find this very disappointing as this one of the main promises of the paper. Lastly, the paper is relatively easy-to-follow.
Comments
========
L8 - As convergence rates are usually stated using O-notation, it is not utterly clear how to inrepret 'smaller constant factor'.
L17 - What does 'simple' stand for? proximal-friendly?
L21 - Can you provide pointers\cross-reference to support 'fundamental'? Also, consider rephrasing this sentence.
L47 - Consider repharsing sentence.
L65 - Table 2: Data radius is not seemed to be defined anywhere in the text. 
L66 - How does concentrating on a quantity that depends only on the minimizer affect the asymptotic properties of the stated convergence analysis?
L69 - 'note that\nabla' is missing a space.
L77 - In what sense is this rate 'unimprovable'?
L78 - This pararaph seems somewhat out of place. Maybe put under 'realted work'?
L90 - This paragrpah too seems somewhat out of place (seems to be realted to section 4).
L116+L121 -  the wording 'when f_i is an expectation' is somewhat confusing.
L183+L185 - The use of epsilon bar is not conventional and makes it hard to parse this statement. Please consider restating the convergence analysis in terms of the pre-defined accuracy level (alterntaively, consider providing more explenatation of the upper bound parameters).
L192 - Can you elaborate more on concrete choices for gamma?
L198 - 'as large as allowed' in terms of EQ 9?
L200 - Figure 1: can you elaborate more on 'satisfies the thoery'? 
L208 - some expremients seem to be 400-epochs long.
L226 - Here and after, numbers are missing thousands separator.
L261 - Comparing could be more fair if a non-uniform version of SGD would be used.
L271 - Line seems out of place.