BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Competitive Online Algorithms for Budgeted Allocation with Applica
 tion to Online Experiment Design - Maryam Fazel (University of Washington)
DTSTART:20180626T134500Z
DTEND:20180626T143000Z
UID:TALK107407@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:We consider an online resource allocation problem\, where the 
 goal is to maximize a function of a positive semidefinite (PSD) matrix wit
 h a scalar budget constraint. The problem data arrives online\, and the al
 gorithm needs to make an irrevocable decision at each step. Of particular 
 interest are classic experiment design problems in the online setting\, wi
 th the algorithm deciding whether to allocate budget to each experiment as
  new experiments become available sequentially.   We analyze two classes o
 f primal-dual algorithms and provide bounds on their competitive ratios. O
 ur analysis relies on a smooth surrogate of the objective function that ne
 eds to satisfy a new diminishing-returns property. We then formulate a con
 vex optimization problem to directly optimize this competitive ratio bound
 \; this design problem can be solved offline before the data start arrivin
 g. We give examples of computing the smooth surrogate for D-optimal and A-
 optimal experiment design.  This is joint work with Reza Eghbali and James
  Saunderson.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR