# Efficient Convex Optimization with Membership Oracles

arXiv: https://arxiv.org/abs/1706.07357 · HTML: https://mlsanity.com/paper/1706.07357/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2017.

## Built on by (most cited first, 23 of 23)

- [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Quasi-Newton Steps for Efficient Online Exp-Concave Optimization](https://mlsanity.com/paper/2211.01357/) (2022)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [An Efficient Drifters Deployment Strategy to Evaluate Water Current Velocity Fields](https://mlsanity.com/paper/2301.04216/) (2023)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Minimum complexity interpolation in random features models](https://mlsanity.com/paper/2103.15996/) (2021)
- [Pseudonorm Approachability and Applications to Regret Minimization](https://mlsanity.com/paper/2302.01517/) (2023)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [A Hybrid Quantum-Classical Hamiltonian Learning Algorithm](https://mlsanity.com/paper/2103.01061/) (2021)
- [Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oracles](https://mlsanity.com/paper/2405.14090/) (2024)
- [Defensive Generation](https://mlsanity.com/paper/2602.21390/) (2026)
- [Random Separating Hyperplane Theorem and Learning Polytopes](https://mlsanity.com/paper/2307.11371/) (2023)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [The Geometry of Efficient Nonconvex Sampling](https://mlsanity.com/paper/2603.25622/) (2026)

## Abstract (arXiv)

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 tildeO(n2) oracle calls and tildeO(n3) 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.