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

• URL: http://arxiv.org/abs/2005.05889v3
• Date: Mon, 13 Sep 2021 17:23:08 GMT
• Title: Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• Authors: Borja Rodr\'iguez-G\'alvez, Germ\'an Bassi, and Mikael Skoglund
• Abstract summary: We study the generalization capability of algorithms from an information-theoretic perspective. In particular, we show the bounds obtained with this strategy for the case of $epsilon$-DP and $mu$-GDP algorithms.
• Score: 31.122671977370416
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Generalization of Hamiltonian algorithms [6.835035668445878]
  The paper proves generalization results for a class of learning algorithms. The method applies whenever the algorithm generates an absolutely continuous distribution relative to some a-priori measure. Applications are bounds for the Gibbs algorithm and randomizations of stable deterministic algorithms as well as PAC-Bayesian bounds with data-dependent priors.
  arXiv  Detail & Related papers  (2024-05-23T11:56:05Z)
• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  We propose a framework for the analysis of the low-rank approximation error in Frobenius norm for centered and non-standard matrices. Under minimal assumptions, we derive accurate bounds in expectation and probability. Our bounds have clear interpretations that enable us to derive properties and motivate practical choices.
  arXiv  Detail & Related papers  (2024-05-08T04:51:56Z)
• Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems [1.5586874069708228]
  This paper develops a new dimension-free Azuma-Hoeffding type bound on norm of a martingale difference sequence with random individual bounds. We provide high-probability bounds for the gradient norm estimator in the proposed algorithm Prob-SARAH.
  arXiv  Detail & Related papers  (2024-01-29T05:05:03Z)
• Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure [1.773764539873123]
  Worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of empirical risk, and the generalization gap are shown to have closed-form expressions. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm.
  arXiv  Detail & Related papers  (2023-12-19T15:20:27Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  Gaussian processes scale prohibitively with the size of the dataset. Many approximation methods have been developed, which inevitably introduce approximation error. This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior. We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
  arXiv  Detail & Related papers  (2022-05-30T22:16:25Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Bootstrapping the error of Oja's Algorithm [16.017328736786922]
  We consider the problem of quantifying uncertainty for the estimation error of the leading eigenvector from Oja's algorithm for streaming principal component analysis. We propose a multiplier bootstrap algorithm that may be updated in an online manner.
  arXiv  Detail & Related papers  (2021-06-28T17:27:26Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

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.