BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Algorithms for Learning using Local Queries
DTSTART:20140331T161500
DTEND:20140331T173000
DTSTAMP:20260406T170130Z
UID:96f6c89221bfef89e7cbcf433bef2f910ebcc1e18fc914914cafcee8
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : Varun Kanade\, UC Berkeley\nIC Faculty candidateAbstract\
 nThe probably approximately correct (PAC) learning setting introduced by V
 aliant (1984) is a theoretical framework for studying automated learning f
 rom examples. The membership query model (MQ) is an extension\, where the 
 learning algorithm is allowed to construct its own examples and ask a (pos
 sibly human) oracle for labels. A rich theory has been developed in this f
 ramework\, connecting learning to other areas of theoretical computer scie
 nce\, including complexity\, cryptography\, and the analysis of boolean fu
 nctions.\nThere are two main shortcomings that make this theory less relev
 ant in practice:\n(i) Many algorithms only have guarantees under the unifo
 rm distribution\n(ii) Membership query algorithms ask queries that appear 
 nonsensical to humans\nIn this talk\, I will present work that makes progr
 ess on both these fronts. We define a notion of local membership queries\,
  where the learning algorithm is allowed to construct queries only through
  small modifications to examples received as part of the training set. We 
 consider a class of smooth distributions\, far more general than the unifo
 rm distribution\, and show that the class of decision trees can be learned
  with local membership queries.\nI will present a few other results and so
 me directions for future work.\n(Based on joint work with P. Awasthi and V
 . Feldman)Biography\nVarun Kanade is currently a Simons Postdoctoral Fello
 w at the University of California\, Berkeley. He obtained his Ph.D. from H
 arvard University under the guidance of Prof. Leslie Valiant. He received 
 his B.Tech. from the Indian Institute of Technology\, Bombay. His research
  interests are in learning theory\, but also more broadly in machine learn
 ing\, theoretical computer science and evolutionary biology.More informati
 on
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR