Dictionary Learning and Anti-Concentration

Abstract

As central as concentration of measure is to the field of statistical learning theory, this thesis aims to motivate anti-concentration as a promising and under-utilized toolkit for the design and analysis of statistical learning algorithms. This thesis focuses on learning incoherent dictionaries A∗ from observations y = A∗x, where x is a sparse coefficient vector drawn from a generative model. We impose an exceedingly simple anti-concentration property on the entries of x, which we call (C, ρ)-smoothness. Leveraging this assumption, we present the first computationally efficient, provably correct algorithms to approximately recover A∗ even in the setting where neither the non-zero coordinates of x are guaranteed to be Ω (1) in magnitude, nor are the supports x chosen in a uniform fashion. As an application of our analytical framework, we present an algorithm with run-time and sample complexity polynomial in the dimensions of A∗ , and logarithmic in the desired precision, which learns a class of randomly generated Non-Negative Matrix Factorization instances up to arbitrary inverse polynomial error, with high probability.