A Stochastic View of Optimal Regret through Minimax Duality

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.

References in corpus (1)

• Functional Bregman Divergence and Bayesian Estimation of Distributions

Cited by in corpus (15)

• Optimal Distributed Online Prediction using Mini-Batches
• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• Composite Binary Losses
• On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
• On-line PCA with Optimal Regrets
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• Optimal learning with Bernstein Online Aggregation
• Majorizing Measures, Sequential Complexities, and Online Learning
• Online Learning via Sequential Complexities
• Online and Batch Learning Algorithms for Data with Missing Features
• Online Convex Optimization in Changing Environments and its Application to Resource Allocation
• No-Regret Learnability for Piecewise Linear Losses
• A Meta-Learning Control Algorithm with Provable Finite-Time Guarantees
• Meta-Learning Guarantees for Online Receding Horizon Learning Control
• Online discrete optimization in social networks in the presence of Knightian uncertainty