When we design an optimization algorithm, we want to know if it can be improved. To prove that an algorithm is optimal, it is not enough to show that it performs well across a variety of tasks; we must prove that no other algorithm can perform fundamentally better. This is achieved by establishing a theoretical lower bound.
To prove a lower bound, theorists play the role of an adversary. They mathematically construct "hard instances"—worst-case objective functions, data distributions, or oracles—that systematically exploit the specific update rules and information bottlenecks of a class of algorithms. By forcing the algorithm to perform as poorly as possible, these adversarial constructions map out the absolute speed limits of optimization.
Hiding Information via Indistinguishability
The most direct way to stymie an optimization algorithm is to withhold information. If an adversary can construct two different functions that yield identical feedback for a given number of queries, the algorithm cannot possibly know which function it is actually optimizing.
Yaron Singer et al. utilized this exact mechanism in Information-theoretic lower bounds for convex optimization with erroneous oracles. By constructing pairs of indistinguishable functions where an adversarial oracle returns identical values despite the functions having vastly different global optima, the authors demonstrated that convex optimization becomes highly fragile when even tiny, non-random errors are introduced. Similarly, in the context of data-driven optimization, Eric Balkanski et al. proved in Minimizing a Submodular Function from Samples that a family of submodular functions can be engineered to look completely identical over a specific sample distribution while hiding entirely different global minima, rendering optimization from samples impossible beyond a certain threshold.
When algorithms only have access to noisy function values rather than exact gradients, this indistinguishability can be framed statistically. Ohad Shamir demonstrated in On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization that by constructing adversarial function instances that remain statistically indistinguishable under noisy observations, one can prove a fundamental quadratic dependence on the problem's dimension ($d^2$) for derivative-free optimization.
Algorithm Queries Point X ───> [ Adversarial Oracle ]
│
├── Looks at Candidate Function A
├── Looks at Candidate Function B
│
<─── Returns Identical Value/Gradient
(Hides which function is real)
Instead of choosing a static pair of functions, an adversary can also construct a resisting oracle that adapts dynamically to the algorithm's queries. As detailed by Christopher Criscitiello et al. in Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles, a resisting oracle maintains a pool of candidate objective functions. Every time the algorithm queries a gradient, the oracle answers in a way that is consistent with the largest possible subset of candidates, effectively delaying the discovery of the true minimizer for as long as possible. This dynamic strategy is a cornerstone for proving lower bounds in diverse settings, from finding stationary points in one dimension (Sebastien Bubeck et al.) to optimizing regularized convex functions (Nikita Doikov).
High-Dimensional Traps and Orthogonal Progress
First-order algorithms, such as Gradient Descent (GD) and Stochastic Gradient Descent (SGD), navigate the optimization landscape by following local slope information. To slow these algorithms down, an adversary can construct high-dimensional functions that force the optimizer to discover only one dimension at a time.
Consider a function designed such that the gradient at the current iterate only points toward the next coordinate axis. The algorithm is effectively forced to make orthogonal steps, exploring the space via a slow, coordinate-by-coordinate crawl. Christopher Liaw et al. used this exact architecture in Tight analyses for non-smooth stochastic gradient descent. By designing high-dimensional, strongly convex functions that induce periodic error spikes through orthogonal gradient steps, the authors proved that the final iterate of SGD is fundamentally slower than the running average of its iterates. To map out how this penalty scales with dimensionality, Daogao Liu et al. constructed a non-smooth convex function by taking the maximum of multiple hyperplanes combined with quadratic regularization, forcing a dimension-dependent $\Omega(\log d)$ penalty on the final iterate.
Iterate 0 (0,0,0) ───[Gradient points to x1]───> Iterate 1 (1,0,0)
│
[Gradient points to x2]
│
▼
Iterate 3 (1,1,1) <───[Gradient points to x3]─── Iterate 2 (1,1,0)
This high-dimensional trapping mechanism also applies to non-convex optimization under relaxed smoothness conditions. In Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness, Michael Crawshaw et al. constructed adversarial functions using high-dimensional biased random walks. This construction forces adaptive gradient algorithms like AdaGrad to suffer from an unavoidable quadratic dependence on problem parameters, demonstrating that sophisticated step-size adaptation cannot always bypass the structural traps set by high-dimensional geometry.
Spectral and Geometric Obstacles
When an adversary cannot rely on non-smooth "sharp corners" to cause spikes, they must exploit the smooth geometry of the landscape. For smooth or quadratic functions, this is achieved by manipulating the spectrum (the eigenvalues) of the Hessian matrix or by stitching together smooth pieces to create internal drift.
In Dimension-Free Iteration Complexity of Finite Sum Optimization Problems, Yossi Arjevani et al. established lower bounds by constructing adversarial quadratic functions with highly specific eigenvalue distributions. By designing a Hessian spectrum that makes polynomial approximation difficult, the authors proved that algorithms using fixed, non-adaptive step sizes face a fundamental speed limit that cannot be overcome simply by increasing the problem's dimensionality.
In distributed and permutation-based optimization, the primary vulnerability is gradient drift—the phenomenon where local updates on subsets of data pull the parameters away from the global optimum. To expose the limits of these methods, adversaries construct piecewise-quadratic landscapes:
- Local SGD: Blake Woodworth et al. designed specific piecewise-quadratic functions in Is Local SGD Better than Minibatch SGD? to identify the exact regimes where local updates cause algorithms to drift onto suboptimal paths, proving that Local SGD can perform worse than simple Minibatch SGD on general convex functions.
- Shuffling SGD: Instead of picking data with replacement, practical training shuffles the dataset once per epoch. Shashank Rajput et al. constructed piecewise-quadratic functions in Closing the convergence gap of SGD without replacement to isolate the internal gradient drift caused by this ordering, establishing the information-theoretic limits of data shuffling.
For min-max optimization (saddle-point problems), the geometric challenge is entirely different: algorithms tend to cycle endlessly around the optimum rather than converging to it. To prove lower bounds for these algorithms, Noah Golowich et al. turned to bilinear functions in Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems. Because bilinear structures represent the purest mathematical expression of rotational, non-convergent vector fields, analyzing them allowed the authors to prove a fundamental "quadratic separation"—showing that the last iterate of the Extragradient algorithm converges significantly slower than the average of its iterates.
Exploiting Noise, Flatness, and Stability
Hard instances do not always rely on intricate geometric shapes; they can also be constructed by manipulating the interaction between an algorithm's operators, its noise distributions, and the data itself.
For example, gradient clipping is widely used to stabilize training, but it introduces a stochastic bias because it alters the magnitude of noisy updates. In Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees, Anastasia Koloskova et al. proved tight lower bounds for clipped SGD by designing specific, adversarial noise distributions paired with stochastic functions. This construction isolated the exact mathematical penalty introduced by the clipping operator, proving it creates an unavoidable barrier to reaching the true optimum.
True Stochastic Gradient ───> [ Clipping Operator ] ───> Biased Update Step
▲
Adversarial Noise Distribution
(Engineered to maximize bias)
Alternatively, an adversary can exploit the asymptotic flatness of a loss function. In Logistic Regression: Tight Bounds for Stochastic and Online Optimization, Elad Hazan et al. constructed worst-case probability distributions that exploit the flat tails of the logistic loss function. By forcing the optimizer into regions where the gradient vanishes exponentially, they proved that despite its smoothness, logistic regression is bound to the same slow convergence rates as non-smooth optimization within practical iteration counts.
Finally, this adversarial approach is essential for understanding generalization. To determine whether an algorithm overfits, researchers construct adversarial loss functions and data distributions that force the algorithm into its worst possible generalization behavior. Yikai Zhang et al. used this technique in Stability of SGD: Tightness Analysis and Improved Bounds to prove that existing stability bounds for convex functions are mathematically tight. To map the boundaries of overfitting in smooth stochastic convex optimization, Jiaye Teng et al. constructed high-dimensional quadratic loss functions to demonstrate exactly when and why longer training leads to benign or catastrophic overfitting.
Key Foundational Work
Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization (2010) — contributed 1 concept elements to this direction.
Lower Bounds on Rate of Convergence of Cutting Plane Methods (2010) — contributed 1 concept elements to this direction.
Optimal strategies and minimax lower bounds for online convex games [Technical Report No. UCB/EECS-2008-19] (2008) — contributed 1 concept elements to this direction.