BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Competitive Online Algorithms for Budgeted Allocat
 ion with Application to Online Experiment Design -
  Maryam Fazel (University of Washington)
DTSTART;TZID=Europe/London:20180626T144500
DTEND;TZID=Europe/London:20180626T153000
UID:TALK107407AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/107407
DESCRIPTION:We consider an online resource allocation problem\
 , where the goal is to maximize a function of a po
 sitive semidefinite (PSD) matrix with a scalar bud
 get constraint. The problem data arrives online\, 
 and the algorithm needs to make an irrevocable dec
 ision at each step. Of particular interest are cla
 ssic experiment design problems in the online sett
 ing\, with the algorithm deciding whether to alloc
 ate budget to each experiment as new experiments b
 ecome available sequentially.   We analyze two cla
 sses of primal-dual algorithms and provide bounds 
 on their competitive ratios. Our analysis relies o
 n a smooth surrogate of the objective function tha
 t needs to satisfy a new diminishing-returns prope
 rty. We then formulate a convex optimization probl
 em to directly optimize this competitive ratio bou
 nd\; this design problem can be solved offline bef
 ore the data start arriving. We give examples of c
 omputing the smooth surrogate for D-optimal and A-
 optimal experiment design.  This is joint work wit
 h Reza Eghbali and James Saunderson.
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:INI IT
END:VEVENT
END:VCALENDAR