Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms

• URL: http://arxiv.org/abs/2007.09371v2
• Date: Fri, 7 Aug 2020 04:41:55 GMT
• Title: Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms
• Authors: Fengxiang He, Bohan Wang, Dacheng Tao
• Abstract summary: This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
• Score: 95.73230376153872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We first establish an alignment between generalization and privacy preservation for any learning algorithm. We prove that $(\varepsilon, \delta)$-differential privacy implies an on-average generalization bound for multi-database learning algorithms which further leads to a high-probability bound for any learning algorithm. This high-probability bound also implies a PAC-learnable guarantee for differentially private learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization. Three composition theorems are proposed to approximate the differential privacy of any iterative algorithm through the differential privacy of its every iteration. By integrating the above two steps, we eventually deliver generalization bounds for iterative learning algorithms, which suggest one can simultaneously enhance privacy preservation and generalization. Our results are strictly tighter than the existing works. Particularly, our generalization bounds do not rely on the model size which is prohibitively large in deep learning. This sheds light to understanding the generalizability of deep learning. These results apply to a wide spectrum of learning algorithms. In this paper, we apply them to stochastic gradient Langevin dynamics and agnostic federated learning as examples.

Related papers

• An Information-Theoretic Approach to Generalization Theory [27.87324770020133]
  We analyze information-theoretic bounds that quantify the dependence between a learning algorithm and the training data. We show that algorithms with a bounded maximal leakage guarantee generalization even with a constant privacy parameter.
  arXiv  Detail & Related papers  (2024-08-20T10:08:21Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation. We obtain several improved algorithms for private optimization problems, including decomposable submodular and set algorithm cover.
  arXiv  Detail & Related papers  (2024-05-28T19:02:30Z)
• Theoretically Principled Federated Learning for Balancing Privacy and Utility [61.03993520243198]
  We propose a general learning framework for the protection mechanisms that protects privacy via distorting model parameters. It can achieve personalized utility-privacy trade-off for each model parameter, on each client, at each communication round in federated learning.
  arXiv  Detail & Related papers  (2023-05-24T13:44:02Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Stochastic Differentially Private and Fair Learning [7.971065005161566]
  We provide the first differentially private algorithm for fair learning that is guaranteed to converge. Our framework is flexible enough to permit different fairness, including demographic parity and equalized odds. Our algorithm can be applied to non-binary classification tasks with multiple (non-binary) sensitive attributes.
  arXiv  Detail & Related papers  (2022-10-17T06:54:57Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection. This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
  arXiv  Detail & Related papers  (2022-09-09T08:54:13Z)
• A Pragmatic Look at Deep Imitation Learning [0.3626013617212666]
  We re-implement 6 different adversarial imitation learning algorithms. We evaluate them on a widely-used expert trajectory dataset. GAIL consistently performs well across a range of sample sizes.
  arXiv  Detail & Related papers  (2021-08-04T06:33:10Z)
• Privacy Analysis of Online Learning Algorithms via Contraction Coefficients [5.333582981327498]
  We show that differential privacy guarantees can be determined by a direct application of contraction coefficients derived from strong data processing inequalities for $f$-divergences. We also show that this framework can be tailored to batch learning algorithms that can be implemented with one pass over the training dataset.
  arXiv  Detail & Related papers  (2020-12-20T22:02:15Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Efficient, Noise-Tolerant, and Private Learning via Boosting [15.62988331732388]
  We show how to construct noise-tolerant and private PAC learners for large-margin halfspaces. This first bound illustrates a general methodology for obtaining PAC learners from privacy. The second bound uses standard techniques to match the best known sample complexity for differentially private learning of large-margin halfspaces.
  arXiv  Detail & Related papers  (2020-02-04T03:16:37Z)

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.