Statistics and Data Science

Low-temperature Mcmc Thresholds In Sparse Tensor Pca And Sparse Regression: Statistical-computational And Computational-local Gaps.

Here we examine two classic statistical parametric estimation tasks that are widely believed to exhibit statistical-computational gaps: sparse tensor PCA, and sparse linear regression. We examine the performance of so-called "low-temperature" Markov chains, that greedily maximise the posterior probability of a set of parameters. We prove upper and lower bounds on the necessary SNR to achieve fast mixing time. The negative result comes via a second moment method to prove the presence of the "Overlap Gap Property". The positive result is an application of a new general result on canonical paths to prove fast mixing times, which may be of independent interest.

Interestingly, in the case of sparse tensor PCA, we find that the required threshold for success of a low temperature Markov chain is significantly larger than the threshold where other polynomial methods are known to succeed, suggesting the existence of a local-computational gap.