Efficient Convex Optimization with Membership Oracles

2017/06/22 by Yin Tat Lee, Aaron Sidford, Lee, Yin Tat +3 · 2 citations
Computer Science · Decision Sciences · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Bandit Algorithms Research

paper · pdf · doi:10.48550/arxiv.1706.07357

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 O(n²) oracle calls and O(n³) 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, Lovasz and Schrijver.

Cited by

• Polynomial-Time Near-Optimal Estimation over Certain Type-2 Convex Bodies
• Estimating Ising Models in Total Variation Distance

Related

• A Simple Method for Convex Optimization in the Oracle Model
• Smooth Convex Optimization using Sub-Zeroth-Order Oracles
• Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
• Efficient Projection-Free Online Convex Optimization with Membership\n Oracle
• Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets