RAIN schedule for Autumn Quarter 2014-15
The RAIN seminar is held on Wednesdays from 12:00-1:00pm in Y2E2 101. And yes, lunch is provided!
|September 24||Balasubramanian Sivan||Towards optimal algorithms for prediction with expert advice|
|October 8||Vivek Farias||TBA|
|December 3||Adam Wierman||TBA
(Joint seminar with OIT and OR)
Google Calendar for RAIN
Previous year's talks
Archived talks can be accessed here.
Talk AbstractsTowards optimal algorithms for prediction with expert advice
Balasubramanian Sivan, Microsoft Research
We study the classic problem of prediction with expert advice. Focusing on settings with a constant number of experts, we develop optimal algorithms and obtain precisely optimal regret values for the case of 2 and 3 experts. Further, we develop regret lower bounds for the multiplicative weights algorithm that exactly match the known upper bounds for an arbitrary number of experts k. This establishes a constant factor separation between the regrets achieved by the optimal algorithm and the multiplicative weights algorithm for a constant number of experts.
The optimal algorithms have a crisp interpretation. For instance, in the case of 2 experts, the optimal algorithm follows the advice of a particular expert with exactly the probability that the expert will turn out to be the best expert.
Our main tool is the minimax principle which lets us analyze the optimal adversary to compute optimal regret values. While analyzing the optimal adversary, we establish deep connections with non-trivial aspects of random walk. We further use this connection to develop an improved regret bound for the case of 4 experts.
Joint work with Nick Gravin and Yuval Peres
Bio: Balasubramanian Sivan is a postdoctoral researcher at Microsoft Research, Redmond. He completed his PhD in Computer Science at the University of Wisconsin-Madison in 2013. His PhD thesis on “Prior Robust Optimization” was awarded the 2014 ACM SIGecom doctoral dissertation award and the University of Wisconsin-Madison Computer Science department’s outstanding graduate student researcher award. His research interests are in Algorithmic Game Theory, online and approximation algorithms, expert learning. More details can be found here: http://research.microsoft.com/en-us/um/people/bsivan/