Blackwell Approachability and Gradient Equilibrium are Equivalent
By Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani
"Proves algorithmic equivalence between gradient equilibrium and Blackwell approachability, enabling transfer of algorithms and connecting GEQ to regret minimization and calibration."
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.
Technical Analysis & Implementation
Detailed Technical Summary§
Core Contribution§
The paper establishes that Gradient Equilibrium (GEQ) and Blackwell approachability are algorithmically equivalent. This means any problem solvable with a Blackwell approachability oracle can be solved with a GEQ oracle (and vice versa) without asymptotic loss in error rate. This equivalence further connects GEQ to regret minimization and calibration via known reductions.
Mathematical Framework§
Gradient Equilibrium (GEQ) generalizes first-order stationarity to online optimization. At each round $t$, the decision maker selects $x_t \in \mathcal{X}$ and observes a gradient-like vector $g_t \in \mathbb{R}^d$ from an adversary. The goal is to minimize the cumulative GEQ error: $$ \text{GEQ-Err}_T = \sum_{t=1}^T \max_{y \in \mathcal{X}} \langle g_t, x_t - y \rangle $$ where $\mathcal{X}$ is a convex compact set. A GEQ oracle returns $x_t$ such that $\max_{y \in \mathcal{X}} \langle g_t, x_t - y \rangle \leq \epsilon_t$.
Blackwell approachability involves a vector-valued payoff $u_t \in \mathbb{R}^d$ chosen by the decision maker, an adversarial outcome $v_t$, and a target set $S$. The decision maker aims to ensure that the cumulative average payoff approaches $S$: $\lim_{T \to \infty} d(\frac{1}{T} \sum u_t, S) = 0$. A Blackwell oracle outputs $u_t$ such that after seeing $v_t$, the distance to $S$ shrinks.
Equivalence Proof§
The reductions are constructive:
- From Blackwell to GEQ: Given a Blackwell problem with set $S = \{0\}$ (or any convex closed set), the GEQ oracle is used to pick $x_t$ by minimizing the dot product with a certain gradient derived from the distance to $S$.
- From GEQ to Blackwell: A GEQ problem is cast as a Blackwell approachability problem with payoff $(g_t, x_t)$ and target set $\{(g, x) : \max_{y \in \mathcal{X}} \langle g, x - y \rangle \leq 0\}$.
Implementation Details§
The reductions are efficient: each reduction uses a single oracle call per round and adds only $O(1)$ computational overhead. The paper also derives necessary and sufficient conditions for GEQ, characterizable via convex analysis, and shows how to handle unconstrained vs. constrained decision sets.
Code Illustration§
Below is pseudocode for the reduction from Blackwell approachability to GEQ:
import numpy as np
def blackwell_via_geq(blackwell_instance, geq_oracle, T):
"""
blackwell_instance: contains set S (target), action set U, and update rule
geq_oracle: function that takes gradient and returns x in convex set X
"""
x_0 = np.zeros(d)
for t in range(1, T+1):
# 1. Receive current state (e.g., previous payoff)
# 2. Compute gradient for GEQ based on distance to S
grad = blackwell_instance.compute_gradient()
# 3. Query GEQ oracle
x_t = geq_oracle(grad)
# 4. Map x_t to action u_t (e.g., projection)
u_t = blackwell_instance.map_to_action(x_t)
# 5. Observe adversary's v_t
v_t = blackwell_instance.adversarial_move()
# 6. Update internal state
blackwell_instance.update(u_t, v_t)
return blackwell_instance.get_average_payoff()Significance§
This equivalence unifies several frameworks: gradient equilibrium, Blackwell approachability, regret minimization, and calibration. It allows transferring advances from regret minimization (e.g., optimistic algorithms, adaptive learning rates) to GEQ. The paper thus clarifies the theoretical landscape of online optimization beyond regret.