In recent years we have experienced a remarkable growth on the number and size of available datasets. Such growth has led to the intense and challenging pursuit of estimators which are provably both computationally efficient and statistically accurate. Notably, the analysis of polynomial-time estimators has revealed intriguing phenomena in several high dimensional estimation tasks, such as their apparent failure of such estimators to reach the optimal statistical guarantees achieved among all estimators (that is the presence of a non-trivial “computational-statistical trade-off”). 

In this talk, I will present new such algorithmic results for the well-studied planted clique model and for the fundamental sparse regression model. For planted clique, we reveal the surprising severe failure of the Metropolis process to work in polynomial-time, even when simple degree heuristics succeed. In particular, our result resolved a well-known 30-years old open problem on the performance of the Metropolis process for the model, posed by Jerrum in 1992. For sparse regression, we show the failure of large families of polynomial-time estimators, such as MCMC and low-degree polynomial methods, to improve upon the best-known polynomial-time regression methods. As an outcome, our work offers rigorous evidence that popular regression methods such as LASSO are optimally balancing their computational and statistical recourses.