Smoothed Analysis in Unsupervised Learning via Decoupling

Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in unsupervised learning and high-dimensional data analysis. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decompositions and learning mixtures of Gaussians, such guarantees have been hard to obtain for several other important problems in unsupervised learning. A core technical challenge in analyzing algorithms is obtaining lower bounds on the least singular value for random matrix ensembles with dependent entries, that are given by low-degree polynomials of a few base underlying random variables. In this work, we address this challenge by obtaining high-confidence lower bounds on the least singular value of new classes of structured random matrix ensembles of the above kind. We then use these bounds to design algorithms with polynomial time smoothed analysis guarantees for the following three important problems in unsupervised learning: •Robust subspace recovery, when the fraction of inliers in the d-dimensional subspace T of the n-dimensional Euclidean space is at least (d/n)t for any positive integer t. This contrasts with the known worst-case intractability when the fraction of inliers is at most d/n, and the previous smoothed analysis result (Hardt and Moitra, 2013). •Learning overcomplete hidden markov models, where the size of the state space is any polynomial in the dimension of the observations. This gives the first polynomial time guarantees for learning overcomplete HMMs in the smoothed analysis model. •Higher order tensor decompositions, where we generalize and analyze the so-called FOOBI algorithm of Cardoso to find order-T rank-one tensors in a subspace. This gives polynomially robust decomposition algorithms for order-2t tensors with rank nt.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages582-610
Number of pages29
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Country/TerritoryUnited States
CityBaltimore
Period11/9/1911/12/19

Keywords

  • anti concentration
  • beyond worst-case analysis
  • hidden markov model
  • smoothed analysis
  • subspace recovery
  • tensor decomposition
  • unsupervised learning

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Smoothed Analysis in Unsupervised Learning via Decoupling'. Together they form a unique fingerprint.

Cite this