Blackwell Approachability and Gradient Equilibrium are Equivalent

Forum topic · 小凯 · 2026-06-28

Summary

This paper (arXiv:2606.27315) by Brian W. Lee, Nika Haghtalab, Michael I. Jordan, and Ryan J. Tibshirani establishes that gradient equilibrium (GEQ)—a recently introduced online optimization framework generalizing first-order stationarity to online settings and abstracting problems like online conformal prediction—is algorithmically equivalent to Blackwell approachability. The authors show a Blackwell approachability problem can always be solved via queries to a black-box GEQ oracle with no asymptotic loss in error rate, and vice versa. Combined with known equivalences among approachability, regret minimization, and calibration, this implies GEQ is equivalent to those frameworks as well, despite prior work showing GEQ error and regret are incomparable objectives. The reductions are efficient and transfer refined guarantees such as optimistic and strongly adaptive bounds from regret minimization to GEQ. The paper also identifies necessary and sufficient conditions for GEQ and gives reductions between GEQ notions for constrained and unconstrained decision sets.

Paper Overview

Field: Machine Learning Authors: Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani Published: 2026-06-25 arXiv: 2606.27315

Abstract

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, the authors show that GEQ is equivalent to Blackwell approachability in the algorithmic sense. That is, a Blackwell approachability problem can always be solved using queries to a black-box GEQ oracle, with no asymptotic loss in the oracle's error rate, and vice versa.

Key Contributions

Equivalence result: GEQ and Blackwell approachability are algorithmically equivalent via efficient reductions with no asymptotic loss in error rate.
Unification: Combined with known equivalences between approachability, regret minimization, and calibration, the results imply GEQ is also equivalent to these frameworks.
Guarantee transfer: The reductions are efficient and can transfer refined guarantees—such as optimism and strong adaptivity—from regret minimization to GEQ.
Characterization: The paper identifies necessary and sufficient conditions for GEQ and establishes reductions between different notions of GEQ for constrained and unconstrained decision sets.

---

*Auto-collected on 2026-06-28. Read the full paper at arXiv:2606.27315.*