Minimax Optimal Algorithms for Unconstrained Linear Optimization
Venue
Advances in Neural Information Processing Systems (NIPS) (2013)
Publication Year
2013
Authors
H. Brendan McMahan, Jacob Abernethy
BibTeX
Abstract
We design and analyze minimax-optimal algorithms for online linear optimization
games where the player's choice is unconstrained. The player strives to minimize
regret, the difference between his loss and the loss of a post-hoc benchmark
strategy. While the standard benchmark is the loss of the best strategy chosen from
a bounded comparator set, we consider a very broad range of benchmark functions.
The problem is cast as a sequential multi-stage zero-sum game, and we give a
thorough analysis of the minimax behavior of the game, providing characterizations
for the value of the game, as well as both the player's and the adversary's optimal
strategy. We show how these objects can be computed efficiently under certain
circumstances, and by selecting an appropriate benchmark, we construct a novel
hedging strategy for an unconstrained betting game.
