Search papers, labs, and topics across Lattice.
This paper establishes a formal equivalence between Gradient Equilibrium (GEQ) and Blackwell approachability, demonstrating that problems in Blackwell approachability can be efficiently solved using a GEQ oracle without loss in error rate. The findings clarify the relationship between GEQ and other online learning frameworks, such as regret minimization and calibration, by showing that they share foundational principles. Additionally, the authors provide necessary and sufficient conditions for GEQ and outline efficient reductions between various GEQ formulations, enhancing the understanding of this optimization framework's role in online learning.
Solving Blackwell approachability problems via Gradient Equilibrium oracles reveals a deep connection between these two seemingly distinct optimization frameworks.
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.
BAIR