Contraction of Locally Differentially Private Mechanisms

• URL: http://arxiv.org/abs/2210.13386v4
• Date: Fri, 3 May 2024 05:05:04 GMT
• Title: Contraction of Locally Differentially Private Mechanisms
• Authors: Shahab Asoodeh, Huanyu Zhang,
• Abstract summary: We derive tight bounds on the divergence between $PK$ and $QK$ output distributions of an $epsilon$-LDP mechanism $K$. We then utilize these bounds to establish locally private versions of the van Trees inequality, Le Cam's, Assouad's, and the mutual information methods.
• Score: 8.547801169402923
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We investigate the contraction properties of locally differentially private mechanisms. More specifically, we derive tight upper bounds on the divergence between $PK$ and $QK$ output distributions of an $\epsilon$-LDP mechanism $K$ in terms of a divergence between the corresponding input distributions $P$ and $Q$, respectively. Our first main technical result presents a sharp upper bound on the $\chi^2$-divergence $\chi^2(PK}\|QK)$ in terms of $\chi^2(P\|Q)$ and $\varepsilon$. We also show that the same result holds for a large family of divergences, including KL-divergence and squared Hellinger distance. The second main technical result gives an upper bound on $\chi^2(PK\|QK)$ in terms of total variation distance $\mathsf{TV}(P, Q)$ and $\epsilon$. We then utilize these bounds to establish locally private versions of the van Trees inequality, Le Cam's, Assouad's, and the mutual information methods, which are powerful tools for bounding minimax estimation risks. These results are shown to lead to better privacy analyses than the state-of-the-arts in several statistical problems such as entropy and discrete distribution estimation, non-parametric density estimation, and hypothesis testing.

Related papers

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• Robust Estimation of Discrete Distributions under Local Differential Privacy [1.52292571922932]
  We consider the problem of estimating a discrete distribution in total variation from $n$ contaminated data batches under a local differential privacy constraint. We show that combining the two constraints leads to a minimax estimation rate of $epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$ up to a $sqrtlog (1/epsilon)$ factor.
  arXiv  Detail & Related papers  (2022-02-14T15:59:02Z)
• Locally differentially private estimation of nonlinear functionals of discrete distributions [9.028773906859541]
  We study the problem of estimating non-linear functionals of discrete distributions in the context of local differential privacy. Only $alpha$-locally differentially private (LDP) samples are publicly available, where the term 'local' means that each $z_i$ is produced using one individual $x_i$. We describe the behavior of the quadratic risk for estimating the power sum functional $F_gamma = sum_k=1K p_kgamma$, $gamma >0$ as a function of $K,, n
  arXiv  Detail & Related papers  (2021-07-08T16:11:10Z)
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation [10.036088581191592]
  We present two sample-efficient differentially private mean estimators for $d$-dimensional (sub)Gaussian distributions. Our estimators output $tildemu$ such that $| tildemu - mu |_Sigma leq alpha$, where $| cdot |_Sigma$ is the Mahalanobis distance.
  arXiv  Detail & Related papers  (2021-06-24T21:40:07Z)
• Cascading Bandit under Differential Privacy [21.936577816668944]
  We study emphdifferential privacy (DP) and emphlocal differential privacy (LDP) in cascading bandits. Under DP, we propose an algorithm which guarantees $epsilon$-indistinguishability and a regret of $mathcalO(fraclog3 Tepsilon)$ for an arbitrarily small $xi$. Under ($epsilon$,$delta$)-LDP, we relax the $K2$ dependence through the tradeoff between privacy budgetepsilon$ and error probability $
  arXiv  Detail & Related papers  (2021-05-24T07:19:01Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Analysis of KNN Density Estimation [56.29748742084386]
  kNN density estimation is minimax optimal under both $ell_infty$ and $ell_infty$ criteria, if the support set is known. The $ell_infty$ error does not reach the minimax lower bound, but is better than kernel density estimation.
  arXiv  Detail & Related papers  (2020-09-30T03:33:17Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• A Universal Approximation Theorem of Deep Neural Networks for Expressing Probability Distributions [12.100913944042972]
  We prove that there exists a deep neural network $g:mathbbRdrightarrow mathbbR$ with ReLU activation. The size of neural network can grow exponentially in $d$ when $1$-Wasserstein distance is used as the discrepancy.
  arXiv  Detail & Related papers  (2020-04-19T14:45:47Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.