In the study of optimization, we often ask how fast an algorithm can work. But a more fundamental question is: how slow must it be? To answer this, researchers establish "speed limits"—mathematical lower bounds that define the minimum number of queries required to solve a problem.
The primary tool for proving these limits is adversarial function construction. Instead of analyzing an algorithm on a typical problem, researchers act as an "adversary" who designs a specific, difficult function to frustrate the optimizer. By showing that no algorithm can quickly solve these "trap" functions, they prove that the complexity of the entire problem class is fundamentally bounded.
The Resisting Oracle
The core intuition behind a lower bound is the concept of an Adversarial Oracle. Imagine you are trying to find the lowest point in a dark landscape using only a flashlight (queries). In a standard setting, the landscape is fixed. In an adversarial setting, the landscape is not fully determined until you point your light.
As shown by Christopher Criscitiello and Nicolas Boumal in their work on geodesically convex optimization, an adversary can maintain a set of "candidate" functions. Every time the algorithm queries a point, the adversary provides a response (like a gradient or function value) that is consistent with as many candidates as possible. This strategy, often called a resisting oracle, ensures that the algorithm gains the minimum possible information about where the true optimum lies.
Hiding the Needle in a Haystack
For global optimization, the adversary's goal is often to hide a "needle" (the global minimum) within a "haystack" (a large, flat region). Wenjie Xu and Colin Jones demonstrate this in their research on black-box optimization. They construct functions that evaluate to zero at every point the algorithm has sampled so far, while maintaining a deep, sharp minimum in the unexplored regions.
This construction forces any deterministic algorithm to perform an exhaustive search. If the algorithm stops too early, the adversary can simply "place" the minimum in the one spot the algorithm didn't look. This logic allows researchers to link the complexity of a function space—often measured by metric entropy—directly to the number of samples required to guarantee success.
Dimensionality and the Curse of Geometry
Adversarial constructions also reveal why certain geometries are harder than others. In high-dimensional non-convex spaces, Jean Honorio and Krishna Reddy Kesari proved that first-order methods can take exponential time to find a global minimizer. They do this by building a family of functions with an exponential number of local features, only one of which is the global optimum.
Geometry plays a similar role. While Nesterov’s acceleration provides a significant speedup in flat Euclidean space, Criscitiello and Boumal showed that negative curvature obstructs acceleration. By using distance functions relative to specific submanifolds, they created adversarial instances where the curvature itself prevents the algorithm from "looking ahead" effectively, proving that standard gradient descent is sometimes already optimal.
Why Stationary Points are Hard
Even if we lower our ambitions from finding a global minimum to just finding a stationary point (where the gradient is zero), adversarial traps still exist. Yoel Drori established that the $O(\epsilon^{-4})$ complexity for Stochastic Gradient Descent (SGD) is a fundamental limit. The adversarial functions used here are often specialized quadratics or sigmoid-like structures that act as "mathematical traps," forcing the algorithm to take a maximum number of steps to reduce the gradient norm.
Similarly, in one dimension, Sébastien Bubeck and Adil Salim used functions that adaptively respond to queries to maintain a large gradient for as long as possible. Their work highlights a key insight: the "hardness" of a problem often depends on what information the algorithm is allowed to see. By adding randomness or function value information, the adversarial traps can sometimes be bypassed, leading to massive theoretical speedups.
Summary of the Mechanism
Adversarial function construction works because it exploits the information gap between what an algorithm knows and what the function space allows. By building functions that are:
- Indistinguishable based on the algorithm's current query history, but
- Divergent in their optimal values or locations,
researchers like Ohad Shamir and Alekh Agarwal can prove that no algorithm—no matter how clever—can bypass the fundamental "speed limits" of optimization. These bounds tell us when our current algorithms are "as good as it gets" and where we must change our assumptions to find more efficient solutions.