A Simple Practical Accelerated Method for Finite Sums
We describe a novel optimization method for finite sums (such as empirical risk minimization problems) building on the recently introduced SAGA method. Our method achieves an accelerated convergence rate on strongly convex smooth problems. Our method has only one parameter (a step size), and is radically simpler than other accelerated methods for finite sums. Additionally it can be applied when the terms are non-smooth, yielding a method applicable in many areas where operator splitting methods would traditionally be applied.
This paper presents an accelerated variant of SAGA for finite sums. Accelerated algorithms are part of an important class of optimization methods which have a much better dependency to the condition number. There is recently been a lot of renewed interest in this class of methods and many papers have been published including accelerated SDCA or the Catalyst method. The authors here describe an accelerated version for SAGA in the regime when L/mu > n. They describe their method as “significantly simpler and requires less tuning than existing accelerated methods”.
Technical quality: To the best of my knowledge, the paper is technically sound and the proofs derived in the paper are correct and not hard to follow. There is not much intuition given as to why the modified step leads to an acceleration. I know accelerated methods are not always very intuitive but is there any intuition that could be gained from recent work on accelerated methods? e.g. the work of Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear coupling: An ultimate unification of gradient and mirror descent.", where the acceleration results from a primal-dual point of view on the progress of the algorithm.  Novelty/originality: The main problem with the paper is the novelty aspect of the work. Similar convergence rates for accelerated variance reduced SGD have already been derived in the catalyst paper as well as other references. One missing reference is Nitanda, Atsushi. "Accelerated Stochastic Gradient Descent for Minimizing Finite Sums." arXiv preprint arXiv:1506.03016 (2015). The authors claim that their method is “significantly simpler and requires less tuning than existing accelerated methods” but I think this point is quite controversial as one could claim that other methods also only have one parameter to tune. The authors acknowledge in the experimental section that “SDCA was chosen as the inner algorithm for the catalyst scheme as it doesn’t require a step-size, making it the most practical of the variants”. Furthermore, the only parameter described for the other baselines in the experimental section is the step-size (“The step-size parameter for each method (κ for catalyst-SDCA) was chosen using a grid search of powers of 2.“). I think this point is very ambiguous in the paper and needs to be rewritten with some compelling arguments as to why their method is simpler or this claim should be toned down. One positive contribution though is that the method proposed by the authors handles non-smooth loss which is not the case for most existing variance-reduced methods (expect SDCA). Could the authors elaborate on whether or not Theorem 7 guarantees a better convergence in comparison to SDCA?  Experimental section: In the experiments with the hinge loss (as a non-smooth objective), the convergence seems linear while their Theorem 7 provides a sub-linear convergence. Could the authors comment on a potential improvement for “nearly everywhere smooth loss functions” as done in the SDCA paper?  Minor: Lines 68-9: there is a typo where the sign of g_j^k is negative.