In the study of mathematical optimization, a "lower bound" is a theoretical speed limit. It tells us that no matter how clever an algorithm designer is, no algorithm can solve a specific class of problems faster than a certain threshold. While these limits are well-understood for deterministic algorithms—those that follow a fixed, repeatable path—the "power of randomness" introduces a complicating factor.
Researchers are currently working to determine whether stochasticity can circumvent these classical speed limits or if randomized algorithms are ultimately bound by the same geometric constraints as their deterministic counterparts.
The Deterministic Baseline and the Oracle Gap
To prove a lower bound, researchers typically use a "resisting oracle." Imagine an adversary who constructs a "hard" function as the algorithm explores it. For deterministic algorithms, this is straightforward: the oracle sees exactly where the algorithm will query next and ensures that the function remains flat or misleading in that specific direction.
Alekh Agarwal established fundamental lower bounds for the optimization of finite sums, which underpin most machine learning training. However, Agarwal noted a significant gap: resisting oracles do not naturally accommodate randomness. If an algorithm can flip a coin to decide its next query, the adversary cannot know for certain where to "hide" the function's minimum. This uncertainty suggests that randomized algorithms might, in theory, "guess" the optimal direction and beat the deterministic speed limit.
When Randomness Fails to Accelerate
Despite the intuitive hope that randomness might allow for faster exploration, several key results show that for many standard problems, the speed limit remains unchanged.
For example, in the case of minimizing a convex Lipschitz function, Blake Woodworth proved that randomized first-order methods still require at least $\Omega(1/\epsilon^2)$ queries. Even with the ability to sample directions stochastically, the algorithm cannot escape the fundamental complexity of the search space.
A similar "no-go" result exists for convex quadratic functions. Max Simchowitz linked this optimization problem to "planted vector" problems in random matrix theory. The intuition here is that in high-dimensional spaces, the probability of a randomized algorithm "stumbling" upon the optimal direction is so vanishingly small that it offers no better performance than Nesterov’s deterministic accelerated gradient descent. In these geometries, the $\Omega(\sqrt{\kappa})$ query barrier remains a hard ceiling.
The Finite Sum Exception
The most notable area where randomness does provide a provable advantage is in finite-sum optimization—problems where the objective is an average of $m$ individual functions.
Blake Woodworth demonstrated that randomized algorithms can achieve a $\sqrt{m}$ speedup over deterministic ones in this setting. This occurs because a randomized algorithm can sample individual components of the sum, gaining partial information about the global objective much faster than a deterministic algorithm that must process components in a fixed (and potentially exploitable) order. This result clarifies why stochastic methods like SVRG and SAGA are so effective in practice compared to full-batch gradient methods.
Expanding the Theory to Complex Landscapes
As optimization moves beyond simple convex functions, the quest for randomized lower bounds has expanded into more complex regimes:
- Minimax Optimization: For saddle-point problems (common in GANs), Junyu Zhang and Siqi Zhang have established iteration complexity limits. However, many of these proofs rely on the "linear span" assumption—that the algorithm only moves in directions defined by previous gradients. Proving these limits for all possible randomized algorithms remains an open challenge.
- PL Functions: For functions satisfying the Polyak-Łojasiewicz (PL) condition, Pengyun Yue showed that gradient descent is already optimal among deterministic methods. Whether stochasticity can break the $\Omega(\log 1/\epsilon)$ convergence rate for this broader class is still being debated.
- Global and Black-Box Optimization: In settings where we have no gradient information, Wenjie Xu and Colin Jones have used metric entropy to establish sample complexity limits. They highlight that while deterministic black-box search is inherently limited, the universal performance limits for randomized sampling strategies are not yet fully tightened.
Why It Matters: The Search for Robustness
The push to extend lower bounds to randomized algorithms is not just a theoretical exercise. It defines the boundaries of what is possible in machine learning. If a randomized lower bound matches a deterministic one, it tells practitioners that they should stop looking for a "magic" stochastic algorithm and instead focus on changing the problem structure (e.g., through better preconditioning or second-order information).
As Jelena Diakonikolas and Cristóbal Guzmán have shown in the context of parallel optimization, even throwing more processors at a problem cannot always overcome these sequential "speed limits." Understanding the interplay between randomness, parallelism, and objective geometry is the key to building the next generation of optimal training algorithms.