BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/909
DTSTAMP:20230914T125943Z
SUMMARY:Learning and Testing Causal Models with Interventions
DESCRIPTION:Speaker: Saravanan Kandasamy (Indian Institute of Science\nDepa
 rtment of Computer\nScience & Automation\nBangalore 560012)\n\nAbstract: \
 nAbstract: We consider testing and learning problems on causal Bayesian ne
 tworks as defined by Pearl.  Given a causal Bayesian network M on a grap
 h with  n discrete variables and bounded in-degree and bounded ``confou
 nded  components''\, we show that O(log n) interventions on an unknown c
 ausal  Bayesian network X on the same graph\, and O(n/epsilon^2) samples
  per  intervention\, suffice to efficiently distinguish whether X=M or w
 hether  there exists some intervention under which X and M are farther t
 han  epsilon in total variation distance. We also obtain  sample/time/i
 ntervention efficient algorithms for: (i) testing the  identity of two u
 nknown causal Bayesian networks on the same graph\; and (ii) learning a 
 causal Bayesian network on a given graph. Although our  algorithms are n
 on-adaptive\, we show that adaptivity does not help in general: Omega(lo
 g n) interventions are necessary for testing the identity of two unknown 
 causal Bayesian networks on the same graph\, even adaptively. Our algorit
 hms are enabled by a new subadditivity inequality for the squared Helling
 er distance between two causal Bayesian networks (joint work with: Jayade
 v Acharya\, Arnab Bhattacharyya and Constantinos  Daskalakis).\n
URL:https://www.tcs.tifr.res.in/web/events/909
DTSTART;TZID=Asia/Kolkata:20181016T140000
DTEND;TZID=Asia/Kolkata:20181016T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR