Competitive Online Algorithms for Budgeted Allocation with Application to Online Experiment Design

Add to your list(s) Download to your calendar using vCal

• Maryam Fazel (University of Washington)
• Tuesday 26 June 2018, 14:45-15:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

STSW04 - Future challenges in statistical scalability

We consider an online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We analyze two classes of primal-dual algorithms and provide bounds on their competitive ratios. Our analysis relies on a smooth surrogate of the objective function that needs to satisfy a new diminishing-returns property. We then formulate a convex optimization problem to directly optimize this competitive ratio bound; this design problem can be solved offline before the data start arriving. 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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.