A Stochastic View of Optimal Regret through Minimax Duality

By Jacob D. Abernethy, Alekh Agarwal, Peter L. Bartlett, Alexander Rakhlin. 2009

99 citations recorded by the source corpus.

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.

Subfields: Finance, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Finance

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “serial algorithm on an arbitrary convex loss is O( √ m) (e.g., Nemirovski and Yudin, 1983; Cesa-Bianchi and Lugosi, 2006; Abernethy et al., 2009).”
Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization (2014, methodology): “The study of lower bounds for stochastic convex optimization was undertaken by Nemirovski and Yudin [1983], and recently extended and refined by Agarwal et al. [2012]. Online convex optimization was introduced by Zinkevich [2003]. Optimal lower bounds for the convex case, even in the stochastic sett”
Communication-Efficient Distributed Online Prediction by Dynamic Model Synchronization (2014, background): “The predictive performance of these two extremes in terms of static regret lies between O( √ kT ) for serial learning (which is optimal for the stationary setting, see Cesa-Bianchi and Lugosi [5] and [1]) and O(k √ T ) for no communication, which corresponds to solving k separate online learning pro”
Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing (2015, methodology): “1) suffered by a single processor processing the M examples in sequence is Ωp?Mq (Nemirovski & Yudin, 1983; Cesa-Bianchi & Lugosi, 2006; Abernethy et al., 2009). Dekel et al. (2012) demonstrate that, using a distributed mini-batch approach, they can achieve Op?Mq regret even though the processing is”
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization (2011, unknown): “Abernethy et al. (2009) put this lower bound in a general framework for min-max regret minimization. It has been brought to our attention that Juditsky and Nesterov (2010) have recently published a technical report that has a very similar algorithm to ours, and also obtain an O( 1 T ) convergence ra”
Sequential complexities and uniform martingale laws of large numbers (2015, background): “In [1, 24] connections between minimax rates of sequential prediction problems and the supremum of the process Mn(f) over the associated class of predictors F are established.”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “Both the O( √ T ) and O(log T ) rates are known to be minimax optimal (Abernethy et al., 2009).”
Optimal Distributed Online Prediction (2011, methodology): “Using gradient-based serial algorithms, the regret bound in this case is O ( √ m ), and is known to be optimal (Nemirovski & Yudin, 1983; Abernethy et al., 2009).”
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. (2010, background): “Abernethy et al. (2009); Cesa-Bianchi and Lugosi (2006) and references therein).”
Composite Binary Losses (2009, background): “There has been increasing awareness of the importance of the conditional Bayes risk curve L ( η ) — also known as “generalized entropy” [17] — in the analysis of losses for probability estimation [23, 24, 1, 32].”
Trading regret for efficiency: online convex optimization with long term constraints (2011, methodology): “In Abernethy et al. (2009), using game-theoretic analysis, it has been shown that both O( √ T ) for Lipschitz continuous and O(log T ) for strongly convex loss functions are tight in the minimax sense.”