BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Distribution Learning Meets Graph Structure Sampling - Arnab Bhatt
 acharya (University of Warwick)
DTSTART:20250422T130000Z
DTEND:20250422T140000Z
UID:TALK229699@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:This work establishes a novel link between the problem of PAC-
 learning high-dimensional graphical models and the task of (efficient) cou
 nting and sampling of graph structures\, using an online learning framewor
 k. We observe that if we apply the exponentially weighted average (EWA) or
  randomized weighted majority (RWM) forecasters on a sequence of samples f
 rom a distribution P using the log loss function\, the average regret incu
 rred by the forecaster's predictions can be used to bound the expected KL 
 divergence between P and the predictions. Known regret bounds for EWA and 
 RWM then yield new sample complexity bounds for learning Bayes nets. Moreo
 ver\, these algorithms can be made computationally efficient for several i
 nteresting classes of Bayes nets. Specifically\, we give a new sample-opti
 mal and polynomial time learning algorithm with respect to trees of unknow
 n structure and the first polynomial sample and time algorithm for learnin
 g with respect to Bayes nets over a given chordal skeleton.\n\nJoint work 
 with Sutanu Gayen (IIT Kanpur)\, Philips George John (NUS)\, Sayantan Sen 
 (NUS)\, and N.V. Vinodchandran (U Nebraska Lincoln)\n
LOCATION:Computer Laboratory\, William Gates Building\, FW26
END:VEVENT
END:VCALENDAR