BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//132.216.98.100//NONSGML kigkonsult.se iCalcreator 2.20.4//
BEGIN:VEVENT
UID:20250917T111027EDT-0752DIVsfO@132.216.98.100
DTSTAMP:20250917T151027Z
DESCRIPTION:Title: Optimality of Glauber dynamics for general-purpose sampl
 ing: the view from statistics.\n\nAbstract: Glauber dynamics is a simple\,
  powerful\, and widely-studied Markov chain Monte Carlo method for samplin
 g from the Gibbs measures of spin systems. A tantalizing sequence of recen
 t results showed that Glauber dynamics mixes rapidly for Ising models prov
 ided only that the eigenvalues of the coupling matrix are confined to a sm
 all enough interval: under a suitable normalization\, one of length 1. In 
 particular\, these results yielded a breakthrough on the analysis of Glaub
 er dynamics for densely coupled disordered systems like the Sherrington-Ki
 rkpatrick spin glass model.\n	\n	I will present evidence that Glauber dynami
 cs 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 proc
 eed indirectly by relating this question to a system of conjectures in com
 putational statistics: I will first argue that an improved sampler could s
 olve a certain hypothesis testing task of detecting unusual vectors 'quiet
 ly planted' in random subspaces. I will then present evidence\, based on t
 he analysis of algorithms computing low-degree polynomials\, for the compu
 tational hardness of the latter task\, which will in turn give evidence th
 at better-than-Glauber general-purpose sampling is also hard.\n	\n	Time perm
 itting\, I may discuss ongoing work on generalizations in two directions: 
 first\, to the analogous question for Potts models\, and second\, to the a
 nalogous question for models on graphs and associated strategies for quiet
  planting using random lifts.\n
DTSTART:20240418T153000Z
DTEND:20240418T163000Z
LOCATION:Room 920\, Burnside Hall\, CA\, QC\, Montreal\, H3A 0B9\, 805 rue 
 Sherbrooke Ouest
SUMMARY:Tim Kunisky (Yale University)
URL:/mathstat/channels/event/tim-kunisky-yale-universi
 ty-356812
END:VEVENT
END:VCALENDAR