Projection-Free Bandit Optimization with Privacy Guarantees
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.
Cite
Text
Ene et al. "Projection-Free Bandit Optimization with Privacy Guarantees." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I8.16899Markdown
[Ene et al. "Projection-Free Bandit Optimization with Privacy Guarantees." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/ene2021aaai-projection/) doi:10.1609/AAAI.V35I8.16899BibTeX
@inproceedings{ene2021aaai-projection,
title = {{Projection-Free Bandit Optimization with Privacy Guarantees}},
author = {Ene, Alina and Nguyen, Huy L. and Vladu, Adrian},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {7322-7330},
doi = {10.1609/AAAI.V35I8.16899},
url = {https://mlanthology.org/aaai/2021/ene2021aaai-projection/}
}