Projection-Free Bandit Optimization with Privacy Guarantees

No. 8: AAAI-21 Technical Tracks 8

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Machine Learning I

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 matches the best known non-private projection-free algorithm and the best known private algorithm, even for the weaker setting when projections are available.

10.1609/aaai.v35i8.16899