Source-linked AI summary
A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
Santosh S. Vempala
TL;DR
Randomized membership-oracle algorithms for linear optimization and uniform sampling were known to have only linear lower bounds, despite a nearly quadratic upper bound for optimization. This paper constructs hard convex bodies and proves nearly quadratic lower bounds for optimization and sampling, extending the bound to volume estimation.
Problem
Previously known lower bounds for randomized membership-oracle algorithms for linear optimization and uniform sampling were linear in dimension.
Source: §1 · p. 1Method
The authors construct hard convex bodies and analyze membership-query transcripts as product partitions of hidden Gaussian rows.
Source: §1 · p. 1, §1.3 · p. 3Results
Ω(n^2/log^9 n) membership queries in expectation are required for linear optimization, uniform sampling, and volume estimation on some inputs in Cn.
Source: §1.1 · pp. 2–3Takeaways & Limitations
The optimization lower bound matches the known nearly quadratic upper bound up to a polylog factor, while the sampling bound improves on the previous linear lower bound.
Source: §1.1 · p. 3The stated bounds use bodies with polynomially bounded radius ratio and reductions may request inverse-polynomial accuracy and failure probability.
Source: §1.1 · p. 2
Abstract
from arXiv · showhide
We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.
1 Introduction
The introduction asks whether randomized membership-oracle algorithms for linear optimization and uniform sampling require superlinear query complexity. It answers with nearly quadratic lower bounds, extends the bound to volume estimation, and outlines a hard-body construction and product-partition proof.
1.2 The hard distribution
- The hard inputs are centrally symmetric parallelepipeds with polynomially bounded outer-to-inner radius ratio, and the proof distinguishes a pair even when the last Gaussian row is revealed.The pair differs in its long-axis constraint; the distinguishing task still requires Ω(n^2/log^9 n) queries in expectation.Source: §1 · p. 1, §1.2 · p. 3
1.1 Results
- Ω(n^2/log^9 n) membership queries in expectation are required for linear optimization, uniform sampling, and volume estimation on some inputs in Cn.The optimization theorem uses a constant-success guarantee for either stated approximation condition; sampling uses total variation distance 1/10, and volume estimation uses a factor-2 interval with probability at least 2/3.Source: §1.1 · pp. 2–3
- The optimization lower bound matches the known nearly quadratic upper bound up to polylogarithmic factors, even for constant-factor approximation.It also makes the dimension dependence of reductions among the five weak oracles optimal up to polylogarithmic factors, and contrasts with quantum membership access, which allows eO(n) optimization queries.Source: §1.1 · p. 2
- The paper’s setting differs from an earlier deterministic lower bound: it optimizes an explicit linear objective over an unknown body given by a membership oracle and applies to randomized algorithms.The paper states that its consequences do not follow from Kerger [14].Source: §1.1 · p. 2
1.3 Product partitions
- A transcript partitions hidden Gaussian rows into convex product parts, with each factor recording row values consistent with that transcript.For positive-measure parts, the hidden rows remain independent under their original Gaussian distributions restricted to the factors.Source: §1.3 · pp. 3–4
1.4 Proof overview
- Normal localization yields sign stability, then large relative entropy and exponentially small parts, which drive the query lower bound.The structural theorem says any substantial family of normal-localizing product parts contains a substantial subfamily of exponentially small parts.Source: §1.3 · pp. 4–5, §1.4 · p. 5
1. Normal localization implies sign stability.
Normal localization constrains each row’s residual direction, making determinant-sign changes rare on most localized parts. The argument compares short residuals under the restricted rows with their Gaussian baseline.
1. Normal localization implies sign stability.
- The sign-change probability ν is the chance that replacing a uniformly chosen row by an independent sample from its part changes the determinant sign; stability means ν < 1/64.For unrestricted Gaussian rows, ν = 1/2.Source: §1 · p. 5
- Conditioning on all rows except one, tight normal localization places that row’s residual near the line whose two directions correspond to the two determinant signs.If both signs remain likely, logconcavity and the covariance bound force mass near the origin; an unstable part has residual length at most t/√n with probability Ω(t).Source: §1 · p. 5
- For unrestricted Gaussian rows, the short-residual event has probability at most t²/2 and does not depend on the part’s localizing direction.Averaging over the partition bounds the total measure of unstable localizing parts by O(t).Source: §1 · p. 5
- The projected rows are scaled by √n so their Gaussian reference becomes standard, and their relative entropies are summed for the next argument.The projections are onto u⊥, where u is the part’s localizing unit vector.Source: §1 · pp. 5–6
2. Sign stability implies large relative entropy.
The proof rules out sign stability together with low relative entropy per squared dimension. Dimension reduction balances flip probability against entropy using a potential whose expected growth is controlled.
2. Sign stability implies large relative entropy.
- The reduction aims to preserve small flip probability and entropy divided by squared dimension while deleting rows and projecting into lower dimensions.The contradiction assumes ν < 1/64 together with the stated entropy bound.Source: §2 · p. 6
- After normalizing second-moment matrices to sum to dId, deleting a random row and projecting the others reduces total entropy while preserving expected flip probability.When each row has small entropy per coordinate, deletion removes Kd/d entropy in expectation, and projection removes nearly another Kd/d through Gaussian Brascamp–Lieb.Source: §2 · p. 6
- The potential Ψ = 2ν + q/q∗ balances flip probability against entropy, and the proof bounds its expected increase at each deletion step.For a row with large entropy per coordinate, deleting it saves enough entropy to compensate for a possible increase in flip probability; the accumulated multiplicative loss is constant.Source: §2 · p. 6
- If q exceeds q∗, entropy makes Ψ > 1; at dimension D with q ≤ q∗, small total entropy makes the row distribution close to independent Gaussians, whose flip probability is 1/2.Either boundary makes the potential large, contradicting a small initial potential when the induction carries the lower bound back to the starting dimension.Source: §2 · p. 6
3. Large relative entropy implies small part measure.
Restricting a Gaussian to a transcript factor has relative-entropy cost determined by that factor’s Gaussian measure. The retained localizing parts are the objects to which the entropy lower bound applies.
3. Large relative entropy implies small part measure.
- A Gaussian restricted to a factor Fi has relative entropy log(1/γ̄n(Fi)) against the original Gaussian, and data processing is applied to its scaled projection.This connects the Gaussian measure of a transcript factor to the projected-row entropy used in the bound.Source: §3 · p. 6
- Sign stability forces K ≥ cn²/log⁸ n on a retained part.The entropy is formed from relative entropies of scaled projections of the rows.Source: §3 · p. 6
- The retained parts together preserve at least half the original normal-localizing family’s measure.Source: §3 · p. 6
2 Preliminaries
The preliminaries establish notation and probability tools used in the proofs, including relative entropy, logconcavity, and Gaussian estimates.
2 Preliminaries
- The paper fixes notation for Euclidean and operator norms, Gaussian measures, projections, pushforward distributions, and symmetric-matrix ordering.The ambient dimension n is assumed to exceed a sufficiently large absolute constant.Source: §2 · p. 7
2.1 Relative entropy and total variation
- Relative entropy and total variation are introduced alongside entropy inequalities, data processing, and a coupling bound for total variation.For any coupling, total variation is at most the probability that the coupled variables differ.Source: §2.1 · pp. 7–8
2.2 Logconcavity
- The logconcavity preliminaries include covariance and moment bounds, as well as a tail bound for a one-dimensional logconcave random variable.The stated fourth-moment bound is (EY⁴)¹/² ≤ 4EY².Source: §2.2 · pp. 8–9
2.3 Gaussian estimates
- Gaussian estimates are proved using exponential Markov bounds and a sphere net for random-matrix operator norms, with an inverse-matrix tail bound also cited.The net argument bounds the operator norm by twice the largest |u⊤Rv| over pairs of net points.Source: §2.3 · p. 10
3 The product partition lower bound
This section develops the product-partition lower-bound argument, using normal localization to establish sign stability and an entropy bound, then combining that bound with Gaussian-restriction identities to control part measure. It also bounds the probabilities of parts in a high-mass subfamily and uses the result to derive a lower bound on decision-tree depth.
3 The product partition lower bound
- For independent rows with full-dimensional densities, the flip probability is the expected conditional variance of the determinant sign when one row is resampled.An invertible linear map preserves all flip probabilities.Source: §3 · p. 10
3.1 Normal localization implies sign stability
- Normal localization together with sign instability forces short row residuals; in particular, taking t=cη retains sign-stable measure at least η/2 from a localizing family of measure at least η.Source: §3.1 · pp. 11, 13
3.2 Sign stability implies large relative entropy
- For independent full-dimensional logconcave rows in sufficiently large dimension, small Gaussian relative entropy forces substantial determinant-sign flip probability.The proof uses induction on dimension, with a one-step potential bound that preserves expected flip probability under projection.Source: §3.2 · pp. 13, 14, 17
3.3 Large relative entropy implies small part measure
- The final step combines sign stability and the entropy lower bound through the relative-entropy identity for Gaussian restrictions to obtain a small-part-measure bound.The proof of Theorem 1.5 begins by setting t=cη.Source: §3.3 · p. 18
- Theorem 1.5’s subfamily has probability at least η/2, and each part has probability at most e^-h, where h = an^2 / log^8 n.The measure bound also yields the stated cardinality bound by summing part measures.Source: §3.3 · pp. 18–19
- For t = ⌊h/(2 log(2n + 1))⌋, the decision tree satisfies P(T > t) ≥ η/4 and t ≥ an^2/(8 log^9 n), yielding a lower bound on ET.The proof bounds the probability mass of subfamily parts at depth at most t by e^-h/2, then uses ET ≥ tP(T > t).Source: §3.3 · p. 19
4 Complexity in the oracle model
The section proves that distinguishing the hard pair requires many membership queries, then uses this bound to establish lower bounds for optimization, sampling, and volume estimation. Its argument links separating queries to localization of the hidden normal and bounds how quickly an algorithm can find one.
4.1 Distinguishing the hard pair
- The product-partition argument shows that a separating query localizes the hidden normal, and that a substantial family of such localized parts forces depth at least c1/8 n^2/log^9 n.After discarding parts of small total measure, retained parts have high conditional localization probability; the product-partition theorem then gives the depth bound.Source: §4 · p. 19, §4.1 · p. 20
- The proof couples runs on the two bodies: until the first separating query, their responses and stopping decisions match, so success requires a separating query with probability at least 1/3.A first separating query after the threshold entails more than that many queries in both runs.Source: §4.1 · p. 21
4.2 Optimization, sampling, volume
- For optimization, the two bodies have optimum values h and 3h, while for volume their ratio is three, making the stated guarantees incompatible across the pair.For sampling, the uniform distribution on the larger body assigns probability 2/3 to the region outside the smaller body, so a sample can yield a separating query.Source: §4.2 · pp. 21–22
- For optimization, sampling, and volume estimation, the common argument yields an input with query tail and expectation lower bounds of Ω(n^2/log^9 n).The task-specific guarantees make the two bodies distinguishable, forcing a separating query before the algorithm stops.Source: §4.2 · pp. 21–22