Optimal Stragies and Minimax Lower Bounds for Online Convex Games

By Jacob D. Abernethy, Peter L. Bartlett, Alexander Rakhlin, Ambuj Tewari. 2008

193 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Adaptive Bound Optimization for Online Convex Optimization (2010, background): “This algorithm achieves a bound of O ( DM √ T ) where D is the diameter of the feasible region and M is a bound on g t 2 , matching the best possible bounds in terms of these parameters [Abernethy et al., 2008].”
Mind the Duality Gap: Logarithmic regret algorithms for online optimization (2008, background): “This equality is the underlying reason that the FTL strategy is a minimax strategy (See Abernethy et al. [2008] for a proof of this claim).”
Provable Guarantees for Gradient-Based Meta-Learning (2019, background): “Furthermore, the following lower-bound on the task-averaged regret, a multi-task extension of Abernethy et al. (2008, Theorem 4.2), shows that such constant factor reductions are the best we can achieve under our task similarity assumption: Corollary 2.1.”
A Stochastic View of Optimal Regret through Minimax Duality (2009, background): “Upon a review of the central results in adversarial online learning—most of which can be found in the recent book Cesa-Bianchi and Lugosi [5]—one cannot help but notice frequent similarities between the guarantees on performance of online algorithms and the analogous guarantees under stochastic…”
An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization (2021, background): “This loss depends on the distance from the chosen parameter on round t to the regret minimizer for round t−1, as well as the adversary’s choice on round t, and it 5We’ve omitted some details; see Abernethy et al. (2008) for the full result. can be bounded as Ω(1/t).”
Efficient Sequential Decision Making (2017, methodology): “The minimax optimal strategy is known also for: (i) the ball game withW = I [50] (our generalization to MahalanobisW 6= I results in fundamentally different strategies), (ii) the ball game withW = I and a constraint on the player’s deviation from the current empirical minimizer [2] (for which the op”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “[40] and Orabona [41] presented lower bounds of static regret, that is, β = 0 and D0 = 0.”
Improved Dynamic Regret for Non-degenerate Functions (2016, background): “Note that the answer to this question is no if one aims to promote the static regret in (1), according to the results on the minimax regret bound (Abernethy et al., 2008a).”
Proximal regularization for online and batch learning (2009, result): “Our analysis thus shows that the modified algorithm, in the worst case, is asymptotically equivalent to Pegasos up to (7)These results are not particularly surprising, given the recent minimax analysis of (Abernethy et al., 2008), who showed that under certain assumptions, the regret bound of the re”
Online Optimization : Competing with Dynamic Comparators (2015, unknown): “Then, nature reveals a convex functionft ∈ F to the learner.”
Adaptive Online Learning in Dynamic Environments (2018, background): “The O( √ T ) and O(log T ) regret bounds, for convex and strongly convex functions respectively, are known to be minimax optimal [Abernethy et al., 2008].”
Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization (2011, methodology): “We show (in Corollary 5) that this algorithm is identical to follow-the-leader on the functions f t (x) = gt · x + Rt(x), an algorithm that is minimax optimal in terms of regret against quadratic functions like f [Abernethy et al., 2008].”