🤖 machine learning

Blackwell Approachability and Gradient Equilibrium are Equivalent

This paper establishes that Gradient Equilibrium (GEQ) is algorithmically equivalent to Blackwell approachability, thereby unifying GEQ with the broader online learning frameworks of regret minimization and calibration while enabling the transfer of advanced guarantees like strong adaptivity.

Original authors: Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani

Published 2026-06-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Two Different Games, One Winning Strategy

Imagine you are playing a series of games against a tricky opponent (let's call them "Nature"). In the world of online learning, researchers have developed different ways to measure if you are playing well.

For a long time, the gold standard was Regret Minimization. Think of this as playing a game where you try to do almost as well as the single best strategy you could have picked if you had known the future. It's like saying, "I didn't win the lottery, but I did almost as well as the person who bought the winning ticket."

Recently, a new framework called Gradient Equilibrium (GEQ) was introduced. This is a different way of playing. Instead of trying to match a future winner, the goal is to keep your "average momentum" balanced. Imagine you are walking through a field of wind. If the wind pushes you left, you take a step right. If it pushes you right, you step left. The goal of GEQ is to ensure that, over a long time, you aren't drifting in any specific direction. You are perfectly balanced.

The Problem: For a while, experts weren't sure how these two games related. They knew they were different. In fact, you could be great at balancing the wind (GEQ) but terrible at matching the future winner (Regret), and vice versa. It was a mystery: Are these just two separate tools, or are they secretly the same thing?

The Discovery: This paper proves that they are actually the same thing.

The authors show that if you have a tool (an algorithm) that can solve the "Balancing the Wind" game, you can instantly turn it into a tool that solves the "Matching the Future Winner" game, and vice versa. They are mathematically equivalent. If you can do one, you can do the other with no loss in performance.

The Core Concepts Explained

1. The "Wind Balancing" Game (Gradient Equilibrium)

Imagine you are a tightrope walker. Every second, a gust of wind (a "gradient") hits you.

The Goal: You want to make sure that if you average out all the wind gusts over the day, they cancel each other out. You end up standing still.
The Catch: Sometimes the wind is chaotic. The paper shows that if the wind has a certain "restoring" property (meaning if you drift too far away, the wind naturally pushes you back toward the center), you can always find a way to balance it.

2. The "Target Hitting" Game (Blackwell Approachability)

This is an older, classic game. Imagine you are throwing darts at a board, but the board is a moving target (like a specific shape or a single point in the center).

The Goal: You want your average throw to land inside that target shape.
The Magic: A famous mathematician named Blackwell figured out that if you can always throw a dart that lands in a specific "safe zone" relative to where you are now, you can eventually hit the target.

The Paper's Insight: The authors realized that "Balancing the Wind" is actually just a special version of "Hitting the Target."

In the wind game, your "target" is the center point (zero wind).
The "wind gusts" are the vectors you need to balance.
The paper proves that any strategy that can hit a target can be used to balance the wind, and any strategy that balances the wind can be used to hit a target.

3. The "Translator" (The Reductions)

The paper provides a "translator" or a recipe book.

Recipe A: If you have a robot that is good at hitting targets, here is how you program it to balance the wind.
Recipe B: If you have a robot that is good at balancing the wind, here is how you program it to hit targets.

Because of this translation, the authors show that GEQ is just as powerful as the old-school Regret Minimization. They are two different languages describing the same underlying ability to learn and adapt.

Why Does This Matter? (The Practical Magic)

The paper doesn't just say "they are the same"; it shows how to use this to build better algorithms.

1. Borrowing Superpowers:
Because they are equivalent, you can take the "superpowers" developed for the old Regret game and give them to the new GEQ game.

Example: Some Regret algorithms are "optimistic." They guess what the wind will do next and adjust early. If the guess is right, they do amazing. The paper shows you can take this "optimism" and plug it into the GEQ framework, giving GEQ algorithms a new superpower they didn't have before.
Example: Some Regret algorithms are "strongly adaptive." They can adjust their speed if the game gets easier or harder in the middle of the day. The paper shows how to give this same flexibility to GEQ.

2. Simplifying the Hard Stuff:
Sometimes, solving a problem with rules (constraints) is hard. The paper shows a clever trick: you can turn a "constrained" problem (where you have rules to follow) into an "unconstrained" problem (where you have total freedom) by adding a little bit of "imaginary force" to the math.

The Result: This means we don't need to invent a new, complex algorithm for every new rule we add. We can just use the simple, unconstrained algorithms we already have, and the math handles the rest.

3. No More Tuning Knobs:
In the old Regret world, algorithms often need you to turn a "knob" (a step size) based on how long the game will last or how strong the wind is. If you guess the knob wrong, the algorithm fails.

The paper shows that by using the GEQ approach, you can build Regret algorithms that don't need any knobs at all. You can just set the knob to "1" and forget it. It works perfectly regardless of the game's length or difficulty.

Summary

Think of this paper as discovering that two different maps (Gradient Equilibrium and Blackwell Approachability) lead to the exact same destination. Even though the terrain looks different on the maps, the authors built a bridge between them.

This bridge allows us to:

Take the best tools from the old "Regret" world and use them in the new "Gradient" world.
Take the simple, robust tools from the "Gradient" world and use them to solve the complex "Regret" problems without needing to fiddle with settings.

In short: They are different names for the same superpower, and now we can use that superpower more effectively than ever before.

Technical Summary: Blackwell Approachability and Gradient Equilibrium are Equivalent

1. Problem Statement and Context

The paper addresses the theoretical positioning of Gradient Equilibrium (GEQ), a recently introduced online optimization framework (Angelopoulos et al., 2025), within the broader landscape of online learning. GEQ generalizes the concept of first-order stationarity from offline optimization to the online setting. Specifically, a sequence of decisions $\{\theta_t\}$ achieves GEQ if the time-average of the subgradients of the loss functions converges to zero:
$\left\| \frac{1}{T} \sum_{t=1}^T g_t(\theta_t) \right\|_2 \to 0 \quad \text{as } T \to \infty.$

While GEQ shares structural similarities with established frameworks like Regret Minimization (RM) and Blackwell Approachability (BA), prior work established that GEQ error and regret are incomparable objectives. A sequence can achieve GEQ without vanishing regret, and vice versa. Furthermore, the conditions under which GEQ is achievable (e.g., restorativity of vector fields) differ from those required for regret minimization (e.g., convexity). Consequently, the precise algorithmic relationship between GEQ and the broader online learning ecosystem remained unclear.

The central question this paper investigates is whether GEQ is algorithmically equivalent to Blackwell Approachability, and by extension, to regret minimization and calibration, despite their semantic differences.

2. Methodology

The authors establish black-box oracle reductions between GEQ and Blackwell Approachability. These reductions demonstrate that an algorithm for one problem can be converted into an algorithm for the other with no asymptotic loss in the error rate.

2.1 Reducing GEQ to Blackwell Approachability

The authors interpret a GEQ problem as a specific instance of a Blackwell Approachability problem:

Action Sets: The learner's action set is the decision space $\Theta = \mathbb{R}^d$ , and Nature's action set is the class of vector fields $\mathcal{G}$ .
Payoff Function: The payoff is defined as $f(\theta, g) = -g(\theta)$ .
Target Set: The target set is the singleton origin $\{0\}$ .

Under this mapping, achieving GEQ is equivalent to driving the time-average of payoffs to the origin. The authors prove that the restorativity condition (a sufficient condition for GEQ) implies Blackwell's condition (the necessary and sufficient condition for approachability).

Challenge: Constructing a valid halfspace oracle for this reduction requires knowledge of the restorativity horizon $h$ , which is not available to the learner.
Solution: The authors propose an approximate halfspace oracle that scales the approach direction by a growing function $\alpha(t)$ . This ensures that the restorativity condition holds for all but a bounded number of rounds (specifically $\lceil \alpha^{-1}(h) \rceil$ ). By utilizing a robust BA oracle (which tolerates a bounded number of errors), the reduction preserves the asymptotic error rate of the underlying BA algorithm.

2.2 Reducing Blackwell Approachability to GEQ

The reverse reduction converts a BA algorithm into a GEQ algorithm.

Conic Case: First, the authors consider the case where the target set $S$ is a cone. They construct a GEQ problem where the decision set is the polar cone $S^\circ$ and the vector fields are derived from the BA payoff function and a halfspace oracle. The GEQ oracle provides approach directions, which are mapped to actions via the halfspace oracle.
General Case (Constrained to Unconstrained): A key technical contribution is a reduction from GEQ with constrained decision sets ( $\Theta \subseteq \mathbb{R}^d$ ) to GEQ with unconstrained sets ( $\Theta = \mathbb{R}^d$ ). The authors introduce a modified vector field that includes a scaled projection residual term. This term ensures the new vector field is restorative and that achieving unconstrained GEQ on the modified field implies achieving constrained GEQ on the original field.
General Target Sets: For non-conic target sets, the authors employ a "conic lifting" argument (following Abernethy et al., 2011) to transform the BA problem into a higher-dimensional conic approachability problem, which can then be solved via the unconstrained GEQ oracle.

3. Key Contributions and Results

3.1 Algorithmic Equivalence

The primary result is the establishment of algorithmic equivalence between GEQ and Blackwell Approachability.

Theorem 3: Any GEQ problem satisfying restorativity can be solved using a robust BA oracle with an error rate of $O(\text{BAErr}(T)/T)$ .
Theorem 9: Any BA problem (with a conic target set) can be solved using an unconstrained GEQ oracle with an error rate of $O(\text{GEQErr}(T)/T)$ .
Corollary: Combined with known reductions between BA, RM, and calibration, this implies that GEQ is algorithmically equivalent to Regret Minimization and Calibration.

3.2 Necessary and Sufficient Conditions

The paper identifies Blackwell's condition as the necessary and sufficient condition for GEQ to be achievable. Previously, only the sufficient condition of restorativity was known. The authors clarify that while restorativity is a practical condition for designing tractable algorithms (like Projected OGD), Blackwell's condition provides the exact characterization of solvability.

3.3 Transfer of Refined Guarantees

The reductions allow for the transfer of refined performance guarantees from one framework to another:

Optimism: By plugging optimistic regret minimization algorithms (which leverage predictable loss sequences) into the GEQ reduction, the authors derive GEQ algorithms with optimistic error bounds that scale with prediction error rather than worst-case norms.
Strong Adaptivity: Similarly, strongly adaptive regret algorithms (which perform well on arbitrary sub-intervals) can be converted into GEQ algorithms with strongly adaptive error bounds.
Parameter-Free Regret Minimization: Conversely, by plugging simple GEQ algorithms (like Online Gradient Descent with a constant step size $\eta=1$ ) into the BA reduction, the authors derive regret minimization algorithms that do not require tuning step sizes and do not need prior knowledge of the loss vector norm bound $L$ or the time horizon $T$ .

4. Significance and Claims

The paper claims that while GEQ offers a semantically different guarantee (absolute convergence of gradients vs. relative performance against a competitor), it is equally powerful as classical frameworks in terms of algorithmic capability.

Unification: The work unifies the understanding of online learning frameworks, showing that GEQ, BA, RM, and calibration are different perspectives on the same underlying algorithmic structure.
Practical Implications: The reductions provide a "design path" for new algorithms. Researchers can leverage existing, highly optimized algorithms from one domain (e.g., the vast literature on regret minimization) to solve problems in another (e.g., online conformal prediction or gradient equilibrium) without reinventing the wheel.
Robustness: The results hold even when the decision sets are constrained or the target sets are non-conic, provided appropriate lifting or projection techniques are used.

The authors explicitly state that their reductions are efficient and black-box, meaning they do not require internal modifications of the underlying oracles, only the ability to query them. This modularity facilitates the immediate application of these theoretical insights to practical algorithm design.