Fast Private Kernel Density Estimation via Locality Sensitive Quantization

• URL: http://arxiv.org/abs/2307.01877v1
• Date: Tue, 4 Jul 2023 18:48:04 GMT
• Title: Fast Private Kernel Density Estimation via Locality Sensitive Quantization
• Authors: Tal Wagner, Yonatan Naamad, Nina Mishra
• Abstract summary: We study efficient mechanisms for differentially private kernel density estimation (DP-KDE) We show how the kernel can privately be approximated in time linear in $d$, making it feasible for high-dimensional data.
• Score: 10.227538355037554
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study efficient mechanisms for differentially private kernel density estimation (DP-KDE). Prior work for the Gaussian kernel described algorithms that run in time exponential in the number of dimensions $d$. This paper breaks the exponential barrier, and shows how the KDE can privately be approximated in time linear in $d$, making it feasible for high-dimensional data. We also present improved bounds for low-dimensional data. Our results are obtained through a general framework, which we term Locality Sensitive Quantization (LSQ), for constructing private KDE mechanisms where existing KDE approximation techniques can be applied. It lets us leverage several efficient non-private KDE methods -- like Random Fourier Features, the Fast Gauss Transform, and Locality Sensitive Hashing -- and ``privatize'' them in a black-box manner. Our experiments demonstrate that our resulting DP-KDE mechanisms are fast and accurate on large datasets in both high and low dimensions.

Related papers

• KDEformer: Accelerating Transformers via Kernel Density Estimation [30.860357184928407]
  In this paper, we introduce a new approach to exact computation of Dot-product attention mechanism. We show that our proposed approach outperforms other attention approximations in terms of accuracy, memory, and runtime. For image classification with T2T-ViT, we show over $18times$ speedup while the accuracy drop is less than $0.5%$.
  arXiv  Detail & Related papers  (2023-02-05T18:23:49Z)
• Solving High-Dimensional PDEs with Latent Spectral Models [74.1011309005488]
  We present Latent Spectral Models (LSM) toward an efficient and precise solver for high-dimensional PDEs. Inspired by classical spectral methods in numerical analysis, we design a neural spectral block to solve PDEs in the latent space. LSM achieves consistent state-of-the-art and yields a relative gain of 11.5% averaged on seven benchmarks.
  arXiv  Detail & Related papers  (2023-01-30T04:58:40Z)
• Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory [16.460386321121945]
  Kernel density estimation (KDE) stands out as a challenging task in machine learning. Recently, there has been a growing trend of using data structures for efficient KDE. In this work, we focus on the dynamic maintenance of KDE data structures with robustness to adversarial queries.
  arXiv  Detail & Related papers  (2022-08-08T04:40:20Z)
• Fast Kernel Density Estimation with Density Matrices and Random Fourier Features [0.0]
  kernels density estimation (KDE) is one of the most widely used nonparametric density estimation methods. DMKDE uses density matrices, a quantum mechanical formalism, and random Fourier features, an explicit kernel approximation, to produce density estimates. DMKDE is on par with its competitors for computing density estimates and advantages are shown when performed on high-dimensional data.
  arXiv  Detail & Related papers  (2022-08-02T02:11:10Z)
• CROM: Continuous Reduced-Order Modeling of PDEs Using Implicit Neural Representations [5.551136447769071]
  Excessive runtime of high-fidelity partial differential equation solvers makes them unsuitable for time-critical applications. We propose to accelerate PDE solvers using reduced-order modeling (ROM) Our approach builds a smooth, low-dimensional manifold of the continuous vector fields themselves, not their discretization.
  arXiv  Detail & Related papers  (2022-06-06T13:27:21Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• Generative Adversarial Learning via Kernel Density Discrimination [32.91091065436645]
  We introduce Kernel Density Discrimination GAN (KDD GAN), a novel method for generative adversarial learning. We define the Kernel Density Estimates directly in feature space and forgo the requirement of invertibility of the kernel feature mappings. We show a boost in the quality of generated samples with respect to FID from 10% to 40% compared to the baseline.
  arXiv  Detail & Related papers  (2021-07-13T15:52:10Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network. We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
  arXiv  Detail & Related papers  (2021-04-03T09:08:12Z)
• Nonparametric Density Estimation from Markov Chains [68.8204255655161]
  We introduce a new nonparametric density estimator inspired by Markov Chains, and generalizing the well-known Kernel Density Estor. Our estimator presents several benefits with respect to the usual ones and can be used straightforwardly as a foundation in all density-based algorithms.
  arXiv  Detail & Related papers  (2020-09-08T18:33:42Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. We propose a private sketch that supports a multitude of machine learning tasks including regression, classification, density estimation, and more. Our sketch consists of randomized contingency tables that are indexed with locality-sensitive hashing and constructed with an efficient one-pass algorithm.
  arXiv  Detail & Related papers  (2020-06-16T17:47:48Z)

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.