REVIEW 1 cited by
Efficient Convex Optimization with Membership Oracles
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We consider the problem of minimizing a convex function over a convex set given access only to an evaluation oracle for the function and a membership oracle for the set. We give a simple algorithm which solves this problem with $\tilde{O}(n^2)$ oracle calls and $\tilde{O}(n^3)$ additional arithmetic operations. Using this result, we obtain more efficient reductions among the five basic oracles for convex sets and functions defined by Gr\"otschel, Lovasz and Schrijver.
Forward citations
Cited by 1 Pith paper
-
Quantum algorithm for estimating volumes of convex bodies
A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.
Discussion (0). Continue with ORCID to comment.