Timezone: »

 
Poster
Efficient Minimax Strategies for Square Loss Games
Wouter M Koolen · Alan Malek · Peter Bartlett

Mon Dec 08 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session and Reception »
We consider online prediction problems where the loss between the prediction and the outcome is measured by the squared Euclidean distance and its generalization, the squared Mahalanobis distance. We derive the minimax solutions for the case where the prediction and action spaces are the simplex (this setup is sometimes called the Brier game) and the $\ell_2$ ball (this setup is related to Gaussian density estimation). We show that in both cases the value of each sub-game is a quadratic function of a simple statistic of the state, with coefficients that can be efficiently computed using an explicit recurrence relation. The resulting deterministic minimax strategy and randomized maximin strategy are linear functions of the statistic.
[ PDF] 

Author Information

Wouter M Koolen (Centrum Wiskunde & Informatica, Amsterdam)
Alan Malek (UC Berkeley)
Peter Bartlett (UC Berkeley)

More from the Same Authors