Sample-Efficient Private Learning of Mixtures of Gaussians

• URL: http://arxiv.org/abs/2411.02298v1
• Date: Mon, 04 Nov 2024 17:23:52 GMT
• Title: Sample-Efficient Private Learning of Mixtures of Gaussians
• Authors: Hassan Ashtiani, Mahbod Majid, Shyam Narayanan,
• Abstract summary: We prove that roughly $kd2 + k1.5 d1.75 + k2 d$ samples suffice to learn a mixture of $k$ arbitrary $d$-dimensional Gaussians. Our work improves over the previous best result [AAL24b] and is provably optimal when $d$ is much larger than $k2$.
• Score: 11.392841244701605
• License:
• Abstract: We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly $kd^2 + k^{1.5} d^{1.75} + k^2 d$ samples suffice to learn a mixture of $k$ arbitrary $d$-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result [AAL24b] (which required roughly $k^2 d^4$ samples) and is provably optimal when $d$ is much larger than $k^2$. Moreover, we give the first optimal bound for privately learning mixtures of $k$ univariate (i.e., $1$-dimensional) Gaussians. Importantly, we show that the sample complexity for privately learning mixtures of univariate Gaussians is linear in the number of components $k$, whereas the previous best sample complexity [AAL21] was quadratic in $k$. Our algorithms utilize various techniques, including the inverse sensitivity mechanism [AD20b, AD20a, HKMN23], sample compression for distributions [ABDH+20], and methods for bounding volumes of sumsets.

Related papers

• Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures [5.668124846154999]
  We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine. Our method gives a non-spherical analog of the classical dimension reduction, based on singular value decomposition. Our algorithms naturally extend to tolerating a dimension-independent fraction of arbitrary outliers.
  arXiv  Detail & Related papers  (2024-11-19T11:58:51Z)
• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Privately Learning Mixtures of Axis-Aligned Gaussians [12.77304082363491]
  We show that $widetildeO(k2 d log3/2 (1/delta) / alpha2 varepsilon)$ samples are sufficient to learn a mixture of $k$ axis-aligned Gaussians. We design a new technique for privately learning mixture distributions.
  arXiv  Detail & Related papers  (2021-06-03T22:34:23Z)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Robust Learning of Mixtures of Gaussians [13.173307471333617]
  We learn to error $poly(eps)$ in total variation when $X$ is an evenly weighted mixture of two arbitrary $d$-dimensional Gaussians. In particular, if $X$ is an evenly weighted mixture of two arbitrary $d$-dimensional Gaussians, we devise a time algorithm that given access to samples from $X$ an $eps$-fraction of which have been adversarially corrupted.
  arXiv  Detail & Related papers  (2020-07-12T05:15:50Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. We test our methods on problems with $p$ as large as $500,000$.
  arXiv  Detail & Related papers  (2020-06-15T21:55:34Z)
• 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)
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians [21.780375994511324]
  We prove a new result for the ExpectationMaximization (EM): we show that EM converges locally, under separation $Omega(sqrtlog k)$. Our results do not assume or use prior knowledge of the (potentially different) Gaussian components.
  arXiv  Detail & Related papers  (2020-02-02T05:09:26Z)

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.