ArXiv

Blackwell Approachability and Gradient Equilibrium are Equivalent

2026-06-25 · 17:29 UTC ·Brian W. Lee, Nika Haghtalab, Michael I. Jordan... ·1 min read
Authors
Brian W. Lee, Nika Haghtalab, Michael I. Jordan...
Categories
cs.LG
arXiv
https://arxiv.org/abs/2606.27315v1
PDF
https://arxiv.org/pdf/2606.27315v1

Brief

Gradient equilibrium (GEQ) is shown equivalent to Blackwell approachability: the authors provide mutual, efficient reductions that use a GEQ black-box to solve approachability problems (and vice versa) with no asymptotic loss in error. Combined with known approachability–regret–calibration equivalences, GEQ is thus algorithmically equivalent to regret minimization and calibration; they also state necessary/sufficient conditions and reductions for constrained vs. unconstrained GEQ.

Why it matters

Proves algorithmic equivalence between Gradient Equilibrium (GEQ) and Blackwell approachability: each can be solved using a black-box oracle for the other with no asymptotic loss in the oracle's error rate, and the reductions are efficient.

Key details

  • By combining this with known approachability–regret–calibration equivalences, GEQ is therefore algorithmically equivalent to regret minimization and calibration; the reductions preserve refined guarantees such as optimism and strong adaptivity.
  • Gives necessary and sufficient conditions for GEQ and reductions between unconstrained and constrained decision sets; paper (Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani) is 30 pages, on arXiv (2606.27315v1) and accepted to COLT 2026 (posted 2026-06-25).
Source evidence

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, 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 that GEQ is equivalent to these frameworks, as well. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Along the way, we also identify necessary and sufficient conditions for GEQ, and establish reductions between different notions of GEQ with unconstrained and constrained decision sets.

Comment: 30 pages, 1 figure, accepted for presentation at COLT 2026