Abstract
This paper introduces a unified, information-theoretic framework for proving lower bounds in nonsmooth convex optimization. By reducing the optimization task to a combinatorial "string guessing" problem, the authors establish that average-case (distributional) complexity is as challenging as worst-case complexity. This result effectively closes long-standing logarithmic gaps between the performance of randomized and deterministic algorithms. The framework provides matching lower bounds for standard algorithms across different accuracy regimes and geometric domains.
Introduction: The Oracle Complexity Challenge
In convex optimization, the "black-box oracle" model is a standard paradigm. Algorithms do not have access to a function's explicit form; instead, they query a point and receive a function value and a subgradient. The oracle complexity is the minimum number of queries required to find an $\epsilon$-approximate minimum.
Historically, establishing lower bounds—the minimum queries strictly necessary—has been difficult. Researchers often relied on "resisting oracles," adversarial strategies that adaptively modify the function to minimize information gain. These proofs were often technical, specific to certain function classes, and primarily addressed worst-case scenarios. A persistent logarithmic gap remained between the known complexity of randomized algorithms and their deterministic counterparts. This work seeks a single, intuitive source of hardness to explain these limits across all algorithm types.
Methods: From Optimization to Information Theory
The authors propose a three-step framework rooted in information theory to derive these bounds:
- The String Guessing Problem (SGP): The core of the hardness is identified as a combinatorial challenge: guessing a hidden bit-string where the oracle only reveals the index of the first incorrect bit. Using Shannon entropy and mutual information, the authors quantify the exact query complexity of SGP.
- Oracle Emulation: A reduction technique is developed to show that any algorithm capable of solving a nonsmooth convex optimization problem can be adapted to solve the SGP. Thus, the fundamental hardness of string guessing translates directly to optimization.
- The Lemma of Unpredictability: To account for "local oracles" that might reveal extra information, the authors employ random perturbations. They prove that adding infinitesimal noise to the function's location ensures that any local oracle provides no more information than a simple one-coordinate oracle.
Key Results and Insights
The primary insight is that nonsmoothness acts as an information bottleneck. Because the function can change abruptly, a single query provides only a localized, minimal amount of information about the global minimum.
Closing the Performance Gap
For $L^\infty$-boxes and $L^p$-balls, the authors demonstrate that randomized and worst-case complexities coincide. This eliminates the logarithmic gap previously suggested in classical literature (e.g., Nemirovski and Yudin), proving that randomized algorithms cannot significantly outperform deterministic ones in this setting.
Matching Known Upper Bounds
The derived lower bounds perfectly match the upper bounds of well-known algorithms across different regimes:
- High-Accuracy Regime: Matches the $\Theta(n \log 1/\epsilon)$ complexity of the Center of Gravity Method.
- Large-Scale Regime: Matches the $\Theta(1/\epsilon^2)$ complexity for $L^2$ and $\Theta(1/\epsilon^p)$ for $L^p$ domains, as achieved by Mirror Descent.
Conclusion and Future Directions
This work unifies the complexity analysis of nonsmooth optimization under a single information-theoretic umbrella. It proves that average-case hardness is fundamental and that the query counts hold with high probability for any algorithm, including those allowed a small failure probability.
The framework is currently tailored to nonsmooth functions. In smooth optimization, where gradients change continuously, algorithms can "look ahead," leading to different complexity scales (e.g., $1/\sqrt{\epsilon}$). Extending this information-theoretic approach to smooth functions or stochastic oracles remains a promising area for future research.
Summary updated