Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
Many canonical machine learning problems boil down to a convex optimization problem with a finite sum structure. However, whereas much progress has been made in developing faster algorithms for this setting, the inherent limitations of these problems are not satisfactorily addressed by existing lower bounds. Indeed, current bounds focus on first-order optimization algorithms, and only apply in the often unrealistic regime where the number of iterations is less than O(d/n) (where d is the dimension and n is the number of samples). In this work, we extend the framework of Arjevani et al. [3, 5]  to provide new lower bounds, which are dimension-free, and go beyond the assumptions of current bounds, thereby covering standard finite sum optimization methods, e.g., SAG, SAGA, SVRG, SDCA without duality, as well as stochastic coordinate-descent methods, such as SDCA and accelerated proximal SDCA.
The authors provide lower bounds for smooth finite sum optimization which apply regardless of the dimension of the problem, and which match upper bounds given by certain iterative optimization methods like SDCA, SVRG, SAG, etc.          The authors begin with a discussion of the limitations of many established lower bounds for finite sum optimization - namely that they apply only when the number of iterations is less than d/n where d is the dimension of the problem and n is the number of components in the sum, and that this condition can be unrealistic in many problems. To avoid a dependence on the dimension of the problem, their lower bound proof requires making assumptions about the form of iterate updates made by the optimization algorithm. They define the notion of an oblivious, CLI algorithm, where updates are linear functions of previous iterates and oracle results, with parameters that are fixed (or scheduled) before the algorithm begins. In this framework, they show that for a certain class of functions parametrized by \eta, the kth iterate of the algorithm is an order-k polynomial in \eta. From here, they use existing function approximation theory to prove the existence of a function in their class for which the algorithm converges slowly to the optimum, completing the lower bound proof.       
        This was a very well-presented paper. It clearly presents a shortcoming of current lower bounds for finite sum optimization (that they apply only in large dimensions) and addresses it with a lower bound which is independent of the dimension of the problem. There are only a few very small issues with the presentation (I will mention those at the end of this section), and overall it is very clear.         This paper is an extension of [5] from single function optimization to finite sum, and uses the same analysis techniques in its proofs. Thus, it does not seem to be a massive leap forward in terms of novelty. Nevertheless, the authors' result here on finite sum optimization demonstrates the limitations of oblivious optimization algorithms, and clears up any questions about the complexity of finite sum optimization in low dimensions for many currently hot algorithms.          Two small mistakes:         - on line 193 in equation (10), C \in R^d rather than C \in R^{dxd}         - on line 202 in equation (12), it should be q^T w rather than q