Efficient Convex Optimization with Membership Oracles

[edit]

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).

Related Material