Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups
Preprint
Abstract
We study the problems of differentially private federated online prediction from experts against both stochastic adversaries and oblivious adversaries. We aim to minimize the average regret on $m$ clients working in parallel over time horizon $T$ with explicit differential privacy (DP) guarantees. With stochastic adversaries, we propose a Fed-DP-OPE-Stoch algorithm that achieves $\sqrt{m}$-fold speed-up of the per-client regret compared to the single-player counterparts under both pure DP and approximate DP constraints, while maintaining logarithmic communication costs. With oblivious adversaries, we establish non-trivial lower bounds indicating that collaboration among clients does not lead to regret speed-up with general oblivious adversaries. We then consider a special case of the oblivious adversaries setting, where there exists a low-loss expert. We design a new algorithm Fed-SVT and show that it achieves an $m$-fold regret speed-up under both pure DP and approximate DP constraints over the single-player counterparts. Our lower bound indicates that Fed-SVT is nearly optimal up to logarithmic factors. Experiments demonstrate the effectiveness of our proposed algorithms. To the best of our knowledge, this is the first work examining the differentially private online prediction from experts in the federated setting.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Differentially Private Stochastic Linear Bandits: (Almost) for FreeIEEE Journal on Selected Areas in Information Theory, 2024
- Tighter Regret Analysis and Optimization of Online Federated LearningIEEE Transactions on Pattern Analysis and Machine Intelligence, 2023
- Asynchronous Online Federated Learning With Reduced Communication RequirementsIEEE Internet of Things Journal, 2023
- (Private) Kernelized Bandits with Distributed Biased FeedbackProceedings of the ACM on Measurement and Analysis of Computing Systems, 2023
- Communication-Efficient Randomized Algorithm for Multi-Kernel Online Federated LearningIEEE Transactions on Pattern Analysis and Machine Intelligence, 2021
- Federated Bandit: A Gossiping Approach2021
- Differentially Private Distributed Online LearningIEEE Transactions on Knowledge and Data Engineering, 2018
- Stochastic Convex Optimization with Bandit FeedbackSIAM Journal on Optimization, 2013
- Efficient algorithms for online decision problemsJournal of Computer and System Sciences, 2005
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997