香蕉视频

罢颈迟濒别:听Optimality of Glauber dynamics for general-purpose sampling: the view from statistics.

Abstract:聽Glauber dynamics is a simple, powerful, and widely-studied Markov chain Monte Carlo method for sampling from the Gibbs measures of spin systems. A tantalizing sequence of recent results showed that Glauber dynamics mixes rapidly for Ising models provided only that the eigenvalues of the coupling matrix are confined to a small enough interval: under a suitable normalization, one of length 1. In particular, these results yielded a breakthrough on the analysis of Glauber dynamics for densely coupled disordered systems like the Sherrington-Kirkpatrick spin glass model.

I will present evidence that Glauber dynamics is optimal for this kind of "general-purpose" sampling task, namely, that no other polynomial-time algorithm can make a similar guarantee while improving on the constant 1. The proof, perhaps surprisingly, will proceed indirectly by relating this question to a system of conjectures in computational statistics: I will first argue that an improved sampler could solve a certain hypothesis testing task of detecting unusual vectors "quietly planted" in random subspaces. I will then present evidence, based on the analysis of algorithms computing low-degree polynomials, for the computational hardness of the latter task, which will in turn give evidence that better-than-Glauber general-purpose sampling is also hard.

Time permitting, I may discuss ongoing work on generalizations in two directions: first, to the analogous question for Potts models, and second, to the analogous question for models on graphs and associated strategies for quiet planting using random lifts.