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:
- 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.
- 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.
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$.
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