===== A Lower Bound for the Optimization of Finite Sums =====
//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.
Alekh Agarwal and Léon Bottou: **A Lower Bound for the Optimization of Finite Sums**, //Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015//, 78--86, 2015.
\\
[[http://arxiv.org/pdf/1410.0723.pdf|ArXiv page]]
@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},
}