TL;DR
This paper introduces a unified, information-theoretic framework to establish tight lower bounds on the oracle complexity of nonsmooth black-box convex optimization. By identifying a simple combinatorial problem—string guessing—as the fundamental source of mathematical hardness, the authors prove that randomized and average-case algorithms cannot outsmart worst-case limits, effectively closing long-standing complexity gaps for standard optimization domains.
What Problem Does This Paper Address?
In black-box convex optimization, we want to find the minimum of a convex function $f$ over a domain $X$. However, we don't know the explicit formula for $f$; we can only interact with it by querying a local "oracle" that returns the function's value and a subgradient at any chosen point. The fundamental question is: What is the minimum number of queries (oracle complexity) required to find an $\varepsilon$-accurate solution?
While classic optimization theory (dating back to Nemirovski and Yudin in the 1970s) established worst-case lower bounds using complex geometric "resisting oracles," two major gaps remained:
- The Randomization Gap: Can randomized algorithms or average-case (distributional) approaches beat these worst-case limits? Prior work suggested a logarithmic gap between randomized and deterministic complexities.
- Lack of Unification: Lower bounds for different domains (like the $L^\infty$-box vs. $L^p$-balls) required completely different, highly technical geometric proofs.
This paper addresses both issues by providing a clean, unified framework rooted in information theory.
Methods
The authors swap out complicated geometric constructions for a game of information theory. Their approach relies on three core pillars:
- The String Guessing Problem (SGP): The authors define a purely combinatorial game where an algorithm tries to identify a hidden binary string by guessing prefixes. The oracle only tells the algorithm the index of its first incorrect bit. Using information theory (specifically Fano's Inequality), they prove a strict lower bound on how many guesses are required to find the string.
- Oracle Emulation: To connect string guessing to optimization, the authors introduce a rigorous reduction mechanism called oracle emulation. They construct specific families of nonsmooth convex functions where finding the minimum point is mathematically equivalent to guessing the hidden string.
- Random Perturbations & Unpredictability: To extend their bounds from simple, idealized oracles to any arbitrary local oracle, the authors introduce random perturbations to their function families. They prove a "Lemma of Unpredictability," showing that with probability 1, an arbitrary oracle cannot leak any more useful information than the idealized one.
Datasets
Not discussed in the paper. This is a purely theoretical paper focused on mathematical proofs and complexity bounds; no empirical datasets or benchmarks were used.
Key Insights and Ideas
- Optimization as Information Retrieval: The core conceptual leap is that nonsmooth optimization is fundamentally about gaining information about a hidden string. If each oracle query yields very little information on average, the algorithm simply cannot converge quickly.
- The Root of Hardness: Instead of treating different domains and scales as separate mathematical problems, this paper unifies them by showing they all inherit their hardness from the exact same source: the combinatorial difficulty of string guessing.
- Randomization Doesn't Help Nonsmooth Problems: A major "aha" moment is the realization that average-case complexity, high-probability complexity, randomized complexity, and worst-case complexity all tightly coincide for these problem classes. Randomizing your query steps does not give you an informational advantage when the objective function is nonsmooth.
Key Results
The paper successfully matches all classical worst-case lower bounds but extends them to much stronger distributional and high-probability settings, closing the gap between randomized and deterministic methods.
- The $L^\infty$-Box Domain: For optimization over $[-1, 1]^n$, the distributional oracle complexity is tightly bounded by $\Omega(n \log(LR/\varepsilon))$.
- The $L^p$-Ball Domain: The framework perfectly captures the two distinct operational regimes of the $L^p$-ball (as illustrated in Figure 1):
- Low-scale (High Accuracy): Where the complexity depends on the dimension, scaling as $\Omega(n \log 1/\varepsilon)$.
- Large-scale (Low Accuracy): Where the complexity becomes independent of the dimension, scaling as $\Omega(1/\varepsilon^{\max\{p,2\}})$.
Limitations and Future Work
The authors explicitly note that this work is restricted to deterministic local oracles under a black-box model. It does not cover stochastic oracles, where the oracle answers are corrupted by random noise—a setting highly relevant to modern machine learning (e.g., Stochastic Gradient Descent).
Additionally, the authors point out that alternative formulations of the string guessing problem exist in literature (such as predicting one bit at a time with advice) and suggest that exploring connections between those variations and online convex optimization could be a fruitful direction for future research.
Summary updated