# Efficient Projection-Free Online Convex Optimization with Membership Oracle

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 59 references that are in the map.
- First posted on arXiv 10 Nov 2021.

## Builds on (most cited first, 7 of 7)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Curvature of Feasible Sets in Offline and Online Optimization](https://mlsanity.com/paper/2002.03213/) (2020)
- [Semidefinite descriptions of the convex hull of rotation matrices](https://mlsanity.com/paper/1403.4914/) (2014)
- [Gauge optimization and duality](https://mlsanity.com/paper/1310.2639/) (2013)
- [Conditional Accelerated Lazy Stochastic Gradient Descent](https://mlsanity.com/paper/1703.05840/) (2017)

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

- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence](https://mlsanity.com/paper/2302.08580/) (2023)
- [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)
- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Online Learning under Adversarial Nonlinear Constraints](https://mlsanity.com/paper/2306.03655/) (2023)
- [Projection-Free Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2402.08799/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access](https://mlsanity.com/paper/2502.16744/) (2025)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Randomized Midpoint Method for Log-Concave Sampling under Constraints](https://mlsanity.com/paper/2405.15379/) (2024)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [Safe Online Convex Optimization with Multi-Point Feedback](https://mlsanity.com/paper/2407.11471/) (2024)
- [Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization](https://mlsanity.com/paper/2608.30271/) (2026)
- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)
- [Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization](https://mlsanity.com/paper/2610.00254/) (2026)
- [Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints](https://mlsanity.com/paper/2610.13787/) (2026)

## Abstract (arXiv)

In constrained convex optimization, existing methods based on the ellipsoid or cutting plane method do not scale well with the dimension of the ambient space. Alternative approaches such as Projected Gradient Descent only provide a computational benefit for simple convex sets such as Euclidean balls, where Euclidean projections can be performed efficiently. For other sets, the cost of the projections can be too high. To circumvent these issues, alternative methods based on the famous Frank-Wolfe algorithm have been studied and used. Such methods use a Linear Optimization Oracle at each iteration instead of Euclidean projections; the former can often be performed efficiently. Such methods have also been extended to the online and stochastic optimization settings. However, the Frank-Wolfe algorithm and its variants do not achieve the optimal performance, in terms of regret or rate, for general convex sets. What is more, the Linear Optimization Oracle they use can still be computationally expensive in some cases. In this paper, we move away from Frank-Wolfe style algorithms and present a new reduction that turns any algorithm A defined on a Euclidean ball (where projections are cheap) to an algorithm on a constrained set C contained within the ball, without sacrificing the performance of the original algorithm A by much. Our reduction requires O(T log T) calls to a Membership Oracle on C after T rounds, and no linear optimization on C is needed. Using our reduction, we recover optimal regret bounds [resp. rates], in terms of the number of iterations, in online [resp. stochastic] convex optimization. Our guarantees are also useful in the offline convex optimization setting when the dimension of the ambient space is large.