Blackwell Approachability and Gradient Equilibrium are Equivalent
2026-06-25 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study Gradient Equilibrium (GEQ), an online optimization method recently introduced to generalize certain problem types. They prove that GEQ is algorithmically the same as Blackwell approachability, a known framework in online learning. This connection shows that GEQ is also equivalent to other established methods like regret minimization and calibration. Their work includes efficient techniques to transfer improvements from regret minimization to GEQ and clarifies when GEQ applies to different decision settings.
Gradient EquilibriumBlackwell ApproachabilityOnline OptimizationRegret MinimizationCalibrationFirst-Order StationarityConstrained Decision SetsAdaptivityOptimism
Authors
Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani
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.