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 $\mu$-strongly convex. We show that no algorithm can reach an error $\epsilon$ in minimizing all functions from this class in fewer than $\Omega(n + \sqrt{n(\kappa-1)}\log(1/\epsilon))$ iterations, where $\kappa=L/\mu$ 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.
Introduction
In machine learning, the standard objective is to minimize a "finite sum" of loss functions: an average loss over $n$ training examples. Traditionally, researchers have navigated a trade-off between batch methods (like Gradient Descent), which are stable but computationally expensive per iteration, and stochastic methods (like SGD), which are fast per step but require many iterations to achieve high precision.
Recently, a new class of "incremental" algorithms, including SAG, SVRG, and SAGA, has emerged. These methods promise the best of both worlds: the low per-step cost of SGD combined with the fast, linear convergence of batch methods. This paper addresses a fundamental question: What is the theoretical "speed limit" for these incremental methods? Is there a floor that no algorithm can cross?
Methods: The Incremental First-order Oracle
The authors define a formal framework called the Incremental First-order Oracle (IFO). In this model, an algorithm can select a specific data point index $i$ and query its value and gradient. To establish a lower bound, the authors utilize a "separable objective" construction. They design a "hard" optimization problem where the global function is partitioned into $n$ components, each acting on a disjoint set of coordinates in a high-dimensional space. Because these components are independent, the algorithm is effectively forced to solve $n$ separate optimization sub-problems. By applying classic lower bounds for single-function optimization (Nemirovsky-Yudin bounds), they aggregate these costs to determine the total complexity for the finite sum.
Key Insights and Complexity Results
The core result of the paper is a lower bound on the number of IFO calls ($K$) required to reach an error $\epsilon$: $$K = \Omega\left(n + \sqrt{n(\kappa - 1)} \log(1/\epsilon)\right)$$
This lower bound consists of two distinct terms:
- The Discovery Cost ($n$): An algorithm must examine every data point at least once to understand the global function's landscape.
- The Conditioning Cost ($\sqrt{n\kappa}$): This term indicates how difficulty scales with the condition number $\kappa = L/\mu$, which measures the curvature of the optimization surface.
As shown in Table 1, different algorithms exhibit varying levels of adaptivity. While some methods have strong worst-case guarantees, others like SAG can exploit the actual curvature of the data (adapting to $\mu_f$), which often leads to superior practical performance.
Comparing Upper and Lower Bounds
When comparing the derived lower bound to the upper bounds of existing state-of-the-art algorithms, a significant gap is revealed. For example, methods like SAG and SVRG have a complexity of $O((n + \kappa) \log(1/\epsilon))$.
Table 2 illustrates this gap, particularly in the $\kappa \gg n$ regime. The difference between the $O(\kappa)$ term in current algorithms and the $\Omega(\sqrt{n\kappa})$ term in the lower bound suggests that current algorithms might be improved—potentially through acceleration techniques—or that the lower bound itself could be further refined.
Limitations and Future Work
Several important caveats remain. First, the current proof applies strictly to deterministic algorithms. Since many modern incremental methods are randomized, extending this bound to the randomized setting is a critical next step. Second, the analysis focuses on training error, whereas machine learning practitioners primarily care about test error (generalization). An algorithm that is slower at minimizing training error might reach optimal generalization performance more quickly. Finally, the bound assumes arbitrary functions; future work could explore if tighter bounds are possible by assuming functions are drawn from a common probability distribution (i.e., i.i.d. data).
Summary updated