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

arXiv: https://arxiv.org/abs/1407.5144 · HTML: https://mlsanity.com/paper/1407.5144/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2014.

## Built on by (most cited first, 17 of 17)

- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Practical Network Acceleration with Tiny Sets: Hypothesis, Theory, and Algorithm](https://mlsanity.com/paper/2303.00972/) (2023)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation](https://mlsanity.com/paper/2606.00703/) (2026)
- [Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates](https://mlsanity.com/paper/2609.20701/) (2026)
- [Explainable Learning Rate Regimes for Stochastic Optimization](https://mlsanity.com/paper/2508.13639/) (2025)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)
- [Provable Quantum-Classical Separation for Continuous Gibbs Sampling](https://mlsanity.com/paper/2608.24527/) (2026)
- [Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps](https://mlsanity.com/paper/2609.09524/) (2026)
- [Nonsmooth Optimization via Orthogonalized Momentum](https://mlsanity.com/paper/2609.13677/) (2026)
- [Stabilizing Performative Feedback Loops with Minimal Model Deployments](https://mlsanity.com/paper/2609.14065/) (2026)
- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

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 Lp-ball for p ≥ 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.