pith. sign in

arxiv: 2606.27315 · v1 · pith:MPRVGHZTnew · submitted 2026-06-25 · 💻 cs.LG

Blackwell Approachability and Gradient Equilibrium are Equivalent

Pith reviewed 2026-06-26 05:02 UTC · model grok-4.3

classification 💻 cs.LG
keywords gradient equilibriumBlackwell approachabilityonline optimizationregret minimizationcalibrationoracle reductionsequivalence
0
0 comments X

The pith

Gradient equilibrium is algorithmically equivalent to Blackwell approachability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any Blackwell approachability problem can be solved by making queries to a black-box gradient equilibrium oracle, with no asymptotic loss in the oracle error rate, and that the reverse reduction holds as well. This places GEQ on the same footing as regret minimization and calibration, because those frameworks are already known to be equivalent to approachability. A reader would care because the equivalence lets guarantees and algorithms developed in one setting transfer directly to the others. The work also supplies necessary and sufficient conditions for GEQ and shows how to reduce between its constrained and unconstrained variants.

Core claim

The central claim is that GEQ and Blackwell approachability are equivalent in the algorithmic sense: 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. The reductions are efficient and also allow refined guarantees such as optimism and strong adaptivity to be transferred from regret minimization to GEQ. Necessary and sufficient conditions for GEQ are identified, and reductions between different notions of GEQ with unconstrained and constrained decision sets are established.

What carries the argument

Efficient black-box oracle reductions between gradient equilibrium problems and Blackwell approachability problems that preserve error rates asymptotically.

If this is right

  • Refined guarantees such as optimism and strong adaptivity transfer from regret minimization to GEQ.
  • GEQ is equivalent to regret minimization and calibration via the known chain of equivalences.
  • Necessary and sufficient conditions for achieving GEQ are identified.
  • Reductions exist between GEQ variants defined with unconstrained and constrained decision sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equivalence suggests GEQ can be used in repeated-game settings where vector-payoff approachability has previously been applied.
  • Similar oracle reductions might connect GEQ to other online optimization notions not covered by the current equivalences.
  • Because GEQ abstracts online conformal prediction, the new reductions may produce approachability-style algorithms for conformal prediction.

Load-bearing premise

The black-box oracle model and problem definitions allow efficient reductions that incur no asymptotic loss in error rate.

What would settle it

A concrete Blackwell approachability instance for which every reduction through a GEQ oracle produces an error rate that exceeds the original oracle error by more than a constant factor.

Figures

Figures reproduced from arXiv: 2606.27315 by Brian W. Lee, Michael I. Jordan, Nika Haghtalab, Ryan J. Tibshirani.

Figure 1
Figure 1. Figure 1: Our main contributions are black-box oracle reductions that establish an equivalence between [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that Gradient Equilibrium (GEQ) is algorithmically equivalent to Blackwell approachability: any approachability instance can be solved via black-box queries to a GEQ oracle with no asymptotic loss in error rate, and vice versa. Combined with known equivalences to regret minimization and calibration, this places GEQ in the same equivalence class. The work also gives necessary and sufficient conditions for GEQ and reductions between its constrained and unconstrained variants, allowing transfer of refined properties such as optimism and strong adaptivity.

Significance. If the reductions hold with the stated error-rate preservation, the result unifies GEQ with the core frameworks of online learning and enables systematic transfer of algorithmic guarantees across them. The identification of necessary/sufficient conditions for GEQ is a useful byproduct.

major comments (2)
  1. [reduction from approachability to GEQ (main theorem)] The central reduction (approachability to GEQ oracle) must be checked for hidden factors: the abstract asserts 'no asymptotic loss,' but if the construction in the main reduction theorem introduces a multiplicative term depending on the diameter of the decision set or the Lipschitz constant of the payoff function, the claim fails for general instances. Please exhibit the exact error-rate relation (e.g., the inequality relating the GEQ error to the approachability distance after T steps).
  2. [reduction from GEQ to approachability] The converse reduction (GEQ to approachability) similarly requires explicit verification that the black-box model and the necessary/sufficient conditions stated for GEQ allow error transfer without additive or multiplicative overhead that grows with problem parameters. If the constrained vs. unconstrained cases introduce different constants, this must be stated precisely.
minor comments (2)
  1. [Preliminaries] Clarify the precise definition of the GEQ oracle (query model, feedback, and error measure) in the preliminaries so that the black-box reductions are unambiguous.
  2. [Discussion of implications] The statement that the reductions 'can be used to transfer refined guarantees' would benefit from a short corollary or example showing how optimism or strong adaptivity carries over.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and for highlighting the need to verify the precise error-rate relations in our reductions. We confirm that both reductions preserve asymptotic rates as claimed in the abstract, with all multiplicative and additive factors independent of the time horizon T. We address each major comment below.

read point-by-point responses
  1. Referee: The central reduction (approachability to GEQ oracle) must be checked for hidden factors: the abstract asserts 'no asymptotic loss,' but if the construction in the main reduction theorem introduces a multiplicative term depending on the diameter of the decision set or the Lipschitz constant of the payoff function, the claim fails for general instances. Please exhibit the exact error-rate relation (e.g., the inequality relating the GEQ error to the approachability distance after T steps).

    Authors: Theorem 3.1 gives the exact relation: if a GEQ oracle achieves error ε_T, the resulting approachability distance satisfies d_T ≤ K · ε_T, where the constant K depends only on the diameter of the decision set and the Lipschitz constant of the payoff function (both instance parameters independent of T). The black-box construction in the proof introduces no additional T-dependent factors, so any rate achieved by the GEQ oracle transfers directly. This is already stated and proved in Section 3; the abstract's claim of no asymptotic loss refers precisely to this T-independent scaling. revision: no

  2. Referee: The converse reduction (GEQ to approachability) similarly requires explicit verification that the black-box model and the necessary/sufficient conditions stated for GEQ allow error transfer without additive or multiplicative overhead that grows with problem parameters. If the constrained vs. unconstrained cases introduce different constants, this must be stated precisely.

    Authors: Theorem 4.2 establishes the converse: the GEQ error is bounded by the approachability distance plus an additive O(1/T) term that vanishes asymptotically. The necessary and sufficient conditions (Proposition 4.1) are used to ensure the black-box reduction incurs no parameter-dependent overhead beyond instance constants. Section 4.3 explicitly compares the constants for the constrained and unconstrained variants, showing they differ by a fixed factor depending only on the geometry of the constraint set. These relations are already exhibited in the stated theorems. revision: no

Circularity Check

0 steps flagged

No circularity: equivalence shown via explicit bidirectional reductions

full rationale

The paper establishes equivalence between GEQ and Blackwell approachability by constructing algorithmic reductions in both directions that use black-box oracle queries while preserving asymptotic error rates exactly. These reductions are independent of the target result, rely on the stated problem definitions and oracle models, and build on (but do not reduce to) previously known equivalences with regret and calibration. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain; the central claim is a pair of explicit constructions rather than a tautology or imported uniqueness theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities; full paper required for audit.

pith-pipeline@v0.9.1-grok · 5736 in / 1072 out tokens · 37514 ms · 2026-06-26T05:02:42.383635+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    Panprediction: Optimal predictions for any downstream task and loss.arXiv preprint arXiv:2510.27638,

    Sivaraman Balakrishnan, Nika Haghtalab, Daniel Hsu, Brian Lee, and Eric Zhao. Panprediction: Optimal predictions for any downstream task and loss.arXiv preprint arXiv:2510.27638,

  2. [2]

    Tibshirani

    Tiffany Ding, Isaac Gibbs, and Ryan J. Tibshirani. Calibrated multi-level quantile forecasting.arXiv preprint arXiv:2512.23671,

  3. [3]

    Multicalibration: Calibration for the (Computationally-identifiable) masses

    Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (Computationally-identifiable) masses. In Jennifer Dy and Andreas Krause, editors,Proceedings of the 35th International Conference on Machine Learning, volume 80 ofProceedings of Machine Learning Research, pages 1939–1948. PMLR,

  4. [4]

    Princewill Okoroafor, Robert Kleinberg, and Michael P. Kim. Near-optimal algorithms for omniprediction. arXiv preprint arXiv:2501.17205,

  5. [5]

    Approachability, Regret and Calibration; implications and equivalences

    Vianney Perchet. Approachability, regret and calibration; implications and equivalences.arXiv preprint arXiv:1301.2663,

  6. [6]

    regret minimization

    Hence, we conclude that 𝑑 ¯𝑓𝑇 , 𝑆 2 ≤ 4𝐿 2 𝑇 + 8𝐿 2𝑚 𝑇 , 25 which implies that 𝑑 ¯𝑓𝑇 , 𝑆 ≤𝐶 𝑚 · 2𝐿√ 𝑇 with𝐶 𝑚 = √ 1+2𝑚. □ A.2 Regret Minimization Given a decision setΘ⊆R 𝑑, the regret of a sequence of decisions{𝜃 𝑡 }𝑡≥1 , with𝜃 𝑡 ∈Θfor all𝑡≥1, on a sequence of losses{ℓ 𝑡 }𝑡≥1 is measured as sup𝜃∈Θ 1 𝑇 Í𝑇 𝑡=1 ℓ𝑡 (𝜃 𝑡 ) −ℓ 𝑡 (𝜃). A sufficient condition for ...

  7. [7]

    For this problem, at each time step𝑡∈ [𝑇],RMtakes as input the history𝑔 1,

    Fix any𝑇≥1. For this problem, at each time step𝑡∈ [𝑇],RMtakes as input the history𝑔 1, . . . , 𝑔𝑡−1 and returns a decision𝜃 𝑡 ∈Θ, with the following guarantee. For any sequence of loss vectors𝑔 1, . . . , 𝑔𝑇, max 𝜃∈Θ 1 𝑇 𝑇∑︁ 𝑡=1 ⟨𝑔𝑡 , 𝜃𝑡 −𝜃⟩ ≤ RMErr(𝐵, 𝐿, 𝑇) 𝑇 , whereRMErr(𝐵, 𝐿, 𝑇)=𝑜(𝑇)is the oracle’s promised rate. Going beyond worst-case regret, recent ...

  8. [8]

    Fix any𝑇≥1. Let𝑚 1, . . . , 𝑚𝑇 be a sequence of loss vector predictions with ∥𝑚 𝑡 ∥2 ≤𝐿for all𝑡∈ [𝑇]. Then there exists an algorithm that uses𝑚 1, . . . , 𝑚𝑇 to select a sequence of decisions𝜃 1, . . . , 𝜃𝑇 ∈Θsuch that, for any sequence of loss vectors𝑔 1, . . . , 𝑔𝑇 ∈ G, max 𝜃∈Θ 1 𝑇 𝑇∑︁ 𝑡=1 ⟨𝑔𝑡 , 𝜃𝑡 −𝜃⟩ ≤𝑂 ©­­ « 𝐵 √︃Í𝑇 𝑡=1 ∥𝑔 𝑡 −𝑚 𝑡 ∥2 2 𝑇 ª®® ¬ . Anothe...

  9. [9]

    Then there exists an algorithm that selects a sequence of decisions 𝜃1,

    Fix any𝑇≥1. Then there exists an algorithm that selects a sequence of decisions 𝜃1, . . . , 𝜃𝑇 ∈Θsuch that, for any sequence of loss vectors𝑔 1, . . . , 𝑔𝑇 ∈ G, max 1≤𝑡 1<𝑡2 ≤𝑇 max 𝜃∈Θ 1 𝑡2 −𝑡 1 +1 ∑︁ 𝑠∈ [𝑡1,𝑡2 ] ⟨𝑔 𝑠, 𝜃𝑠 −𝜃⟩ ≤𝑂 𝐵𝐿(1+ √︁ log(𝑡 2)) √𝑡2 −𝑡 1 +1 ! . A.3 Known Equivalences Next, we recall two reductions from Abernethy et al. (2011) that estab...

  10. [10]

    The reduction is formalized in Algorithm 8 and has the following guarantee

    For any𝑢∈𝑆 ◦, playing𝜃(𝑢)as in Equation 9 ensures that for all𝑔∈ G,⟨𝑢, 𝑓(𝜃(𝑢), 𝑔)⟩=0. The reduction is formalized in Algorithm 8 and has the following guarantee. Proposition 7((Abernethy et al., 2011)).Given a RM problem(R 𝑑,Θ,G)that satisfies Assumption 3, define the BA problem(R 𝑑+1, 𝐴, 𝐵, 𝑓 , 𝑆)as in Equation

  11. [11]

    Selecting the sequence of decisions 𝜃1,

    Fix any𝑇≥1. Selecting the sequence of decisions 𝜃1, . . . , 𝜃𝑇 ∈Θusing Algorithm 8 guarantees that, for any sequence of loss vectors𝑔 1, . . . , 𝑔𝑇 ∈ G, max 𝜃∈Θ 1 𝑇 𝑇∑︁ 𝑡=1 ⟨𝑔𝑡 , 𝜃𝑡 −𝜃⟩ ≤2𝐵· BAErr( √ 2𝐿, 𝑇) 𝑇 . Reducing BA to RMIn this direction, we are given a BA problem(R 𝑑, 𝐴, 𝐵, 𝑓 , 𝑆)that satisfies Assump- tion 1, as well as a valid halfspace oracleO...

  12. [12]

    Selecting a sequence of actions𝑎 1,

    Fix any𝑇≥1. Selecting a sequence of actions𝑎 1, . . . , 𝑎𝑇 ∈𝐴using Algorithm 9 guarantees that, for any sequence of Nature’s actions𝑏1, . . . , 𝑏𝑇 ∈𝐵, 𝑑 1 𝑇 𝑇∑︁ 𝑡=1 𝑓(𝑎 𝑡 , 𝑏𝑡 ), 𝑆 ! ≤ RMErr(1, 𝐿, 𝑇) 𝑇 . Abernethy et al. (2011) show that if(R 𝑑, 𝐴, 𝐵, 𝑓 , 𝑆)satisfies Assumption 1 but𝑆is not a cone, then the problem can be embedded into an auxiliary BA pro...