Differentially Private Federated Bayesian Optimization with Distributed Exploration

Zhongxiang Dai, Bryan Kian Hsiang Low, Patrick Jaillet

Overview

Bayesian Optimization (BO) is the gold standard for tuning "expensive" black-box systems, such as finding the best hyperparameters for a deep neural network or selecting the right medical tests for patients. Recently, BO has been extended to the Federated Learning (FL) setting, allowing multiple agents (like different hospitals or mobile phone users) to collaborate without sharing their raw, sensitive data.

However, existing Federated BO algorithms lack Differential Privacy (DP)—a rigorous mathematical framework ensuring an adversary cannot tell whether a specific individual participated in a dataset. Simply "bolting on" DP to existing BO algorithms usually fails because the noise required to protect privacy often "drowns out" the useful information, leading to poor performance.

This paper introduces DP-FTS-DE (Differentially Private Federated Thompson Sampling with Distributed Exploration), the first framework for Federated BO that provides rigorous, user-level differential privacy guarantees. By combining a novel "Distributed Exploration" strategy with a central-server architecture, the authors demonstrate that it is possible to protect sensitive user data without sacrificing the optimization performance typically lost when adding privacy-preserving noise.

Methodology: Introducing DP-FTS-DE

The challenge is clear: how do we provide a rigorous privacy guarantee while keeping the optimization efficient? The authors solve this through a four-part architecture involving a central server and multiple agents.

Architecture of DP-FTS-DE, illustrating the central server communication, the subsampled Gaussian mechanism, and the partitioned search space for Distributed Exploration.
  1. DP-FTS (Differentially Private Federated Thompson Sampling): The authors modify the standard Federated Thompson Sampling algorithm to fit a general DP framework. The central server subsamples a fraction of agents, clips their shared parameter vectors (to limit the influence of any single user), and adds Gaussian noise before broadcasting an aggregated update back to all agents.
  2. Distributed Exploration (DE): This is the paper's core innovation to recover lost utility. The search space is partitioned into smaller sub-regions. At the start, agents are assigned to explore specific sub-regions rather than the entire domain.
  3. Local Modeling: Because agents focus on smaller areas, their local Gaussian Process (GP) models become much more accurate. This "stronger signal" helps the algorithm overcome the "noise" added for privacy.
  4. Adaptive Weighting: The server uses a softmax-based weighting scheme. Early in the process, it gives more weight to agents assigned to a specific sub-region. As time goes on, it gradually shifts toward uniform weights as agents naturally explore beyond their initial assignments.

Key Insights

  • Divide and Conquer for Privacy: The "aha moment" of this research is that local modeling (DE) isn't just an optimization trick—it's a privacy enabler. By making local models more precise, the information shared with the server is of "higher quality," allowing the system to tolerate the noise required for DP.
  • Quantifiable Privacy-Utility Trade-off: The authors provide a theoretical "regret bound" (a measure of how much performance is lost compared to an optimal strategy). This bound explicitly shows how privacy parameters (like noise level and subsampling rate) impact the optimization speed.
  • Robustness to Heterogeneity: In federated settings, different agents often have slightly different goals. The authors prove that their algorithm is "no-regret," meaning it will eventually find the optimum for the primary agent even if other collaborating agents have heterogeneous data.

Key Results: Privacy Without Sacrificing Utility

The researchers evaluated their algorithm on synthetic functions, as well as real-world benchmarks including Landmine Detection, Human Activity Recognition, and EMNIST (tuning a CNN on handwritten characters).

Experimental results demonstrating the simple regret over iterations. The plots show how DP-FTS-DE maintains competitive performance and how different privacy parameters influence the optimization trade-off.
  • Competitive Performance: DP-FTS-DE achieves "single-digit" privacy loss ($\epsilon < 10$), which is considered a strong privacy guarantee in the ML community, while still outperforming standard non-federated BO.
  • DE is Essential: Experiments showed that without the Distributed Exploration component, adding DP noise caused a significant drop in performance. With DE, the algorithm remained highly effective.
  • Real-World Success: On the EMNIST and Landmine tasks, DP-FTS-DE consistently converged faster and reached better solutions than standard Thompson Sampling, even with the added privacy constraints.

Limitations and Future Work

While DP-FTS-DE marks a significant step forward, the authors note a few areas for future refinement. First, the current model assumes every agent can communicate with the server in every iteration, which doesn't explicitly handle devices going offline in real-world edge computing. Second, while the "Moments Accountant" method was used for privacy tracking, newer techniques like Gaussian Differential Privacy could potentially provide even tighter bounds. Finally, the authors acknowledge that while DP protects privacy, it doesn't guarantee fairness; ensuring that outlier users aren't "discriminated against" by the global model remains a critical area for future research.

Summary updated

Abstract

Bayesian optimization (BO) has recently been extended to the federated learning (FL) setting by the federated Thompson sampling (FTS) algorithm, which has promising applications such as federated hyperparameter tuning. However, FTS is not equipped with a rigorous privacy guarantee which is an important consideration in FL. Recent works have incorporated differential privacy (DP) into the training of deep neural networks through a general framework for adding DP to iterative algorithms. Following this general DP framework, our work here integrates DP into FTS to preserve user-level privacy. We also leverage the ability of this general DP framework to handle different parameter vectors, as well as the technique of local modeling for BO, to further improve the utility of our algorithm through distributed exploration (DE). The resulting differentially private FTS with DE (DP-FTS-DE) algorithm is endowed with theoretical guarantees for both the privacy and utility and is amenable to interesting theoretical insights about the privacy-utility trade-off. We also use real-world experiments to show that DP-FTS-DE achieves high utility (competitive performance) with a strong privacy guarantee (small privacy loss) and induces a trade-off between privacy and utility.
BibTeX
@inproceedings{dai2021differentially,
  author = {Zhongxiang Dai and Bryan Kian Hsiang Low and Patrick Jaillet},
  title = {{Differentially Private Federated Bayesian Optimization with Distributed Exploration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=aj8x18_Te9},
}
Figure