A Lower Bound for the Optimization of Finite Sums

Alekh Agarwal, Léon Bottou

Introduction

In machine learning, optimizing an objective function that is the average of $n$ individual loss functions (plus a regularization term) is a foundational task known as Empirical Risk Minimization (ERM). Historically, researchers had to choose between two extremes:

  1. Batch Methods (e.g., Gradient Descent): These evaluate all $n$ functions for a single update. They converge quickly in terms of iterations but are computationally expensive per step when $n$ is large.
  2. Stochastic Methods (e.g., SGD): These evaluate just one random function per update. They are extremely fast per step but converge slowly due to the variance introduced by random sampling.

Recently, a new class of "incremental" methods—such as SAG, SVRG, and SAGA—has emerged. These methods promise the best of both worlds: the low per-iteration cost of SGD combined with the fast, linear convergence of batch methods. This paper asks a fundamental question: What is the absolute fastest any such incremental algorithm could possibly converge? By establishing a theoretical lower bound, the authors provide a benchmark that reveals exactly how much room is left for improvement in these popular optimization methods.

The Incremental First-Order Oracle (IFO) Framework

To rigorously determine this limit, the authors define a formal framework called the Incremental First-order Oracle (IFO). In this model, an optimization algorithm can select an index $i$ and a point $x$, and the oracle returns the value and gradient of the $i$-th function.

To prove the lower bound, the authors construct a "hard" problem instance in an infinite-dimensional Hilbert space. They design a specific set of "separable" functions, where each function only provides information about a small slice of the total solution. This structure forces any algorithm to discover the solution piece by piece, preventing shortcuts. By reducing this to classical optimization lower bounds (specifically building on the work of Nemirovsky and Yudin), they finalize the proof.

The Fundamental Limit and Condition Numbers

The paper's core result proves that to reach an error $\epsilon$, any IFO algorithm must perform at least the following number of iterations: $$ \Omega\left(n + \sqrt{n(\kappa - 1)} \log\frac{1}{\epsilon}\right) $$

A critical factor in this complexity is the condition number, $\kappa = L/\mu$, which represents the ratio of the smoothness ($L$) to the strong convexity ($\mu$) of the functions. In many machine learning settings, individual data points (and their corresponding functions) are much "rougher" ($L$) than the average function ($L_f$). Because the lower bound depends on the worst-case individual $L$, it suggests that incremental methods might be fundamentally limited by the worst-behaved data point in the set.

Algorithm Comparison: Worst-case vs. Reality

How do existing algorithms stack up against this new lower bound?

  • Batch Gradient Descent: Requires $\mathcal{O}(n \sqrt{\kappa} \log(1/\epsilon))$ iterations, which becomes significantly slower as the dataset size $n$ grows.
  • SVRG/SAGA: Have upper bounds of $\mathcal{O}((n + \kappa) \log(1/\epsilon))$.
  • Accelerated Incremental Methods: Algorithms like ASDCA or SPDC have upper bounds that more closely match the lower bound's $\sqrt{n\kappa}$ dependence.

However, matching the worst-case lower bound doesn't always translate to better practical performance.

Comparison of batch complexity and adaptivity for various algorithms.

As shown in the comparison above, while accelerated methods (ASDCA, SDPC) have tighter theoretical bounds, they are not adaptive to the average curvature of the data. In contrast, methods like SAG can adapt to the average strong convexity ($\mu_f$), which is often much more favorable than the worst-case $\mu$.

Algorithm complexity under different condition number regimes.

Furthermore, the performance hierarchy shifts depending on the condition number regime. When the condition number is relatively small ($\kappa = \mathcal{O}(n)$), standard incremental methods like SAG perform exceptionally well. Accelerated methods only show their theoretical superiority in the highly ill-conditioned regime ($\kappa \gg n$). This explains why SAG and SVRG often outperform accelerated methods on well-conditioned real-world problems, despite the accelerated methods having a "better" worst-case bound.

Limitations and Future Directions

While this paper establishes a crucial theoretical benchmark, it has a few notable limitations:

  • Training vs. Testing Error: The lower bound focuses entirely on training error (optimizing the empirical risk). In practice, machine learning prioritizes test error (generalization). For massive datasets, a single pass of simple SGD might still be superior because it directly optimizes for expected risk.
  • Worst-Case vs. Average-Case: The bound is a "worst-case" limit, applying to any set of $n$ functions. Real-world data is typically independent and identically distributed (I.I.D.). Future work could investigate whether an "average-case" lower bound for I.I.D. data is even lower, which might better reflect practical performance.
  • Oracle Restrictions: The findings strictly apply to algorithms constrained by the IFO model. Algorithms utilizing more complex information, such as the gradients of Fenchel conjugate functions used in certain dual methods, are not necessarily bound by these limits.

Summary updated

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 εin mini...
BibTeX
@inproceedings{agarwal2015lower,
  author = {Alekh Agarwal and Léon Bottou},
  title = {{A Lower Bound for the Optimization of Finite Sums}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
  url = {https://openreview.net/forum?id=SyNyvi-O-H},
}
Figure