Projection-Free Bandit Optimization with Privacy Guarantees

Alina Ene, Huy L. Nguyen, Adrian Vladu

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:

  1. Privacy: We need Differential Privacy (DP) to ensure that the algorithm's output doesn't leak information about any single user.
  2. 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

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, NeurIPS `13).
BibTeX
@inproceedings{ene2021projection,
  author = {Alina Ene and Huy L. Nguyen and Adrian Vladu},
  title = {{Projection-Free Bandit Optimization with Privacy Guarantees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i8.16899},
}
Figure