Robust Learning of Mixtures of Gaussians

• URL: http://arxiv.org/abs/2007.05912v1
• Date: Sun, 12 Jul 2020 05:15:50 GMT
• Title: Robust Learning of Mixtures of Gaussians
• Authors: Daniel M. Kane
• Abstract summary: 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.
• Score: 13.173307471333617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We resolve one of the major outstanding problems in robust statistics. In particular, if $X$ is an evenly weighted mixture of two arbitrary $d$-dimensional Gaussians, we devise a polynomial time algorithm that given access to samples from $X$ an $\eps$-fraction of which have been adversarially corrupted, learns $X$ to error $\poly(\eps)$ in total variation distance.

Related papers

• Sample-Efficient Private Learning of Mixtures of Gaussians [11.392841244701605]
  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$.
  arXiv  Detail & Related papers  (2024-11-04T17:23:52Z)
• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  We study the problem of learning mixtures of $k$ Gaussians in $d$ dimensions. We make no separation assumptions on the underlying mixture components. We give an algorithm that draws $dmathrmpoly(k/varepsilon)$ samples from the target mixture, runs in sample-polynomial time, and constructs a sampler.
  arXiv  Detail & Related papers  (2024-04-29T17:30:36Z)
• Learning GMMs with Nearly Optimal Robustness Guarantees [25.313563663123354]
  robustness guarantee is optimal up to polylogarithmic factors. At the heart of our algorithm is a new way to relax a system of equations which corresponds to solving an improper learning problem.
  arXiv  Detail & Related papers  (2021-04-19T22:14:54Z)
• 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)
• Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
  We give a-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in $mathbbRd$, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions. Our main tools are an efficient emphpartial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.
  arXiv  Detail & Related papers  (2020-12-03T17:54:03Z)
• 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)
• 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)
• 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.