# Optimistic and Adaptive Lagrangian Hedging

arXiv: https://arxiv.org/abs/2101.09603 · HTML: https://mlsanity.com/paper/2101.09603/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 23 Jan 2021.

## Builds on (most cited first, 10 of 10)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)

## Built on by (most cited first, 3 of 3)

- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games: Corrections](https://mlsanity.com/paper/2205.12031/) (2022)

## Abstract (arXiv)

In online learning an algorithm plays against an environment with losses possibly picked by an adversary at each round. The generality of this framework includes problems that are not adversarial, for example offline optimization, or saddle point problems (i.e. min max optimization). However, online algorithms are typically not designed to leverage additional structure present in non-adversarial problems. Recently, slight modifications to well-known online algorithms such as optimism and adaptive step sizes have been used in several domains to accelerate online learning -- recovering optimal rates in offline smooth optimization, and accelerating convergence to saddle points or social welfare in smooth games. In this work we introduce optimism and adaptive stepsizes to Lagrangian hedging, a class of online algorithms that includes regret-matching, and hedge (i.e. multiplicative weights). Our results include: a general general regret bound; a path length regret bound for a fixed smooth loss, applicable to an optimistic variant of regret-matching and regret-matching+; optimistic regret bounds for Phi regret, a framework that includes external, internal, and swap regret; and optimistic bounds for a family of algorithms that includes regret-matching+ as a special case.