Blackwell Approachability and Gradient Equilibrium are Equivalent

Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4585-4587, 2026.

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, such as regret minimization, prior work has shown that GEQ error and regret are incomparable as 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. 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. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply an equivalence between GEQ and these frameworks, as well. Hence, while GEQ guarantees are semantically different from known online learning guarantees, GEQ algorithms are equally powerful primitives as classical regret minimization and calibration algorithms. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Our techniques can also be used to identify necessary and sufficient conditions for GEQ, and to establish reductions between different notions of GEQ with unconstrained and constrained decision sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-lee26c, title = {Blackwell Approachability and Gradient Equilibrium are Equivalent}, author = {Lee, Brian W. and Haghtalab, Nika and Jordan, Michael I. and Tibshirani, Ryan J.}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4585--4587}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/lee26c/lee26c.pdf}, url = {https://proceedings.mlr.press/v336/lee26c.html}, 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, such as regret minimization, prior work has shown that GEQ error and regret are incomparable as 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. 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. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply an equivalence between GEQ and these frameworks, as well. Hence, while GEQ guarantees are semantically different from known online learning guarantees, GEQ algorithms are equally powerful primitives as classical regret minimization and calibration algorithms. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Our techniques can also be used to identify necessary and sufficient conditions for GEQ, and to establish reductions between different notions of GEQ with unconstrained and constrained decision sets.} }
Endnote
%0 Conference Paper %T Blackwell Approachability and Gradient Equilibrium are Equivalent %A Brian W. Lee %A Nika Haghtalab %A Michael I. Jordan %A Ryan J. Tibshirani %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-lee26c %I PMLR %P 4585--4587 %U https://proceedings.mlr.press/v336/lee26c.html %V 336 %X 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, such as regret minimization, prior work has shown that GEQ error and regret are incomparable as 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. 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. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply an equivalence between GEQ and these frameworks, as well. Hence, while GEQ guarantees are semantically different from known online learning guarantees, GEQ algorithms are equally powerful primitives as classical regret minimization and calibration algorithms. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Our techniques can also be used to identify necessary and sufficient conditions for GEQ, and to establish reductions between different notions of GEQ with unconstrained and constrained decision sets.
APA
Lee, B.W., Haghtalab, N., Jordan, M.I. & Tibshirani, R.J.. (2026). Blackwell Approachability and Gradient Equilibrium are Equivalent. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4585-4587 Available from https://proceedings.mlr.press/v336/lee26c.html.

Related Material