Dimension-Free Iteration Complexity of Finite Sum Optimization Problems

Abstract

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 $\mathcal{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., 2015) 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.

References in corpus (9)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
• An optimal randomized incremental gradient method
• SDCA without Duality
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems

Cited by in corpus (1)

• Optimal algorithms for smooth and strongly convex distributed optimization in networks