Abstract
In this talk we will present new results on the variant of the sparse PCA model where one seeks to recover a binary k-sparse spike x ∈ {0, 1} p from observations of the form Y = λxxt + W where W is a GOE matrix and λ > 0. A large line of research suggests the rise of a “hard” regime, that is the existence of some values of λ > 0 for which recovery is possible in exponential time but not in polynomial time. Furthermore, some recent work by [Ding et al’2019] analyzed the performance of low-degree polynomial estimators for this recovery task, and conjectured the exact subexponential time needed to recover, for all the values of λ > 0 in the hard regime.
We will discuss some new results on the local dynamics of the recovery problem of interest, which establish that a large family of MCMC methods also requires the same subexponential time conjectured in [Ding et al ’2019] to succeed in the hard regime. The results are obtained by establishing the presence of the Overlap Gap Property and Free Energy Wells in the landscape of the problem, which are geometric properties introduced in the theory of spin glasses.
This is joint work with G ́erard Ben Arous and Alexander Wein.