Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups

• URL: http://arxiv.org/abs/2409.19092v1
• Date: Fri, 27 Sep 2024 18:43:24 GMT
• Title: Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups
• Authors: Fengyu Gao, Ruiquan Huang, Jing Yang,
• Abstract summary: We study the problems of differentially private online prediction from experts against both adversaries and oblivious adversaries. With adversaries, we propose a Fed-DP-OPE-Stoch algorithm that achieves $sqrtm$-fold speed-up of the per-client regret. With oblivious adversaries, we establish non-trivial lower bounds indicating that collaboration among clients does not lead to regret speed-up.
• Score: 6.925352969721467
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Convergent Differential Privacy Analysis for General Federated Learning: the $f$-DP Perspective [57.35402286842029]
  Federated learning (FL) is an efficient collaborative training paradigm with a focus on local privacy. differential privacy (DP) is a classical approach to capture and ensure the reliability of private protections.
  arXiv  Detail & Related papers  (2024-08-28T08:22:21Z)
• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  We study a multi-agent imitation learning (MAIL) problem where we take the perspective of a learner attempting to coordinate a group of agents. Most prior work in MAIL essentially reduces the problem to matching the behavior of the expert within the support of the demonstrations. While doing so is sufficient to drive the value gap between the learner and the expert to zero under the assumption that agents are non-strategic, it does not guarantee to deviations by strategic agents.
  arXiv  Detail & Related papers  (2024-06-06T16:18:20Z)
• FastLloyd: Federated, Accurate, Secure, and Tunable $k$-Means Clustering with Differential Privacy [26.927356987142407]
  We study the problem of privacy-preserving $k$-means clustering in the horizontally federated setting. Existing approaches using secure computation suffer from substantial overheads and do not offer output privacy. By utilizing the computational DP model, we design a lightweight, secure aggregation-based approach that achieves four orders of magnitude speed-up.
  arXiv  Detail & Related papers  (2024-05-03T19:04:37Z)
• Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation [79.64626707978418]
  We propose using link local differential privacy over decentralized nodes to train graph neural networks. Our approach spends the privacy budget separately on links and degrees of the graph for the server to better denoise the graph topology. Our approach outperforms existing methods in terms of accuracy under varying privacy budgets.
  arXiv  Detail & Related papers  (2023-09-06T17:53:31Z)
• DP-BREM: Differentially-Private and Byzantine-Robust Federated Learning with Client Momentum [11.68347496182345]
  Federated Learning (FL) allows multiple participating clients to train machine learning models collaboratively. Existing FL protocols are vulnerable to attacks that aim to compromise data privacy and/or model robustness. We focus on simultaneously achieving differential privacy (DP) and Byzantine robustness for cross-silo FL.
  arXiv  Detail & Related papers  (2023-06-22T00:11:53Z)
• Federated Linear Contextual Bandits with User-level Differential Privacy [8.396384861175799]
  This paper studies federated linear contextual bandits under the notion of user-level differential privacy (DP) We first introduce a unified federated bandits framework that can accommodate various definitions of DP in the sequential decision-making setting. We then formally introduce user-level central DP (CDP) and local DP (LDP) in the federated bandits framework, and investigate the fundamental trade-offs between the learning regrets and the corresponding DP guarantees.
  arXiv  Detail & Related papers  (2023-06-08T15:21:47Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algorithms for this problem that improve over the regret bounds of the best existing algorithms for non-adaptive adversaries.
  arXiv  Detail & Related papers  (2022-10-24T18:40:19Z)
• Generalised Likelihood Ratio Testing Adversaries through the Differential Privacy Lens [69.10072367807095]
  Differential Privacy (DP) provides tight upper bounds on the capabilities of optimal adversaries. We relax the assumption of a Neyman--Pearson (NPO) adversary to a Generalized Likelihood Test (GLRT) adversary. This mild relaxation leads to improved privacy guarantees.
  arXiv  Detail & Related papers  (2022-10-24T08:24:10Z)
• Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions [49.726408540784334]
  Key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We show that our pessimistic estimate is the best possible among all pessimistic estimates.
  arXiv  Detail & Related papers  (2022-07-10T04:25:02Z)
• Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training [12.386462516398469]
  Finding efficient, easily implementable differentially private (DP) algorithms that offer strong excess risk bounds is an important problem in modern machine learning. We provide the tightest known $(epsilon, 0)$-DP population loss bounds and fastest runtimes under the presence of smoothness and strong convexity. We apply our theory to two learning frameworks: tilted ERM and adversarial learning frameworks.
  arXiv  Detail & Related papers  (2021-02-09T08:47:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.