Efficient Convex Optimization with Membership Oracles
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 Grotschel, Lovasz and Schrijver.
Cite
Text
Lee et al. "Efficient Convex Optimization with Membership Oracles." Annual Conference on Computational Learning Theory, 2018.Markdown
[Lee et al. "Efficient Convex Optimization with Membership Oracles." Annual Conference on Computational Learning Theory, 2018.](https://mlanthology.org/colt/2018/lee2018colt-efficient/)BibTeX
@inproceedings{lee2018colt-efficient,
title = {{Efficient Convex Optimization with Membership Oracles}},
author = {Lee, Yin Tat and Sidford, Aaron and Vempala, Santosh S.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2018},
pages = {1292-1294},
url = {https://mlanthology.org/colt/2018/lee2018colt-efficient/}
}