# Projection-Free Bandit Convex Optimization

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2018.

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

- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Projection-free Distributed Online Learning with Sublinear Communication Complexity](https://mlsanity.com/paper/2103.11102/) (2021)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (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)
- [From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds](https://mlsanity.com/paper/2108.07406/) (2021)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization](https://mlsanity.com/paper/2102.07387/) (2021)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [Online Ad Procurement in Non-stationary Autobidding Worlds](https://mlsanity.com/paper/2307.05698/) (2023)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Multi-point Feedback of Bandit Convex Optimization with Hard Constraints](https://mlsanity.com/paper/2310.10946/) (2023)
- [Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization](https://mlsanity.com/paper/2607.25480/) (2026)

## Abstract (arXiv)

In this paper, we propose the first computationally efficient projection-free algorithm for bandit convex optimization (BCO). We show that our algorithm achieves a sublinear regret of O(nT4/5) (where T is the horizon and n is the dimension) for any bounded convex functions with uniformly bounded gradients. We also evaluate the performance of our algorithm against baselines on both synthetic and real data sets for quadratic programming, portfolio selection and matrix completion problems.