---
title: "Equivalence between Blackwell Approachability and Gradient Equilibrium"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2606.27315v1"
permalink: "https://feed.astralor.com/items/itm_a460bc7beaee6fd7867f6851"
published: "2026-06-25T17:29:48.000Z"
score: 53
channel: "ai"
tags: ["Blackwell Approximability","Optimization Theory","Online Learning","Gradient Equilibrium"]
---

# Equivalence between Blackwell Approachability and Gradient Equilibrium

## At a glance

This paper establishes the algorithmic equivalence between Gradient Equilibrium (GEQ) and Blackwell approachability. GEQ is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization and abstracts problems like online conformal prediction. By constructing bidirectional reductions, the paper reveals deep connections between GEQ and classical online learning frameworks such as regret minimization and calibration. It also identifies necessary and sufficient conditions for GEQ and provides reductions between different notions of GEQ under unconstrained and constrained decision sets. This work provides a key piece for unifying online learning theory.

## Key points

- Gradient Equilibrium (GEQ) is algorithmically equivalent to Blackwell approachability, with bidirectional reductions preserving asymptotic error rates.
- Through known equivalences among approachability, regret minimization, and calibration, GEQ is also equivalent to these frameworks.
- Necessary and sufficient conditions for GEQ are identified, and reductions between different GEQ notions under unconstrained and constrained decision sets are established.
- The reductions are efficient and can transfer refined guarantees such as optimism and strong adaptivity from regret minimization to GEQ.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_a460bc7beaee6fd7867f6851