A Stochastic View of Optimal Regret through Minimax Duality Export

@article{citeulike:4252168, abstract = {We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary.}, archivePrefix = {arXiv}, author = {Abernethy, Jacob and Agarwal, Alekh and Bartlett, Peter L. and Rakhlin, Alexander}, citeulike-article-id = {4252168}, citeulike-linkout-0 = {http://arxiv.org/abs/0903.5328}, citeulike-linkout-1 = {http://arxiv.org/pdf/0903.5328}, comment = {This is a preliminary version of the same authors' COLT 2009 paper entitled "A Stochastic View of Optimal Regret through Minimax Duality".}, day = {30}, eprint = {0903.5328}, keywords = {bregman\_divergence, convexity, duality, game\_theory, online}, month = {Mar}, posted-at = {2009-04-01 09:03:19}, priority = {5}, title = {A Stochastic View of Optimal Regret through Minimax Duality}, url = {http://arxiv.org/abs/0903.5328}, year = {2009} }

TY - JOUR ID - citeulike:4252168 L3 - citeulike-article-id:4252168 N2 - We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary. TI - A Stochastic View of Optimal Regret through Minimax Duality KW - bregman_divergence KW - convexity KW - duality KW - game_theory KW - online N1 - This is a preliminary version of the same authors' COLT 2009 paper entitled "A Stochastic View of Optimal Regret through Minimax Duality". AU - Abernethy, Jacob AU - Agarwal, Alekh AU - Bartlett, Peter AU - Rakhlin, Alexander PY - 2009/Mar/30/ UR - http://arxiv.org/abs/0903.5328 ER -