Breaking the Span Assumption Yields Fast Finite-Sum Minimization *
In this paper, we show that SVRG and SARAH can be modified to be fundamentally faster than all of the other standard algorithms that minimize the sum of n smooth functions, such as SAGA, SAG, SDCA, and SDCA without duality. Most finite sum algorithms follow what we call the "span assumption": Their updates are in the span of a sequence of component gradients chosen in a random IID fashion. In the big data regime, where the condition number κ = O(n), the span assumption prevents algorithms from converging to an approximate solution of accuracy in less than n ln(1/ ) iterations. SVRG and SARAH do not follow the span assumption since they are updated with a hybrid of full-gradient and component-gradient information. We show that because of this, they can be up to Ω(1 + (ln(n/κ)) + ) times faster. In particular, to obtain an accuracy = 1/n α for κ = n β and α, β ∈ (0, 1), modified SVRG requires O(n) iterations, whereas algorithms that follow the span assumption require O(n ln(n)) iterations. Moreover, we present lower bound results that show this speedup is optimal, and provide analysis to help explain why this speedup exists. With the understanding that the span assumption is a point of weakness of finite sum algorithms, future work may purposefully exploit this to yield faster algorithms in the big data regime.
Summary:  The authors consider the finite-sum minimization problem.   The work aims to investigate the “span condition” of modern variance reduced methods, and the role it plays in the complexity analysis of modern variance reduced methods. The span condition is satisfied for some method if the k-th iterate is formed as the starting iterate plus a linear combination of the stochastic gradients computed by the method. This condition is satisfied for many methods, including SAG, SDCA, SAGA, Finito and MISO. However, it is not satisfied for methods such as SVRG and SARAH.   The authors ask the question whether the lack of the span condition in methods such as SVRG and SARAH might lead to better complexity estimates, both in terms of lower and upper bounds. They give positive answer to this question.  In all results the authors assume all functions f_i to be smooth (with parameter L_i), and the average to be strongly convex (with parameter \mu). Specialized results are then proved in the case when the functions f_i are convex (CASE 1), and when they are not convex (CASE 2).  Clarity:   The paper is well written; the ideas are clearly introduced, motivated and explained.  Quality/Originality/Significance:  One of the key results of this paper (Theorem 2) is to show that in the regime when the condition number is not too large when compared to the number of functions (kappa = O(n)), the lower bound proved in [17] can be improved. This is done for CASE 1. The improvement is not very large, which is not surprising. In particular, in one expression, the term “n” is replaced by “n/(1+log(n/kappa))”. However, the relative improvement grows as n/kappa grows, and is clearly unbounded. The new lower bound is obtain by a modification/tightening of the bound obtained in [17]. Because of this, the tools used to obtain this result are not highly original. However, the result itself is quite interesting.  The second key result (Theorem 1/Corollary 2) is a modified analysis of SVRG (used with a different stepsize) which matches the newly established lower bound (again, for CASE 1). The result itself can be derived from the original SVRG analysis by a different choice of the parameters of the method (stepsize, number of steps in the inner loop, number of outer loops). Hence, the result can be seen as a rather elementary observation. Still, it is interesting that this observation was not explicitly made before.   Can you give examples of important problems or reasonable situations when one might expect n/kappa to be very large? This would strengthen the importance of the regime analyzed in this paper.  The paper does not contain any experiments. I view this as a major issue and this omission weakens the paper considerably. I’d like to see the difference, through experiments, offered by the logarithmic speedup. It should be possible to test this and clearly illustrate the benefits as n/kappa grows, even if this is done on a carefully constructed synthetic problems. Various types of experiments can be done and should have been done.     The authors provide a compelling explanation of why the “hybrid methods“ (i.e., methods such as SVRG that do not follow the span assumption) allow for this faster rate. This is done in Section 3.   Additional contributions:  a) Proposition 1: Provides a lower bound for SDCA (Omega(n log(1/eps))); which means that SDCA can not attain logarithmic speedup. Can SDCA be modified to allow for logarithmic speedup?  b) Section 4: Provides logarithmic speedup for SVRG in CASE 2. However, I do not see a lower bound provided for this case. Can you establish a lower bound?  Small issues:  1) Line 139: Missing right parenthesis 2) Line 139: “can can” -> “can” 3) Line 168: “X^*” -> “x^*” 4) Footnote 7: “sequence” -> “sequences” 5) Line 303: “shwartz” -> “Shwartz”  Comment: My answer to Q4 should be ignored (it's a dummy response; one should really have a NA option) since there are no computational results to be reproduced.   -----  POST AUTHOR FEEDBACK:  I've read the rebuttal, and the other reviews. I am keeping the same score.