Abstract: This paper presents a lower bound for optimizing a finite sum of n functions, where each function is L-smooth and the sum is µ-strongly convex. We show that no algorithm can reach an error $\epsilon$ in minimizing all functions from this class in fewer than $\Omega(n+\sqrt{n(\kappa-1)}\log(1/\epsilon))$ iterations, where $\kappa=L/\mu$ is a surrogate condition number. We then compare this lower bound to upper bounds for recently developed methods specializing to this setting. When the functions involved in this sum are not arbitrary, but based on i.i.d. random data, then we further contrast these complexity results with those for optimal first-order methods to directly optimize the sum. The conclusion we draw is that a lot of caution is necessary for an accurate comparison, and identify machine learning scenarios where the new methods help computationally.

We call the attention of the reader that the lower bound established in this paper is established the case of a deterministic optimization algorithm only. This limitation applies to both theorems 1 and 2. It arises because the resisting oracle construction works only for deterministic algorithm. This is an important because the best known algorithms discussed in section 2 are randomized algorithms (section 3 remains entirely valid). We believe that a comparable lower bound holds for randomized optimization algorithms and are working on a substantially different (and substantially more complex proof) for the randomized case. We shall update the ArXiV document as soon as we are entirely satisfied with the new proof.<p>

@inproceedings{agarwal-bottou-2015,
  author = {Agarwal, Alekh and Bottou, L{\'{e}}on},
  title = {A Lower Bound for the Optimization of Finite Sums},
  booktitle = {Proceedings of the 32nd International Conference on Machine Learning, {ICML} 2015, Lille, France, 6-11 July 2015},
  pages = {78--86},
  year = {2015},
  url = {http://leon.bottou.org/papers/agarwal-bottou-2015},
}