Projection-Free Bandit Optimization with Privacy Guarantees
This work addresses privacy-preserving optimization for complex decision sets like matroid polytopes, where Euclidean projections are unavailable, making it relevant for applications in machine learning and data analysis.
The authors tackled the problem of bandit convex optimization in a projection-free setting with privacy constraints, achieving a regret bound of O~(T^{3/4}) that matches the best known non-private and private algorithms.
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 $\widetilde{O}(T^{3/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).