Better Gaussian Mechanism using Correlated Noise

• URL: http://arxiv.org/abs/2408.06853v2
• Date: Tue, 29 Oct 2024 14:58:32 GMT
• Title: Better Gaussian Mechanism using Correlated Noise
• Authors: Christian Janos Lebeda,
• Abstract summary: We show that adding a random variable distributed as a Gaussian with variance scaled by $(sqrtd + 1)/4$ to all counts allows us to reduce the variance of the independent noise samples to scale only with $(d + sqrtd)/4$. The central idea of our mechanism is simple and the technique is flexible.
• Score: 1.450405446885067
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a simple variant of the Gaussian mechanism for answering differentially private queries when the sensitivity space has a certain common structure. Our motivating problem is the fundamental task of answering $d$ counting queries under the add/remove neighboring relation. The standard Gaussian mechanism solves this task by adding noise distributed as a Gaussian with variance scaled by $d$ independently to each count. We show that adding a random variable distributed as a Gaussian with variance scaled by $(\sqrt{d} + 1)/4$ to all counts allows us to reduce the variance of the independent Gaussian noise samples to scale only with $(d + \sqrt{d})/4$. The total noise added to each counting query follows a Gaussian distribution with standard deviation scaled by $(\sqrt{d} + 1)/2$ rather than $\sqrt{d}$. The central idea of our mechanism is simple and the technique is flexible. We show that applying our technique to another problem gives similar improvements over the standard Gaussian mechanism.

Related papers

• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Here we study the complexity of NGCA in the Sum-of-Squares framework.
  arXiv  Detail & Related papers  (2024-10-28T18:19:13Z)
• Count on Your Elders: Laplace vs Gaussian Noise [9.546521474972485]
  We argue that Laplace noise may in fact be preferable to Gaussian noise in many settings. We show that the noise added by the Gaussian mechanism can always be replaced by Laplace noise of comparable variance. This challenges the conventional wisdom that Gaussian noise should be used for high-dimensional noise.
  arXiv  Detail & Related papers  (2024-08-13T16:36:33Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances [15.990720051907864]
  Subset-of-Signals model serves as a benchmark for heteroskedastic mean estimation. Our algorithm resolves this open question up to logarithmic factors. Even for $d=2$, our techniques enable rates comparable to knowing the variance of each sample.
  arXiv  Detail & Related papers  (2023-12-05T01:13:10Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  Differentially private computation often begins with a bound on some $d$-dimensional statistic's sensitivity. For pure differential privacy, the $K$-norm mechanism can improve on this approach using a norm tailored to the statistic's sensitivity space. This paper solves both problems for the simple statistics of sum, count, and vote.
  arXiv  Detail & Related papers  (2023-09-27T17:09:36Z)
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
  We study the problem of estimating mixtures of Gaussians under the constraint of differential privacy (DP) Our main result is that $textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$ samples are sufficient to estimate a mixture of $k$ Gaussians in $mathbbRd$ up to total variation distance $alpha$. This is the first finite sample complexity upper bound for the problem that does not make any structural assumptions on the GMMs.
  arXiv  Detail & Related papers  (2023-09-07T17:02:32Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• On the Role of Channel Capacity in Learning Gaussian Mixture Models [31.841289319809814]
  We study the sample complexity of learning the $k$ unknown centers of a balanced Gaussian mixture model (GMM) Our main results characterize the exact noise threshold $sigma2$ below which the GMM learning problem, in the large system limit $d,ktoinfty$, is as easy as learning from labeled observations. While our results are only proved for GMMs whose centers are uniformly distributed over the sphere, they hint that perhaps it is the decoding error probability associated with the center constellation as a channel code that determines the statistical difficulty of learning the corresponding GMM.
  arXiv  Detail & Related papers  (2022-02-15T20:15:00Z)
• 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)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• 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)

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.