Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory

Gábor Braun, Cristobal Guzman, Sebastian Pokutta

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:

  1. 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.
  2. 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.
  3. 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.
Construction of hard function instances used in the reduction to the string guessing problem.

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.
The complexity landscape showing different regimes and how lower bounds match known algorithmic performance.

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

Abstract

We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst-case oracle complexity. We obtain strong lower bounds on distributional oracle complexity for the box $[-1,1]^n$, as well as for the $L^p$-ball for $p \geq 1$ (for both low-scale and large-scale regimes), matching worst-case upper bounds, and hence we close the gap between distributional complexity, and in particular, randomized complexity, and worst-case complexity. Furthermore, the bounds remain essentially the same for high-probability and bounded-error oracle complexity, and even for combination of the two, i.e., bounded-error high-probability oracle complexity. This considerably extends the applicability of known bounds.
BibTeX
@article{braun2014lower,
  author = {Gábor Braun and Cristobal Guzman and Sebastian Pokutta},
  title = {{Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  doi = {10.1109/tit.2017.2701343},
}
Figure