Instance-Specific Asymmetric Sensitivity in Differential Privacy

• URL: http://arxiv.org/abs/2311.14681v1
• Date: Thu, 2 Nov 2023 05:01:45 GMT
• Title: Instance-Specific Asymmetric Sensitivity in Differential Privacy
• Authors: David Durfee
• Abstract summary: We build upon previous work that gives a paradigm for selecting an output through the exponential mechanism. Our framework will slightly modify the closeness metric and instead give a simple and efficient application of the sparse vector technique.
• Score: 2.855485723554975
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a new algorithmic framework for differentially private estimation of general functions that adapts to the hardness of the underlying dataset. We build upon previous work that gives a paradigm for selecting an output through the exponential mechanism based upon closeness of the inverse to the underlying dataset, termed the inverse sensitivity mechanism. Our framework will slightly modify the closeness metric and instead give a simple and efficient application of the sparse vector technique. While the inverse sensitivity mechanism was shown to be instance optimal, it was only with respect to a class of unbiased mechanisms such that the most likely outcome matches the underlying data. We break this assumption in order to more naturally navigate the bias-variance tradeoff, which will also critically allow for extending our method to unbounded data. In consideration of this tradeoff, we provide strong intuition and empirical validation that our technique will be particularly effective when the distances to the underlying dataset are asymmetric. This asymmetry is inherent to a range of important problems including fundamental statistics such as variance, as well as commonly used machine learning performance metrics for both classification and regression tasks. We efficiently instantiate our method in $O(n)$ time for these problems and empirically show that our techniques will give substantially improved differentially private estimations.

Related papers

• Distributed Semi-Supervised Sparse Statistical Inference [6.685997976921953]
  A debiased estimator is a crucial tool in statistical inference for high-dimensional model parameters. Traditional methods require computing a debiased estimator on every machine. An efficient multi-round distributed debiased estimator, which integrates both labeled and unlabelled data, is developed.
  arXiv  Detail & Related papers  (2023-06-17T17:30:43Z)
• Generating Private Synthetic Data with Genetic Algorithms [29.756119782419955]
  We study the problem of efficiently generating differentially private synthetic data that approximates the statistical properties of an underlying sensitive dataset. We propose Private-GSD, a private genetic algorithm based on zeroth-order optimizations that do not require modifying the original objective. We show that Private-GSD outperforms the state-of-the-art methods on non-differential queries while matching accuracy in approximating differentiable ones.
  arXiv  Detail & Related papers  (2023-06-05T21:19:37Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• A Data-Driven Method for Automated Data Superposition with Applications in Soft Matter Science [0.0]
  We develop a data-driven, non-parametric method for superposing experimental data with arbitrary coordinate transformations. Our method produces interpretable data-driven models that may inform applications such as materials classification, design, and discovery.
  arXiv  Detail & Related papers  (2022-04-20T14:58:04Z)
• Masked prediction tasks: a parameter identifiability view [49.533046139235466]
  We focus on the widely used self-supervised learning method of predicting masked tokens. We show that there is a rich landscape of possibilities, out of which some prediction tasks yield identifiability, while others do not.
  arXiv  Detail & Related papers  (2022-02-18T17:09:32Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning [78.83598532168256]
  Marginal-likelihood based model-selection is rarely used in deep learning due to estimation difficulties. Our work shows that marginal likelihoods can improve generalization and be useful when validation data is unavailable.
  arXiv  Detail & Related papers  (2021-04-11T09:50:24Z)
• Robust Bayesian Inference for Discrete Outcomes with the Total Variation Distance [5.139874302398955]
  Models of discrete-valued outcomes are easily misspecified if the data exhibit zero-inflation, overdispersion or contamination. Here, we introduce a robust discrepancy-based Bayesian approach using the Total Variation Distance (TVD) We empirically demonstrate that our approach is robust and significantly improves predictive performance on a range of simulated and real world data.
  arXiv  Detail & Related papers  (2020-10-26T09:53:06Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• 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)
• Learning Flat Latent Manifolds with VAEs [16.725880610265378]
  We propose an extension to the framework of variational auto-encoders, where the Euclidean metric is a proxy for the similarity between data points. We replace the compact prior typically used in variational auto-encoders with a recently presented, more expressive hierarchical one. We evaluate our method on a range of data-sets, including a video-tracking benchmark.
  arXiv  Detail & Related papers  (2020-02-12T09:54:52Z)

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.