A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

Santosh S. Vempala

cs.DSSep 24, 2026

A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

Authors: Santosh S. Vempala

Organizations: Georgia Tech

Abstract

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.

Explore similar work

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirFirst Order Oracle Complexity Lower Bounds
Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1
Lower Bounds for Linear-Oracle Online Learning
Sep 29, 2026Mohit Sinha\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Lower Bounds
Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
Sep 17, 2026David Martínez-Rubio, Cristóbal GuzmánConvex Optimization Lipschitz Continuity
IMDEA Software Institute, Madrid, Spain · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile

Jul 21, 2026, cs.DSJ/K move · Enter open · S save

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

Michael Menart, Aleksandar Nikolov, Ohad Shamir

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto+1

First Order Oracle Complexity Lower Bounds Convex Optimization Nonconvex

Open paper AskPDF arXiv

We prove two lower bounds for the first order oracle complexity of minimizing a

d

-dimensional

1

-Lipschitz convex function over the unit ball with

m

bits of memory. We first show that any such (possibly randomized) algorithm must make

\tildeΩ(\frac{d^2}{\sqrt{m}})

oracle queries. For deterministic optimization algorithms, we show that

\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})

queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of

\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})

and

\tildeΩ(\frac{d^{5/3}}{m^{1/3}})

for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around

m\approx d^2

, where a polylogarithmic change in memory leads to a

\mathsf{poly}(d)

change in the number of required oracle calls. Further, when the suboptimality is polynomially small in

d

, our lower bound randomized algorithms is the first to show that

\tildeΩ(d^2)

memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in

d

Abstract

Explore similar work

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

Lower Bounds for Linear-Oracle Online Learning

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates