In the membership‑oracle model, this paper establishes nearly quadratic lower bounds for randomized algorithms that perform linear optimization and uniform sampling over convex bodies. Let $K\subset\mathbb{R}^n$ be a convex body and assume we have access to an oracle that answers whether a query point $x$ belongs to $K$. The linear optimization problem is $$\max_{x\in K} c^{\top}x,$$ where $c\in\mathbb{R}^n$ is a given direction vector.
The authors construct a family of parameterised convex bodies such that any algorithm needs at least $\tilde{\Omega}(n^2)$ oracle calls to distinguish different instances, yielding the lower bound $$T_{\text{opt}}(n)=\tilde{\Omega}(n^2).$$ The $\tilde{\Omega}$ notation hides polylogarithmic factors in $n$. This matches the best known upper bound $\tilde{O}(n^2)$ (e.g., via ellipsoid methods or random‑walk based algorithms), showing that quadratic query complexity is essentially optimal in this model.
For uniform sampling—drawing an approximately uniform point from $K$—the paper proves $$T_{\text{sample}}(n)=\tilde{\Omega}(n^2),$$ improving upon the previously known linear lower bound. Since volume estimation reduces to uniform sampling, the same $\tilde{\Omega}(n^2)$ lower bound applies to volume computation.
The proof hinges on embedding the hidden‑hyperplane problem into a carefully designed family of convex bodies. These bodies are locally indistinguishable under few queries; only by probing a quadratic number of directions can an algorithm gather enough information to separate the instances. An information‑theoretic entropy argument then yields the required query count.
Key technical ideas
- The membership oracle provides only a binary “in/out” answer, without gradient or distance information.
- The constructed convex bodies are globally similar but differ subtly along specific directions.
- Randomized, adversarial instances force any algorithm to explore almost all directions.
Thus, in the pure membership‑oracle setting, linear optimization, uniform sampling, and volume estimation all incur a fundamental $\Theta(n^2)$ query cost up to polylogarithmic factors.
Review