Smoothed analysis for tensor methods in unsupervised learning

• 成果类型: Article
• 署名作者: Bhaskara, Aditya; Chen, Aidao; Perreault, Aidan; Vijayaraghavan, Aravindan
• 署名单位: Utah System of Higher Education; University of Utah; Northwestern University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01577-z
• 发表日期: 2022
• 页码: 549-599
• 关键词: blind identification; rank; Identifiability; inequalities; algorithms; models

摘要

Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in high-dimensional data analysis and unsupervised learning. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decomposition and learning mixtures of Gaussians, such guarantees have been hard to obtain for several other important problems in data analysis. 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 high-dimensional data analysis: Higher order tensor decompositions, where we generalize and analyze the socalled FOOBI algorithm of Cardoso. This allows us to obtain polynomially robust decomposition algorithms for 2l'th order tensors with rank O(n(l)). 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 overcompleteHMMsin the smoothed analysis model. Robust subspace recovery, when the fraction a of inliers in the d-dimensional subspace T subset of R-n is at least alpha > (d/n)(l) for any constant l is an element of Z(+). This contrasts with the known worst-case intractability when alpha < d/n, and the previous smoothed analysis result which needed alpha > d/n ([33]).