Projection-Free Bandit Optimization with Privacy Guarantees
Keywords:Online Learning & Bandits
AbstractWe 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.
How to Cite
Ene, A., Nguyen, H. L., & Vladu, A. (2021). Projection-Free Bandit Optimization with Privacy Guarantees. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 7322-7330. https://doi.org/10.1609/aaai.v35i8.16899
AAAI Technical Track on Machine Learning I