We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

(Quasi)-Efficiently Learning Mixtures of Gaussians at the Statistically Optimal Separation

Formal Metadata

Title
(Quasi)-Efficiently Learning Mixtures of Gaussians at the Statistically Optimal Separation
Title of Series
Number of Parts
17
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Recovering a hidden signal or structure in the presence of random noise is a recurring theme in fundamental problems arising in computational complexity, cryptography, machine learning, and statistics. In the recent years, a Sum-of-Squares method, a hierarchy of generic semi-definite programming relaxations, has yielded a systematic approach for such "parameter estimation" problems. In this talk, I'll illustrate the SoS method for parameter estimation by means of a recent application of to learning mixture of gaussians with information theoretically optimal cluster-separation in quasi-polynomial time. No sub-exponential time algorithm was previously known in this regime.