In optimization theory, evaluating the efficiency of an algorithm requires answering two distinct questions:
- The Upper Bound: How fast does our current best algorithm solve a given class of problems?
- The Lower Bound: What is the absolute mathematical speed limit for any possible algorithm attempting to solve this same class of problems?
When the upper bound of an algorithm matches the lower bound of its problem class, the algorithm is considered optimal. However, across many domains in machine learning—ranging from non-convex stochastic optimization to minimax games—a persistent complexity gap remains.
This gap represents a fundamental blind spot. When an algorithm's performance lags behind a theoretical lower bound, we do not know whether our algorithm is poorly designed or if the lower bound itself is too loose to reflect the true mathematical difficulty of the landscape. Bridging this gap requires working from both sides: either by proving tighter lower bounds (proving the problem is inherently harder) or by designing faster algorithms (proving the problem is easier).
The Anatomy of a Complexity Gap
To build intuition, consider the challenge of finding a stationary point ($\|\nabla f(x)\| \le \epsilon$) in smooth, non-convex optimization. For years, standard stochastic gradient descent (SGD) was known to achieve an oracle complexity of $O(\epsilon^{-4})$. While variance-reduction techniques emerged to improve this rate, a significant gap remained between these practical algorithms and the absolute mathematical speed limits permitted by the underlying constraints of the problem class.
This specific gap was addressed by Cong Fang et al. in their work on the SPIDER framework (SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator). By tracking the optimization path using a specialized differential estimator, the authors closed the gap, hitting the mathematical speed limit for finite-sum non-convex optimization. Similarly, Zeyuan Allen-Zhu (How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD) pushed the boundaries of stochastic gradient methods to find points with small gradients faster than previously thought possible, narrowing the gap in the broader non-convex stochastic setting.
Standard SGD Complexity: O(ε⁻⁴) ──┐
├──► The Complexity Gap (Room for improvement)
True Mathematical Speed Limit ──┘
The Frontier of Unmapped Speed Limits
When we move beyond standard independent and identically distributed (i.i.d.) data or simple minimization objectives, the theoretical speed limits become much harder to map.
Non-i.i.d. and Markovian Data
Most classical optimization proofs assume that data points are sampled independently. In reinforcement learning or streaming applications, however, data arrives sequentially via a Markov chain, meaning the next data point depends heavily on the current state.
Zhenyu Sun et al. (Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling) tackled the historical gap between existing algorithms and theoretical limits in this setting, establishing tighter lower bounds to define the true speed limits under Markovian noise. When the data distribution is state-dependent—meaning the model's parameters actively alter the Markov chain—the problem becomes even more complex. As noted by Abhishek Roy et al. (Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data), while upper bounds have been established for projection-free methods in this domain, the fundamental lower bound remains an open question, leaving us uncertain if more efficient algorithms are mathematically possible.
Minimax Optimization
In generative adversarial networks (GANs) and adversarial robust training, optimization behaves like a multi-player tug-of-war formulated as a minimax problem ($\min_x \max_y f(x,y)$). Here, the complexity gaps are notoriously wide.
Chi Jin et al. (Near-Optimal Algorithms for Minimax Optimization) and Tianyi Lin et al. (On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems) highlighted that standard gradient descent-ascent (GDA) exhibits significantly higher gradient complexity than standard minimization tasks, leaving absolute lower bounds for nonconvex minimax landscapes unproven.
Even when a lower bound is known, algorithms often suffer from sub-optimal "logarithmic overhead"—unnecessary mathematical terms that slow down convergence in practice. This gap was recently resolved for smooth, strongly-convex-strongly-concave settings by Dmitry Kovalev et al. (The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization), who introduced an algorithm that completely eliminates this overhead to achieve absolute minimax optimality.
The Challenge of Non-Smoothness and Geometry
Complexity gaps frequently widen when we move away from well-behaved, smooth functions. In nonsmooth optimization (such as deep networks using ReLU activations), finding traditional stationary points can be mathematically impossible in finite time.
Hongzhou Lin et al. (Complexity of Finding Stationary Points of Nonconvex Nonsmooth Functions) and Guy Kornowski et al. (On the Complexity of Finding Small Subgradients in Nonsmooth Optimization) have shown that a massive discrepancy remains regarding the exact polynomial dependence on precision parameters, suggesting that current lower bounds are loose and fail to capture the true difficulty of navigating sharp, non-differentiable valleys.
Geometry also plays a critical role. When function smoothness and domain constraints are measured in mismatched norms (such as $\ell_p$ spaces vs. $\ell_q$ spaces), standard accelerated algorithms degrade. Cristóbal A Guzmán et al. (Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings) pointed out a large discrepancy between lower bounds and current algorithms in these nonstandard geometries, proving that our understanding of first-order oracle limits is still incomplete when moving outside traditional Euclidean spaces.
Why Closing Gaps Matters
Closing a complexity gap is not just an academic exercise; it prevents engineers from wasting effort trying to design an impossibly fast algorithm.
For example, in stochastic convex optimization, it was long debated whether gradient descent was uniquely vulnerable to high dimensions compared to general empirical risk minimization. Matan Schliserman (The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization) proved a tight lower bound showing that gradient descent fundamentally requires a number of samples proportional to the square root of the dimension ($\sqrt{d}$) to generalize in certain settings, exposing an inescapable curse of dimensionality for gradient-based methods.
Conversely, when an algorithm successfully closes a gap, it often introduces a powerful new mechanism. Weixin An (Kill a Bird with Two Stones: Closing the Convergence Gaps in Non-Strongly Convex Optimization by Directly Accelerated SVRG with Double Compensation and Snapshots) closed the oracle complexity gap for non-strongly convex finite-sum problems by introducing a "double snapshot" strategy that eliminated unnecessary logarithmic factors.
By constantly squeezing the space between what is algorithmically possible (upper bounds) and what is mathematically permitted (lower bounds), optimization theory provides a definitive map of the speed limits of machine learning.