TL;DR
This paper introduces the first differentially private algorithm for Bandit Convex Optimization (BCO) in the projection-free setting. By combining noisy mirror descent with tree-based noise aggregation, the authors achieve regret bounds that match the state-of-the-art for both non-private projection-free methods and private projection-based methods.
What Problem Does This Paper Address?
In many real-world online learning scenarios (like ad-serving or dynamic pricing), algorithms must make decisions based on sensitive user data. Two major challenges arise:
- Privacy: We need Differential Privacy (DP) to ensure that the algorithm's output doesn't leak information about any single user.
- Computational Complexity: Standard optimization algorithms often require "projecting" a point onto a set of feasible decisions. For complex decision spaces (like those involving matroids or submodular functions), these projections are computationally "prohibitive." Projection-free methods solve this by using a Linear Optimization Oracle (LOO), which is much faster.
While previous work addressed privacy in bandit settings and projection-free methods in non-private settings, this paper is the first to bridge the gap, providing a private, projection-free algorithm for the "bandit" setting (where the algorithm only sees the loss for the specific action it took, not the entire loss function).
Methods
The authors develop a framework called NOISYOCO (Noisy Online Convex Optimization), which treats privacy-preserving noise and bandit-feedback noise as a unified challenge. Their algorithm, PRIVATEBANDIT, employs several key techniques:
- Randomized Smoothing: Since the algorithm only sees a single "bandit" feedback value, it uses a standard trick of querying a slightly perturbed point to estimate the gradient of a "smoothed" version of the loss function.
- Tree-Based Aggregation: To maintain privacy over many iterations, the algorithm doesn't release every gradient. Instead, it uses a tree-based structure to release partial sums of gradients. This keeps the total noise added (the "privacy cost") low.
- Batching: The algorithm processes iterations in batches. In each batch, it uses a fixed decision point but perturbs it differently to gather information, which helps balance the regret and the privacy budget.
- Conditional Gradient (Frank-Wolfe): Instead of Euclidean projections, the algorithm uses a linear optimization oracle to update its decisions, making it suitable for complex geometric constraints.
Datasets
Not discussed in the paper. This is a theoretical work focused on proving mathematical guarantees (regret bounds) rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The $(\epsilon, \delta)$ Advantage: The authors found a significant difference between "pure" DP $(\epsilon, 0)$ and "approximate" DP $(\epsilon, \delta)$. By allowing a tiny probability ($\delta$) of privacy failure, they could use a matrix concentration inequality (Matrix Bernstein) to significantly reduce the noise's dependence on the dimension $n$.
- Modularity: The NOISYOCO framework is highly modular. It allows researchers to "plug in" different privacy mechanisms (like Laplace or Gaussian noise) and immediately see the resulting regret bound.
- Matching the State-of-the-Art: Surprisingly, even though projection-free methods are generally considered "weaker" or more restricted than projection-based methods, the authors' private version achieves the same regret rate as the best known private algorithms that do use projections.
Key Results
The paper's main contribution is summarized in Theorem 1, which provides the expected regret ($R_T$)—the difference between the algorithm's total loss and the best possible fixed decision:
- For $(\epsilon, \delta)$-Differential Privacy: The regret is $\tilde{O}\left(\frac{T^{3/4}n^{1/2}}{\epsilon}\right)$. This matches the best known non-private projection-free bounds up to a $1/\epsilon$ factor and matches private projection-based bounds.
- For $(\epsilon, 0)$-Differential Privacy: The regret is $\tilde{O}\left(\frac{T^{3/4}n^{3/2}}{\epsilon}\right)$.
- Dimension Dependence: In the $(\epsilon, \delta)$ regime, the algorithm scales with the square root of the dimension ($\sqrt{n}$), which is a major improvement over the $n^{3/2}$ scaling required for pure privacy.
Limitations and Future Work
- The Pure Privacy Gap: There is still a $\sqrt{n}$ gap between the authors' $(\epsilon, 0)$ result and what is possible with projections. Closing this gap remains an open problem.
- Regret Rate: The $T^{3/4}$ regret rate is standard for bandit settings but slower than the $T^{1/2}$ rate achievable when the full loss function is known. Improving the fundamental regret rate for BCO is a broader challenge in the field.
- Complex Geometry: While the algorithm works for any convex set with a linear oracle, the authors note that achieving even better regret might require "stronger control" over the geometry of the domain, which is difficult to maintain under the "noise" required for privacy.
Summary updated