Paper Overview
Area: Machine Learning Authors: Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani Published: 2026-06-25 arXiv: 2606.27315
Summary
Gradient equilibrium (GEQ) is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization to the online setting, and abstracts problems such as online conformal prediction. Although GEQ shows curious similarities with known online learning frameworks—in particular regret minimization—prior work has shown that GEQ error and regret are incomparable objectives, leaving open a precise understanding of how GEQ fits into the broader online learning landscape.
In this work, the authors show that GEQ is equivalent to Blackwell approachability in the algorithmic sense:
- Any Blackwell approachability problem can be solved by querying a black-box GEQ oracle, with no asymptotic loss in the oracle's error rate.
- Conversely, GEQ can be solved via Blackwell approachability.
- The reductions are efficient, and can be used to transfer refined guarantees—such as optimism and strong adaptivity—from regret minimization to GEQ.
- The authors identify necessary and sufficient conditions for GEQ.
- They establish reductions between different notions of GEQ on unconstrained versus constrained decision sets.
Taken together with known equivalences among approachability, regret minimization, and calibration, these results imply that GEQ is also equivalent to those frameworks.
Key Contributions
Original Abstract (excerpt)
> Gradient equilibrium (GEQ) is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization and abstracts problems like online conformal prediction. While GEQ has curious similarities with known online learning frameworks, namely regret minimization, prior work has shown that GEQ error and regret are incomparable objectives, leaving open a precise understanding of how GEQ fits into the broader online learning landscape. In this work, we show that GEQ is equivalent to Blackwell approachability in the algorithmic sense...
---
*Auto-collected on 2026-06-28*