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