Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
This work addresses unsupervised learning problems for machine learning practitioners, but it is incremental as it extends a previous noise-free framework to handle noise.
The authors tackled the problem of designing efficient algorithms for unsupervised learning tasks like mixtures of Gaussians and subspace clustering by introducing a general framework that learns arithmetic formulas in noisy settings, building on prior noise-free work and relying on a novel robust vector space decomposition algorithm.
We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal and Saha (FOCS 20), who designed such a framework for learning arithmetic circuits without any noise. A key ingredient of our meta algorithm is an efficient algorithm for a novel problem called Robust Vector Space Decomposition. We show that our meta algorithm works well when certain matrices have sufficiently large smallest non-zero singular values. We conjecture that this condition holds for smoothed instances of our problems, and thus our framework would yield efficient algorithms for these problems in the smoothed setting.