# On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2020.

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

- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [Non-Convex Federated Optimization under Cost-Aware Client Selection](https://mlsanity.com/paper/2512.05327/) (2025)

## Abstract (arXiv)

Recent advances in randomized incremental methods for minimizing L-smooth μ-strongly convex finite sums have culminated in tight complexity of tildeO((n+√n L/μ)log(1/ε)) and O(n+√nL/ε), where μ>0 and μ=0, respectively, and n denotes the number of individual functions. Unlike incremental methods, stochastic methods for finite sums do not rely on an explicit knowledge of which individual function is being addressed at each iteration, and as such, must perform at least Omega(n2) iterations to obtain O(1/n2)-optimal solutions. In this work, we exploit the finite noise structure of finite sums to derive a matching O(n2)-upper bound under the global oracle model, showing that this lower bound is indeed tight. Following a similar approach, we propose a novel adaptation of SVRG which is both compatible with stochastic oracles, and achieves complexity bounds of tildeO((n2+n√L/μ)log(1/ε)) and O(n√L/ε), for μ>0 and μ=0, respectively. Our bounds hold w.h.p. and match in part existing lower bounds of tildeOmega(n2+√nL/μlog(1/ε)) and tildeOmega(n2+√nL/ε), for μ>0 and μ=0, respectively.