# A Lower Bound for the Optimization of Finite Sums

arXiv: https://arxiv.org/abs/1410.0723 · HTML: https://mlsanity.com/paper/1410.0723/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2014.

## Built on by (most cited first, 13 of 13)

- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization](https://mlsanity.com/paper/2302.08766/) (2023)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization](https://mlsanity.com/paper/2102.09893/) (2021)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Faster Convergence of Riemannian Stochastic Gradient Descent with Increasing Batch Size](https://mlsanity.com/paper/2501.18164/) (2025)
- [Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods](https://mlsanity.com/paper/2103.04413/) (2021)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)

## Abstract (arXiv)

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 ε in minimizing all functions from this class in fewer than Omega(n + √n(kappa-1)log(1/ε)) iterations, where kappa=L/μ 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.