Abstract
This paper introduces DP-DPE, a unified framework for distributed linear bandits designed to maximize global rewards while sampling only a fraction of the population. By integrating Central, Local, and Shuffle Differential Privacy (DP) models, the authors demonstrate that privacy can be achieved "for free"—meaning the performance penalty for protecting user data is negligible compared to the inherent challenges of learning from a distributed population. The framework achieves sublinear regret and communication costs, providing a robust solution for large-scale optimization problems like 5G configuration and dynamic pricing.
Introduction
In many real-world scenarios, such as configuring a 5G base station or selecting public policies, a single central action affects a massive population. To optimize this action, a learning agent (the server) requires feedback. However, two major hurdles exist: the prohibitive cost of collecting feedback from millions of users and the privacy concerns of users unwilling to share raw reward data.
The challenge is to design an algorithm that is communication-efficient, private, and effective at minimizing "regret"—the gap between the chosen actions and the theoretical best action.
The DP-DPE Framework
The authors propose Differentially Private Distributed Phased Elimination (DP-DPE). Unlike standard bandit algorithms that update after every interaction, DP-DPE operates in phases, employing several key innovations:
- Exponential Sampling: In each phase, the algorithm exponentially increases both the number of rounds and the number of sampled clients. This ensures regret stays low while the total number of users contacted remains sublinear relative to the total time.
- Modular Privatizer: The algorithm uses a three-part process—Randomizer (R), Shuffler (S), and Analyzer (A)—to support three trust models: Central DP (server-side noise), Local DP (client-side noise), and Shuffle DP (noise plus anonymous shuffling).
- Tri-Partite Confidence Widths: A sophisticated mathematical confidence width accounts for three distinct types of uncertainty: action-related noise, client-sampling bias, and privacy-preserving noise.
Theoretical and Empirical Results
The paper validates DP-DPE using synthetic datasets (dimension $d=20$, $1,000$ actions, $100,000$ users, and $T=1,000,000$ rounds). The theoretical analysis, summarized in the table below, highlights the trade-offs between regret, communication cost, and privacy level.
Key Insights
- Privacy "For Free": In Central and Shuffle DP models, the additional regret caused by privacy noise is a lower-order term. The error introduced by partial sampling is significantly larger than the error from privacy protection, allowing for privacy without a noticeable performance drop.
- The Power of Shuffling: This work is the first to apply Shuffle DP to distributed linear bandits. It proves that shuffling user reports achieves the high accuracy of a trusted central server while maintaining the strict privacy of a local model.
- Communication Efficiency: In the Shuffle model, users can send binary feedback (bits) rather than high-precision numbers, further reducing the technical burden on user devices.
Conclusion and Future Work
DP-DPE provides a scalable, private solution for distributed optimization. While currently limited by a linearity assumption, the authors suggest extending this framework to kernelized bandits and full Reinforcement Learning (RL) settings where actions have long-term consequences. The bridging of bandits and Differentially Private Stochastic Convex Optimization (DP-SCO) provides a new theoretical foundation for why privacy is increasingly "cheaper" in distributed settings.
Summary updated