Research map / Federated learning and privacy / Differential privacy
Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups
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.
Studies differentially private federated online prediction from experts against stochastic and oblivious adversaries, proposing Fed-DP-OPE-Stoch (sqrt(m) speed-up), lower bounds for general oblivious adversaries, and Fed-SVT (m-fold speed-up under low-loss expert realizability).
Problem
Differentially private online prediction from experts in a federated setting with m clients, minimizing per-client regret against stochastic or oblivious adversaries while keeping communication low.
Approach
A federated DP-FW-based algorithm where clients privatize local gradient estimates via tree mechanism and Laplace noise, and the server picks a global expert from noisy inner products (stochastic case); and a sparse-vector-based protocol where clients send per-phase accumulated losses so the server decides when to switch experts (realizable oblivious case). A policy-reduction argument yields lower
Key results
- Fed-DP-OPE-Stoch achieves a sqrt(m)-fold per-client regret speed-up over single-player Limited Updates under pure and approximate DP with O(md log T) communication in the beta-small regime.
- Fed-SVT achieves an m-fold regret speed-up over single-player Sparse-Vector under pure and approximate DP in the near-realizable oblivious setting.
- Lower bound Omega(min(log d/eps, T)) shows collaboration gives no regret speed-up for general oblivious adversaries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use federated collaboration with Fed-DP-OPE-Stoch instead of the single-player Limited Updates algorithm | Online prediction from experts with stochastic adversaries · Stochastic adversaries | per-client regret: $O\left( \sqrt{T\log d}+\frac{\log d \log T}{\varepsilon}\right)$ -> $O\left( \sqrt{\frac{T\log d}{m}}+\frac{\log d \log | Helped |
| Use Fed-SVT with federated collaboration instead of single-player Sparse-Vector | Online prediction from experts with realizable oblivious adversaries · Oblivious adversaries (realizable), $\varepsilon$-DP | regret: $O\left(\frac{\log T\log d+\log^2 d}{\varepsilon} \right)$ -> $O\left( \frac{\log T\log d+\log^2 d}{m\varepsilon} + N\lo | Helped |
| Collaborate across clients against general oblivious adversaries | Federated online prediction from experts · Oblivious adversaries | per-client regret | No clear effect |
Surprising findings
- For general oblivious adversaries, per-client regret lower bounds are independent of the number of clients m, so collaboration does not help.
Limitations
- Experiments are only synthetic, with no real-world federated learning evaluation (MovieLens-1M only in appendix).
- General oblivious setting shows no speed-up; Fed-SVT requires a near-realizable low-loss expert assumption.
Experimental setup
Datasets: MovieLens-1M
Metrics: per-client regret
Baselines: Limited Updates Sparse-Vector
Builds on: DP-FW Limited Updates Sparse-Vector technique
Closest papers by meaning
- Tracking The Best Expert Privately (ICML 2025 · similarity 0.90)
- Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy (NeurIPS 2025 · similarity 0.89)
- Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems (ICML 2024 · similarity 0.89)
- On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.89)
- Private Online Learning via Lazy Algorithms (NeurIPS 2024 · similarity 0.88)
- Revisiting Differentially Private Algorithms for Decentralized Online Learning (ICML 2025 · similarity 0.88)
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.