Research map / Federated learning and privacy / Differential privacy
On Differentially Private Federated Linear Contextual Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Identifies privacy, regret and communication flaws in the federated LinUCB DP method of Dubey & Pentland (2020), and proposes a fixed-batch federated LinUCB with tree-based private aggregation that achieves correct silo-level LDP and near-optimal shuffle-DP regret.
Problem
Cross-silo federated linear contextual bandits need per-user differential privacy at each silo while keeping regret close to a super single agent and communication low; prior work claimed these but has gaps.
Approach
Replace the data-adaptive synchronization schedule with a fixed-batch schedule and privatize per-batch sufficient statistics with a distributed tree-based mechanism; under shuffle DP, use a new amplification-via-shuffling lemma for Gaussian mechanisms on multi-point datasets, or a shuffled vector-sum protocol inside the tree mechanism, to match central-DP regret.
Key results
- Shows the state-of-the-art algorithm of Dubey & Pentland leaks privacy via its data-adaptive synchronization schedule and mis-scales injected noise by M, so its true privacy cost is M^{3/4}sqrt(T/eps) rather than sqrt(MT/eps).
- Silo-level LDP algorithm achieves group regret Otilde(d sqrt(MT) + sqrt(T)(Md)^{3/4}/sqrt(eps)) with sqrt(MT) synchronizations.
- Shuffle-DP variants (amplification lemma and vector-sum protocol) match the central-DP super-agent regret Otilde(d sqrt(MT) + d^{3/4} sqrt(MT)/sqrt(eps)); simulations show SDP-FedLinUCB regret below LDP-FedLinUCB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace adaptive, non-private-data-dependent synchronization with a fixed-batch schedule | Private-FedLinUCB · Federated LCBs under silo-level LDP | privacy protection | Helped |
| Use a fixed-batch schedule instead of the adaptive communication schedule | Private-FedLinUCB · Federated LCBs | communication cost: O(\sqrt{T}) rather than ... O(\log T) | Hurt |
| Account for noise from all M silos instead of using the proposed single-silo noise variance | Prior Algorithm 1 · Federated LCBs under silo-level LDP | privacy-dependent regret cost: \widetilde{O}(\sqrt{MT/\epsilon}) -> \widetilde{O}(M^{3/4}\sqrt{T/\epsilon}) | Hurt |
| Add shuffling to the silo-level LDP privacy protocol | Private-FedLinUCB · Federated LCBs under SDP (amplification) | privacy-dependent regret cost: M^{1/4} factor | Helped |
| Use the vector-sum shuffle protocol instead of the amplification-based protocol | SDP-FedLinUCB · Federated LCBs under SDP | regret | No clear effect |
| Increase ε from 0.2 to 1 or 5 while keeping δ = 0.1 | LDP-FedLinUCB · Microsoft Learning to Rank bandit instance | time-averaged group regret | Helped |
| Use SDP-FedLinUCB instead of LDP-FedLinUCB | FedLinUCB variants · Synthetic Gaussian bandit, M = 100 | time-averaged group regret | Helped |
| Use SDP-FedLinUCB instead of LDP-FedLinUCB | FedLinUCB variants · Synthetic Gaussian bandit, M = 100; ε = 0.2, δ = 0.1 | time-averaged group regret | Helped |
Surprising findings
- The adaptive communication schedule of the prior method leaks private information via the timing of synchronization, so it fails silo-level LDP and even Fed-DP.
- Fixing the schedule to be data-independent yields O(sqrt(T)) communication rather than the claimed O(log T).
Limitations
- Silo-level LDP regret carries an M^{1/4} privacy-cost gap relative to a super agent under central DP.
- Shuffle-DP amplification guarantee holds only for small epsilon and delta; the vector-sum variant needs a different setting.
- Communication cost is O(sqrt(T)) rather than logarithmic; a private data-adaptive schedule remains open.
Experimental setup
Datasets: Microsoft Learning to Rank dataset (MSLR) synthetic Gaussian bandit instances
Benchmarks: synthetic Gaussian linear bandit instances MSLR-WEB10K-derived bandit instances
Metrics: time-averaged group regret
Baselines: FedLinUCB (non-private) Dubey & Pentland 2020 private federated LinUCB
Builds on: LinUCB FedLinUCB (Dubey et al. 2020) tree-based mechanism for continual sum release vector sum mechanism under shuffle model concentrated differential privacy
Closest papers by meaning
- Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits (NeurIPS 2026 · similarity 0.91)
- Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.89)
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups (NeurIPS 2024 · similarity 0.89)
- Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users (AAAI 2024 · similarity 0.88)
- Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret (ICML 2025 · similarity 0.88)
- Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.