Differentially-Private Federated Linear Bandits

Abhimanyu Dubey, Alex Pentland

Introduction

Contextual multi-armed bandits are essential for personalized decision-making in domains like news recommendation and clinical trials. However, these applications often process sensitive user data. In a federated setting, multiple agents aim to learn a shared model collaboratively to improve performance. The primary challenge is ensuring privacy: how can agents share information without leaking raw data? This paper introduces FEDUCB, the first algorithm for contextual linear bandits providing rigorous $(\epsilon, \delta)$-differential privacy (DP) in a federated environment.

The FEDUCB Framework

The authors adapt the Linear Upper Confidence Bound (LinUCB) algorithm for two federated paradigms:

  1. Centralized: A central controller coordinates updates.
  2. Decentralized: Agents communicate peer-to-peer with inherent network delays.

FEDUCB balances three competing objectives: privacy, utility (low regret), and communication efficiency.

Methods: Tree-Based Privatization

A core innovation of FEDUCB is the PRIVATIZER mechanism. Standard DP approaches often add noise to every observation, which can destroy utility, or only at the end, which delays learning. FEDUCB uses a tree-based mechanism to maintain a binary tree of partial sums. This allows agents to share privatized Gram matrices and reward vectors where the noise scales only logarithmically with time ($\log T$).

Algorithm 2: The PRIVATIZER mechanism for tree-based differential privacy.

As shown in Algorithm 2, the mechanism initializes a binary tree of depth $m$ and samples Gaussian noise for each node. During runtime, agents receive updates and compute privatized estimators ($\widehat{\mathbf{U}}_{i,t+1}, \widehat{\mathbf{u}}_{i,t+1}$) using the least nodes of the tree, ensuring robust $(\epsilon, \delta)$-DP without sacrificing significant utility.

Communication Efficiency via Log-Determinant Synchronization

To minimize communication and privacy leakage, FEDUCB employs a "Log-Determinant Synchronization" protocol. Communication is only triggered when an agent's local information significantly deviates from the global model, measured by the change in the log-determinant of the Gram matrix. This effectively balances the cost of communication against the benefit of new data.

In decentralized settings, the authors use round-robin subsampling to handle network delays, ensuring that delayed information does not bias estimators, allowing for a rigorous regret analysis even in complex network topologies.

Key Results and Empirical Validation

The theoretical analysis shows that in the centralized case, FEDUCB achieves a group pseudoregret of $\tilde{O}(d^{3/4}\sqrt{MT}/\epsilon)$. This matches the dependence on time ($T$) and the number of agents ($M$) found in non-private algorithms.

Synthetic benchmarks with up to 100 agents and $10^7$ trials validated these findings:

  • Privacy-Utility Trade-off: As the privacy budget $\epsilon$ increases (less privacy), regret drops significantly.
  • Communication Savings: The log-det threshold successfully keeps regret low while using only $O(M \log T)$ communication rounds, compared to $O(MT)$ in naive implementations.
  • Network Robustness: In decentralized settings, regret scales with the network's diameter and clique cover, demonstrating that cooperation remains beneficial even in sparse networks.

Conclusion

FEDUCB provides a robust framework for private, federated contextual bandits. While it achieves optimal scaling in many respects, future work remains to refine decentralized bounds—potentially scaling with the graph's independence number—and exploring "local" differential privacy where agents do not trust their own local storage.

Summary updated

BibTeX
@inproceedings{dubey2020differentially,
  author = {Abhimanyu Dubey and Alex Pentland},
  title = {{Differentially-Private Federated Linear Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure