A quest for an algorithmic theory for high-dimensional statistical inference

Title: A quest for an algorithmic theory for high-dimensional statistical inference

Abstract: When does a statistical inference problem admit an efficient algorithm?
There is an emergent body of research that studies this question by trying to understand the power and limitations of various algorithmic paradigms in solving statistical inference problems; for example, convex programming, Markov chain Monte Carlo (MCMC) algorithms, and message passing algorithms to name a few.

Of these, MCMC algorithms are easy to adapt to new inference problems and have shown strong performance in practice, which makes them promising as a universal algorithm for inference.  However, provable guarantees for MCMC have been scarce, lacking even for simple stylized models of inference.

In this talk, I will survey some recent strides that I have made with my collaborators on achieving provable guarantees for MCMC in inference, and some new tools we introduced for analyzing the behavior of slow-mixing Markov chains.

Bio: Sidhanth is a postdoc in the Theory of Computation group at MIT, fortunate to be hosted by Sam Hopkins. He is generally interested in theoretical computer science and probability theory. Most recently, he has been interested in the algorithms and complexity of inference problems.