Are generative models the new sparsity?

Abstract:
Sparse principle component analysis is being used in a range of applications and attracted interest of theoreticians for its algorithmically challenging properties. Sparsity is a widely explored way to reduce dimensionality. Another such way, that is recently widely studied, is learning generative models from data. In this talk I will discuss what happens when sparsity is replaced by generative models. I will present a detailed study of the spiked matrix model with the spike coming from generative model. I will show that the computational gap well-known in sparse principle component analysis does not exist in this case. I will discuss the behaviour of message passing algorithms and a construction and analysis of optimality-achieving spectral algorithms. Talk is based on arxiv:1905.12385.