# Projection-Free Bandit Optimization with Privacy Guarantees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2020.

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

- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)

## Abstract (arXiv)

We design differentially private algorithms for the bandit convex optimization problem in the projection-free setting. This setting is important whenever the decision set has a complex geometry, and access to it is done efficiently only through a linear optimization oracle, hence Euclidean projections are unavailable (e.g. matroid polytope, submodular base polytope). This is the first differentially-private algorithm for projection-free bandit optimization, and in fact our bound of widetildeO(T3/4) matches the best known non-private projection-free algorithm (Garber-Kretzu, AISTATS `20) and the best known private algorithm, even for the weaker setting when projections are available (Smith-Thakurta, NeurIPS `13).