The Limits of Differential Privacy in Online Learning

• URL: http://arxiv.org/abs/2411.05483v1
• Date: Fri, 08 Nov 2024 11:21:31 GMT
• Title: The Limits of Differential Privacy in Online Learning
• Authors: Bo Li, Wei Wang, Peng Ye,
• Abstract summary: We present evidence that separates three types of constraints: no DP, pure DP, and approximate DP. We first describe a hypothesis class that is online learnable under approximate DP but not online learnable under pure DP under the adaptive adversarial setting. We then prove that any private online learner must make an infinite number of mistakes for almost all hypothesis classes.
• Score: 11.099792269219124
• License:
• Abstract: Differential privacy (DP) is a formal notion that restricts the privacy leakage of an algorithm when running on sensitive data, in which privacy-utility trade-off is one of the central problems in private data analysis. In this work, we investigate the fundamental limits of differential privacy in online learning algorithms and present evidence that separates three types of constraints: no DP, pure DP, and approximate DP. We first describe a hypothesis class that is online learnable under approximate DP but not online learnable under pure DP under the adaptive adversarial setting. This indicates that approximate DP must be adopted when dealing with adaptive adversaries. We then prove that any private online learner must make an infinite number of mistakes for almost all hypothesis classes. This essentially generalizes previous results and shows a strong separation between private and non-private settings since a finite mistake bound is always attainable (as long as the class is online learnable) when there is no privacy requirement.

Related papers

• Masked Differential Privacy [64.32494202656801]
  We propose an effective approach called masked differential privacy (DP), which allows for controlling sensitive regions where differential privacy is applied. Our method operates selectively on data and allows for defining non-sensitive-temporal regions without DP application or combining differential privacy with other privacy techniques within data samples.
  arXiv  Detail & Related papers  (2024-10-22T15:22:53Z)
• LLM-based Privacy Data Augmentation Guided by Knowledge Distillation with a Distribution Tutor for Medical Text Classification [67.92145284679623]
  We propose a DP-based tutor that models the noised private distribution and controls samples' generation with a low privacy cost. We theoretically analyze our model's privacy protection and empirically verify our model.
  arXiv  Detail & Related papers  (2024-02-26T11:52:55Z)
• Personalized Differential Privacy for Ridge Regression [3.4751583941317166]
  We introduce our novel Personalized-DP Output Perturbation method ( PDP-OP) that enables to train Ridge regression models with individual per data point privacy levels. We provide rigorous privacy proofs for our PDP-OP as well as accuracy guarantees for the resulting model. We show that PDP-OP outperforms the personalized privacy techniques of Jorgensen et al.
  arXiv  Detail & Related papers  (2024-01-30T16:00:14Z)
• Considerations on the Theory of Training Models with Differential Privacy [13.782477759025344]
  In federated learning collaborative learning takes place by a set of clients who each want to remain in control of how their local training data is used. Differential privacy is one method to limit privacy leakage.
  arXiv  Detail & Related papers  (2023-03-08T15:56:27Z)
• On Differentially Private Online Predictions [74.01773626153098]
  We introduce an interactive variant of joint differential privacy towards handling online processes. We demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing. We then study the cost of interactive joint privacy in the basic setting of online classification.
  arXiv  Detail & Related papers  (2023-02-27T19:18:01Z)
• How Do Input Attributes Impact the Privacy Loss in Differential Privacy? [55.492422758737575]
  We study the connection between the per-subject norm in DP neural networks and individual privacy loss. We introduce a novel metric termed the Privacy Loss-Input Susceptibility (PLIS) which allows one to apportion the subject's privacy loss to their input attributes.
  arXiv  Detail & Related papers  (2022-11-18T11:39:03Z)
• Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano [83.5933307263932]
  We study data reconstruction attacks for discrete data and analyze it under the framework of hypothesis testing. We show that if the underlying private data takes values from a set of size $M$, then the target privacy parameter $epsilon$ can be $O(log M)$ before the adversary gains significant inferential power.
  arXiv  Detail & Related papers  (2022-10-24T23:50:12Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning [43.6041475698327]
  Differentially private (DP) machine learning allows us to train models on private data while limiting data leakage. In this paper, we evaluate the importance of the adversary capabilities allowed in the privacy analysis of DP training algorithms.
  arXiv  Detail & Related papers  (2021-01-11T18:47:11Z)

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.