# Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization

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

## Key facts

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

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

- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)

## Abstract (arXiv)

We study the conditions under which one is able to efficiently apply variance-reduction and acceleration schemes on finite sum optimization problems. First, we show that, perhaps surprisingly, the finite sum structure by itself, is not sufficient for obtaining a complexity bound of tildecO((n+L/μ)ln(1/ε)) for L-smooth and μ-strongly convex individual functions - one must also know which individual function is being referred to by the oracle at each iteration. Next, we show that for a broad class of first-order and coordinate-descent finite sum algorithms (including, e.g., SDCA, SVRG, SAG), it is not possible to get an `accelerated' complexity bound of tildecO((n+√n L/μ)ln(1/ε)), unless the strong convexity parameter is given explicitly. Lastly, we show that when this class of algorithms is used for minimizing L-smooth and convex finite sums, the optimal complexity bound is tildecO(n+L/ε), assuming that (on average) the same update rule is used in every iteration, and tildecO(n+√nL/ε), otherwise.