Settling the Robust Learnability of Mixtures of Gaussians

• URL: http://arxiv.org/abs/2011.03622v3
• Date: Sun, 25 Jul 2021 20:46:03 GMT
• Title: Settling the Robust Learnability of Mixtures of Gaussians
• Abstract summary: We give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. At the heart of our algorithm is a new method for proving dimension-independent identifiability. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.
• Score: 19.229475414802213
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights (bounded fractionality) and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving dimension-independent polynomial identifiability through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.

Related papers

• Efficient learning of bosonic Gaussian unitaries [3.1022255067547877]
  We present the first time-efficient for learning bosonic Gaussian unitaries with a rigorous analysis.<n>Our algorithm produces an estimate of the unknown unitary that is accurate to small worst-case error.
  arXiv  Detail & Related papers  (2025-10-07T02:42:40Z)
• Efficient Hamiltonian, structure and trace distance learning of Gaussian states [2.949446809950691]
  We show that it is possible to learn the underlying interaction graph in a similar setting and sample complexity. Our results put the status of the quantum Hamiltonian learning problem for continuous variable systems in a much more advanced state.
  arXiv  Detail & Related papers  (2024-11-05T15:07:20Z)
• 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)
• Symbolic Recovery of Differential Equations: The Identifiability Problem [52.158782751264205]
  Symbolic recovery of differential equations is the ambitious attempt at automating the derivation of governing equations. We provide both necessary and sufficient conditions for a function to uniquely determine the corresponding differential equation. We then use our results to devise numerical algorithms aiming to determine whether a function solves a differential equation uniquely.
  arXiv  Detail & Related papers  (2022-10-15T17:32:49Z)
• AutoIP: A United Framework to Integrate Physics into Gaussian Processes [15.108333340471034]
  We propose a framework that can integrate all kinds of differential equations into Gaussian processes. Our method shows improvement upon vanilla GPs in both simulation and several real-world applications.
  arXiv  Detail & Related papers  (2022-02-24T19:02:14Z)
• Numerical Solution of Stiff Ordinary Differential Equations with Random Projection Neural Networks [0.0]
  We propose a numerical scheme based on Random Projection Neural Networks (RPNN) for the solution of Ordinary Differential Equations (ODEs) We show that our proposed scheme yields good numerical approximation accuracy without being affected by the stiffness, thus outperforming in same cases the textttode45 and textttode15s functions.
  arXiv  Detail & Related papers  (2021-08-03T15:49:17Z)
• Probabilistic Simplex Component Analysis [66.30587591100566]
  PRISM is a probabilistic simplex component analysis approach to identifying the vertices of a data-circumscribing simplex from data. The problem has a rich variety of applications, the most notable being hyperspectral unmixing in remote sensing and non-negative matrix factorization in machine learning.
  arXiv  Detail & Related papers  (2021-03-18T05:39:00Z)
• 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)
• Learning Mixtures of Low-Rank Models [89.39877968115833]
  We study the problem of learning computational mixtures of low-rank models. We develop an algorithm that is guaranteed to recover the unknown matrices with near-optimal sample. In addition, the proposed algorithm is provably stable against random noise.
  arXiv  Detail & Related papers  (2020-09-23T17:53:48Z)
• 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)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.