mlsanityData to 14 Oct 2026

Projection-Free Bandit Convex Optimization

arXiv 1805.07474 ↗First posted 18 May 2018stat.ML cs.DS cs.LGcited by 17

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

17 papers.

Sort:

  1. 2022New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guaranteescited by 26
  2. 2022Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Setscited by 14
  3. 2021Projection-free Distributed Online Learning with Sublinear Communication Complexitycited by 13
  4. 2023Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guaranteescited by 13
  5. 2022Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learningcited by 11
  6. 2022An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regretcited by 10
  7. 2023Projection-free Online Exp-concave Optimizationcited by 10
  8. 2024From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimizationcited by 9
  9. 2021From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifoldscited by 6
  10. 2025Revisiting Projection-Free Online Learning with Time-Varying Constraintscited by 5
  11. 2021Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimizationcited by 3
  12. 2022Projection-free Online Learning with Arbitrary Delayscited by 3
5 more
  1. 2023Online Ad Procurement in Non-stationary Autobidding Worldscited by 1
  2. 2024Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximizationcited by 1
  3. 2021Scalable Projection-Free Optimizationcited by 0
  4. 2023Multi-point Feedback of Bandit Convex Optimization with Hard Constraintscited by 0
  5. 2026Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimizationcited by 0