Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data

Abstract

In this work, we study the generalization capability of algorithms from an information-theoretic perspective. It has been shown that the expected generalization error of an algorithm is bounded from above by a function of the relative entropy between the conditional probability distribution of the algorithm's output hypothesis, given the dataset with which it was trained, and its marginal probability distribution. We build upon this fact and introduce a mathematical formulation to obtain upper bounds on this relative entropy. Assuming that the data is discrete, we then develop a strategy using this formulation, based on the method of types and typicality, to find explicit upper bounds on the generalization error of stable algorithms, i.e., algorithms that produce similar output hypotheses given similar input datasets. In particular, we show the bounds obtained with this strategy for the case of $\epsilon$-DP and $\mu$-GDP algorithms.

arXiv comment18 pages (double column), 4 figures, accepted at IEEE Transactions on Information Theory

References in corpus (10)

• Adam: A Method for Stochastic Optimization
• Brain Tumor Segmentation with Deep Neural Networks
• Renyi Differential Privacy
• Information-theoretic analysis of generalization capability of learning algorithms
• Generalization in Adaptive Data Analysis and Holdout Reuse
• Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle
• Generalization Bounds via Information Density and Conditional Information Density
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm
• Differentially Private Markov Chain Monte Carlo