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 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, NeurIPS13).
Introduction
In online learning, an agent makes a sequence of decisions to minimize regret—the difference between their total loss and the loss of the best fixed decision in hindsight. While standard online convex optimization (OCO) is well-understood, real-world applications often introduce three simultaneous challenges: bandit feedback, complex constraints, and privacy requirements.
Prior to this work, no existing algorithm could handle all three constraints. This paper introduces PRIVATEBANDIT, the first differentially private algorithm for projection-free bandit convex optimization. Remarkably, the algorithm achieves regret bounds that match the state-of-the-art for non-private projection-free methods, effectively providing privacy "for free" in terms of the iteration count $T$.
Problem Formulation
The Three Pillars of the Challenge
- Bandit Feedback: The agent only observes the loss of the action they actually performed, rather than the full gradient of the loss function. This necessitates gradient estimation through sampling.
- Projection-Free Constraints: In many high-dimensional problems, such as those involving matroid or submodular base polytopes, the decision set has a complex geometry. Standard algorithms require "projecting" points back into this set, a step that can be computationally prohibitive. Projection-free methods instead rely on a Linear Optimization Oracle (LOO), which is often much more efficient.
- Differential Privacy (DP): Loss functions frequently depend on sensitive user data. The algorithm must ensure that its outputs do not reveal whether any specific individual's data was included in the training set.
Methodology: The PRIVATEBANDIT Algorithm
The authors develop a modular framework called NoisyOCO (Noisy Online Convex Optimization), which treats privacy-preserving noise as a specific form of gradient error. This allows for a decoupled analysis of optimization performance and privacy loss. The algorithm integrates several key techniques:
- Noisy Mirror Descent: A meta-algorithm that maintains stability even when gradient estimates are corrupted by the noise required for differential privacy.
- Randomized Smoothing: To address the lack of direct gradient information (bandit feedback), the algorithm queries the loss function at randomly perturbed points to estimate the gradient.
- Tree-Based Aggregation: To maintain privacy over a long time horizon $T$, the algorithm avoids adding independent noise at every step. Instead, it uses a tree-based structure to aggregate noisy gradient estimates, which minimizes cumulative noise while satisfying DP requirements.
- Conditional Gradient (Frank-Wolfe): To remain projection-free, the algorithm uses the Frank-Wolfe method, solving a linear optimization over the decision set at each iteration instead of a quadratic projection.
Key Results and Insights
The paper proves that PRIVATEBANDIT achieves a regret bound of $\widetilde{O}(T^{3/4})$, matching the best-known non-private projection-free algorithms. The specific bounds depend on the type of privacy guaranteed:
- Pure $(\epsilon, 0)$-DP: Expected regret is $\tilde{O}\left(\frac{T^{3/4} n^{3/2}}{\epsilon}\right)$.
- Approximate $(\epsilon, \delta)$-DP: Expected regret is $\tilde{O}\left(\frac{T^{3/4} n^{1/2} + T^{1/2} n}{\epsilon}\right)$.
A significant technical contribution is the use of matrix concentration inequalities to derive the approximate DP bound. This approach improves the dependence on the dimension $n$ to $n^{1/2}$, matching the performance of algorithms that have the luxury of using expensive projections.
Discussion and Future Work
While this work bridges the gap between private and non-private projection-free optimization, several open questions remain. The $T^{3/4}$ regret bound, while state-of-the-art for projection-free bandit settings, is still higher than the $T^{1/2}$ bound achievable in general bandit optimization. Additionally, there remains a $\sqrt{n}$ gap in dimension dependence between pure and approximate DP settings. Future research may focus on closing these gaps and improving the robustness of the linear systems required by the algorithm to handle noise more effectively.
Summary updated