Efficient Convex Optimization with Membership Oracles

Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
Proceedings of the 31st Conference On Learning Theory, PMLR 75:1292-1294, 2018.

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{ö}tschel, Lov{á}sz, and Schrijver (1988).

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-lee18a, title = {Efficient Convex Optimization with Membership Oracles}, author = {Lee, Yin Tat and Sidford, Aaron and Vempala, Santosh S.}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {1292--1294}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/lee18a/lee18a.pdf}, url = {https://proceedings.mlr.press/v75/lee18a.html}, 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{ö}tschel, Lov{á}sz, and Schrijver (1988). } }
Endnote
%0 Conference Paper %T Efficient Convex Optimization with Membership Oracles %A Yin Tat Lee %A Aaron Sidford %A Santosh S. Vempala %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-lee18a %I PMLR %P 1292--1294 %U https://proceedings.mlr.press/v75/lee18a.html %V 75 %X 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{ö}tschel, Lov{á}sz, and Schrijver (1988).
APA
Lee, Y.T., Sidford, A. & Vempala, S.S.. (2018). Efficient Convex Optimization with Membership Oracles. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:1292-1294 Available from https://proceedings.mlr.press/v75/lee18a.html.

Related Material