Near Instance-Optimality in Differential Privacy

• URL: http://arxiv.org/abs/2005.10630v1
• Date: Sat, 16 May 2020 04:53:48 GMT
• Title: Near Instance-Optimality in Differential Privacy
• Authors: Hilal Asi, John C. Duchi
• Abstract summary: We develop notions of instance optimality in differential privacy inspired by classical statistical theory. We also develop inverse sensitivity mechanisms, which are instance optimal (or nearly instance optimal) for a large class of estimands.
• Score: 38.8726789833284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop two notions of instance optimality in differential privacy, inspired by classical statistical theory: one by defining a local minimax risk and the other by considering unbiased mechanisms and analogizing the Cramer-Rao bound, and we show that the local modulus of continuity of the estimand of interest completely determines these quantities. We also develop a complementary collection mechanisms, which we term the inverse sensitivity mechanisms, which are instance optimal (or nearly instance optimal) for a large class of estimands. Moreover, these mechanisms uniformly outperform the smooth sensitivity framework on each instance for several function classes of interest, including real-valued continuous functions. We carefully present two instantiations of the mechanisms for median and robust regression estimation with corresponding experiments.

Related papers

• A phase transition between positional and semantic learning in a solvable model of dot-product attention [30.96921029675713]
  Morelinear model dot-product attention is studied as a non-dimensional self-attention layer with trainable and low-dimensional query and key data. We show that either a positional attention mechanism (with tokens each other based on their respective positions) or a semantic attention mechanism (with tokens tied to each other based their meaning) or a transition from the former to the latter with increasing sample complexity.
  arXiv  Detail & Related papers  (2024-02-06T11:13:54Z)
• On the Optimization and Generalization of Multi-head Attention [28.33164313549433]
  We investigate the potential optimization and generalization advantages of using multiple attention heads. We derive convergence and generalization guarantees for gradient-descent training of a single-layer multi-head self-attention model.
  arXiv  Detail & Related papers  (2023-10-19T12:18:24Z)
• Causality-oriented robustness: exploiting general additive interventions [3.871660145364189]
  In this paper, we focus on causality-oriented robustness and propose Distributional Robustness via Invariant Gradients (DRIG) In a linear setting, we prove that DRIG yields predictions that are robust among a data-dependent class of distribution shifts. We extend our approach to the semi-supervised domain adaptation setting to further improve prediction performance.
  arXiv  Detail & Related papers  (2023-07-18T16:22:50Z)
• Trustworthy Multimodal Regression with Mixture of Normal-inverse Gamma Distributions [91.63716984911278]
  We introduce a novel Mixture of Normal-Inverse Gamma distributions (MoNIG) algorithm, which efficiently estimates uncertainty in principle for adaptive integration of different modalities and produces a trustworthy regression result. Experimental results on both synthetic and different real-world data demonstrate the effectiveness and trustworthiness of our method on various multimodal regression tasks.
  arXiv  Detail & Related papers  (2021-11-11T14:28:12Z)
• The Skellam Mechanism for Differentially Private Federated Learning [28.623090760737075]
  We introduce the multi-dimensional Skellam mechanism, a discrete differential privacy mechanism based on the difference of two independent Poisson random variables. We analyze the privacy loss distribution via a numerical evaluation and provide a sharp bound on the R'enyi divergence between two shifted Skellam distributions. While useful in both centralized and distributed privacy applications, we investigate how it can be applied in the context of federated learning.
  arXiv  Detail & Related papers  (2021-10-11T04:28:11Z)
• An automatic differentiation system for the age of differential privacy [65.35244647521989]
  Tritium is an automatic differentiation-based sensitivity analysis framework for differentially private (DP) machine learning (ML) We introduce Tritium, an automatic differentiation-based sensitivity analysis framework for differentially private (DP) machine learning (ML)
  arXiv  Detail & Related papers  (2021-09-22T08:07:42Z)
• Reinforcement Learning of Sequential Price Mechanisms [24.302600030585275]
  We introduce the use of reinforcement learning for indirect mechanisms, working with the existing class of sequential price mechanisms. We show that our approach can learn optimal or near-optimal mechanisms in several experimental settings.
  arXiv  Detail & Related papers  (2020-10-02T19:57:25Z)
• A general framework for defining and optimizing robustness [74.67016173858497]
  We propose a rigorous and flexible framework for defining different types of robustness properties for classifiers. Our concept is based on postulates that robustness of a classifier should be considered as a property that is independent of accuracy. We develop a very general robustness framework that is applicable to any type of classification model.
  arXiv  Detail & Related papers  (2020-06-19T13:24:20Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

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.