Projection-Free Bandit Optimization with Privacy Guarantees

Authors

  • Alina Ene Boston University
  • Huy L. Nguyen Northeastern University
  • Adrian Vladu CNRS & IRIF, Universit√© de Paris

Keywords:

Online Learning & Bandits

Abstract

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.

Downloads

Published

2021-05-18

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16899

Issue

Section

AAAI Technical Track on Machine Learning I