mlsanityData to 14 Oct 2026

Efficient Convex Optimization with Membership Oracles

arXiv 1706.07357 ↗First posted 22 Jun 2017cs.DS cs.CG math.OCcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 4; 2023: 7; 2024: 4; 2025: 2; 2026: 2.

23 papers.

Sort:

  1. 2021Stateful Strategic Regressioncited by 32
  2. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  3. 2023Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agentscited by 25
  4. 2022Projection-free Adaptive Regret with Membership Oraclescited by 13
  5. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  6. 2022Quasi-Newton Steps for Efficient Online Exp-Concave Optimizationcited by 10
  7. 2023Projection-free Online Exp-concave Optimizationcited by 10
  8. 2024Online Convex Optimization with a Separation Oraclecited by 8
  9. 2025Swap Regret and Correlated Equilibria Beyond Normal-Form Gamescited by 8
  10. 2023An Efficient Drifters Deployment Strategy to Evaluate Water Current Velocity Fieldscited by 6
  11. 2021From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximizationcited by 5
  12. 2021Minimum complexity interpolation in random features modelscited by 5
11 more
  1. 2023Pseudonorm Approachability and Applications to Regret Minimizationcited by 5
  2. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
  3. 2024Computing Optimal Regularizers for Online Linear Optimizationcited by 4
  4. 2024Learning to Play Against Unknown Opponentscited by 3
  5. 2025Estimating Ising Models in Total Variation Distancecited by 3
  6. 2021A Hybrid Quantum-Classical Hamiltonian Learning Algorithmcited by 1
  7. 2024Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oraclescited by 1
  8. 2026Defensive Generationcited by 1
  9. 2023Random Separating Hyperplane Theorem and Learning Polytopescited by 0
  10. 2023Nonsmooth Projection-Free Optimization with Functional Constraintscited by 0
  11. 2026The Geometry of Efficient Nonconvex Samplingcited by 0