A Lower Bound for the Optimization of Finite Sums

Alekh Agarwal, Leon Bottou

This paper presents a lower bound for optimizing a finite sum of $n$ functions, where each function is $L$-smooth and the sum is $\mu$-strongly convex. We show that no algorithm can…