Pith. sign in

REVIEW 1 major objections 5 minor 15 references

Blackwell's Approachability with Approximation Algorithms

T0 review · 1 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A Blackwell player armed only with approximation oracles can still force average loss into the downward closure of the scaled target at the optimal rate.

desk verdict First general reduction of Blackwell approachability to approximation algorithms, with a repairable but real gap in Lemma 10's proof. read the letter →

arxiv 2502.03919 v2 pith:5FJSTZGZ submitted 2025-02-06 math.OC cs.LG

Dan Garber , Mhna Massalha This is my paper · ORCID
classification math.OCcs.LG MSC 91A2090C4768W25
keywords Blackwellapproachabilityapproximationoracleonlineconvexoptimizationinfeasiblesaddle-pointdownwardclosureregretminimizationNP-hardactionsetsmonotonepreferences
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks what a player can guarantee in Blackwell's repeated vector-valued game when the action sets can only be optimized approximately, as happens when actions are solutions to NP-hard problems. The central answer is a scaling law: if the original target set $S$ is approachable and the player's preferences are monotone, then with approximation ratios $\alpha_{\mathcal X} \ge 1$ for the player's set and $1 \ge \alpha_{\mathcal Y} > 0$ for the adversary's set, the downward closure of the scaled target $\alpha_{\mathcal X}\alpha_{\mathcal Y}^{-1}S$ is efficiently approachable at the optimal $O(1/\sqrt{T})$ rate. The price of approximate computation is therefore not the convergence rate but the target itself: the player can steer average loss only into the set of points coordinatewise no better than $\alpha_{\mathcal X}\alpha_{\mathcal Y}^{-1}$ times some point in $S$. When only one side has an approximation oracle, simpler algorithms achieve the same rate with fewer oracle calls, and this matters because it extends a classical guarantee to settings where exact optimization over an action set is computationally infeasible, provided all actions and losses are nonnegative.

What carries the argument

The load-bearing machinery is the approximate infeasible saddle-point oracle, defined by the paper: given a direction $w$ on the unit ball, it returns an infeasible point $x$ whose guaranteed loss against every adversary action is at most $\epsilon$ above the minimax value of a modified Blackwell instance, together with a feasible point $s \le x$. The meta-algorithm runs an online convex optimization algorithm on the unit ball, queries this oracle each round, plays the feasible point, and uses the online regret bound to show the infeasible average approaches the modified target; monotonicity then makes the feasible average at least as good. The oracle is implemented by combining an extended approximation oracle for the nonnegative set with online-gradient-based primal-dual iterations and, for the two-sided case, a Frank-Wolfe infeasible projection onto $\alpha_{\mathcal X}\mathcal X$. Also central is the scaling choice of the modified instance: when both sets are approximate, it is $(\alpha_{\mathcal X}\mathcal X,\ \alpha_{\mathcal Y}^{-1}(\mathcal Y - B_+(R_{\mathcal Y})),\ \ell,\ \alpha_{\mathcal X}\alpha_{\mathcal Y}^{-1}(S - B_+(\widetilde R)))$, which is shown to remain approachable.

What would settle it

Run the algorithm on the vertex-cover game described in the introduction, with the standard 2-approximation oracle for the player and exact access for the adversary, and fix any adversarial sequence: the theorem predicts the average loss's distance to $(2S)_{\downarrow}$ decays like $O(1/\sqrt{T})$, so a simulation showing the distance leveling off above zero for large $T$ would refute the claim. More directly, any approachable Blackwell instance satisfying Assumption 1 in which the feasible average loss fails to dominate the infeasible average, i.e., where $\ell(s_t,y_t) \le \ell(x_t,y_t)$ is violated despite $s_t \le x_t$, would sever the step that connects the oracle output to the player's actual payoff.

Watch

Extended reading notes

Core claim

The paper's core claim is that Blackwell approachability is robust to replacing exact optimization over the action sets by approximation oracles, provided the game is monotone. Formally, for any Blackwell instance $(\mathcal X, \mathcal Y, \ell, S)$ satisfying Assumption 1 (namely $\mathcal X \subset \mathbb R_+^n$, $\mathcal Y \subset \mathbb R_+^m$, and $\ell$ nonnegative on nonnegative actions), if $S$ is approachable and $\mathcal X$ is reachable through an $\alpha_{\mathcal X}$-approximation oracle while $\mathcal Y$ is reachable through an $\alpha_{\mathcal Y}$-approximation oracle, then there is an algorithm whose average feasible loss converges in Euclidean distance to $(\alpha_{\mathcal X}\alpha_{\mathcal Y}^{-1}S)_{\downarrow}$ at rate $O(1/\sqrt{T})$. The algorithm is built from an online-convex-optimization meta-procedure that plays an infeasible point $x_t$, whose average approaches the scaled target, together with a feasible point $s_t \le x_t$; monotonicity transfers the guarantee from the infeasible average to the feasible one. The same machinery yields the one-sided results $(\alpha_{\mathcal X}S)_{\downarrow}$ and $(\alpha_{\mathcal Y}^{-1}S)_{\downarrow}$, with $O(T^2)$ oracle calls, and the two-sided result uses $O(T^3)$ calls to the $\mathcal X$-oracle and $O(T^2)$ calls to the $\mathcal Y$-oracle.

Load-bearing premise

The load-bearing premise is that the action sets and every coordinate of the loss function are nonnegative: the argument transfers the oracle's guarantee from an infeasible play $x_t$ to the actual feasible play $s_t \le x_t$ through the inequality $\ell(s_t,y_t) \le \ell(x_t,y_t)$, which holds only because losses are nonnegative on nonnegative actions.

Editorial extensions

If this is right

  • In monotone Blackwell instances, an NP-hard player action set does not destroy approachability: with an $\alpha_{\mathcal X}$-approximation oracle the player efficiently approaches $(\alpha_{\mathcal X}S)_{\downarrow}$ at rate $O(1/\sqrt{T})$ using $O(T^2)$ oracle calls.
  • If only the adversary's set is approximated with ratio $\alpha_{\mathcal Y}$, the player efficiently approaches $(\alpha_{\mathcal Y}^{-1}S)_{\downarrow}$ at the same rate and again with $O(T^2)$ oracle calls.
  • If both sets are approximated, the efficiently approachable target becomes the downward closure of $\alpha_{\mathcal X}\alpha_{\mathcal Y}^{-1}S$, with $O(T^3)$ calls to the $\mathcal X$-oracle and $O(T^2)$ calls to the $\mathcal Y$-oracle.
  • Because the convergence rate remains $O(1/\sqrt{T})$, the approximation oracles do not degrade the speed of approachability; they only replace the target set by a scaled, coordinatewise-worse one.
  • When the target set $S$ is itself downward closed, the result directly gives efficient approachability of the scaled set $\alpha_{\mathcal X}\alpha_{\mathcal Y}^{-1}S$ rather than merely its downward closure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof's domination step $\bar\ell_{s,T} \le \bar\ell_{x,T}$ relies on nonnegativity of all loss coordinates; an extension to mixed-sign losses would likely need a shifted or otherwise modified target rather than a purely downward-closed scaled set, and that is a natural testbed for the boundary of the result.
  • The infeasible saddle-point oracle is a general reduction device: any two feasible sets equipped with approximation oracles can be plugged into the meta-algorithm, suggesting the technique may apply beyond NP-hard solution families to any structured nonnegative feasible set where exact optimization is expensive.
  • The oracle counts, $O(T^3)$ for $\mathcal X$ and $O(T^2)$ for $\mathcal Y$, are not symmetric, and the paper notes the two sides could be swapped; this raises an open slack for designing more oracle-efficient variants that balance the computational load between the two players.
  • In a monotone game where the target set is downward closed, the result effectively says approximation algorithms lose nothing in convergence speed and only shift the guarantee by the known approximation ratios, which could make Blackwell approachability more attractive as a template for online games with combinatorial action sets.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. This paper studies Blackwell's approachability in settings where the player's and/or adversary's action sets are accessible only through approximation oracles with ratios α_X ≥ 1 and 1 ≥ α_Y > 0. Under Assumption 1 (nonnegative action sets and nonnegative bilinear losses, compactness, and approachability of S), the authors propose approaching the downward closure of the scaled target set α_X α_Y^{-1} S. They introduce an "infeasible saddle-point oracle" that returns an infeasible point x whose value against Y is at least as good as a min-max point of a modified instance, together with a feasible point s ≤ x. Using reductions from approachability to online convex optimization (following Shimkin [13]) and the extended approximation oracle of Kakade-Kalai-Ligett [10], they prove that downward-closed scaled targets are approachable at rate O(1/√T), with O(T^2) oracle calls in the one-sided cases and O(T^3) and O(T^2) calls in the two-sided case. The main results are stated as Theorems 5, 6, and 7, with the general statement in Theorem 2.

Significance. If the results are correct, this is a meaningful extension of Blackwell's theory to computationally constrained settings, e.g., games over vertex covers or other NP-hard feasible sets. The paper gives explicit algorithms and finite-time oracle complexity bounds. The proof strategy—combining the OCO-based approachability reduction with infeasible saddle-point oracles and extended approximation oracles—is novel and well-structured. The central claim is not circular: it is derived from the stated building blocks, and the dependence on the monotone-preference assumption is explicit. The main weakness is the gap in the proof of Lemma 10, which is load-bearing for Theorems 6 and 7 but is repairable by a direct Cauchy-Schwarz bound.

major comments (1)
  1. [Appendix B, Lemma 10] The proof of Lemma 10 contains an invalid inequality. After Eq. (20), the paper claims ⟨w⁻, ℓ(x_w, b)⟩ ≥ -∥w⁻∥⟨ŵ⁻, ℓ(x_w, b)⟩. This fails when ⟨ŵ⁻, ℓ(x_w, b)⟩ < 0, because then the right-hand side is positive while the left-hand side is negative. Since this bound is used to derive the crucial lower bound -∥w⁻∥∥ℓ∥R_X R, the written proof of Lemma 10 does not establish the lemma. Lemma 10 is invoked in Theorems 6 and 7 to prove approachability of the modified instances, so this is a load-bearing gap. The gap is repairable: using the nonnegativity of ℓ, ⟨w, ℓ(x_w, b)⟩ ≥ ⟨w⁻, ℓ(x_w, b)⟩, and by Cauchy-Schwarz, ⟨w⁻, ℓ(x_w, b)⟩ ≥ -∥w⁻∥∥ℓ(x_w, b)∥ ≥ -∥w⁻∥∥ℓ∥∥x_w∥∥b∥ ≥ -∥w⁻∥∥ℓ∥R_X R. This yields exactly the needed bound. Please revise the proof accordingly.
minor comments (5)
  1. [Theorems 5, 6, and 7] The displayed rate bounds such as "d(ℓ̄_{s,T}, (α_X S)↓) ≤ 6G1 + 3/(2√T)" are missing parentheses; they should read (6G1+3)/(2√T), (6G3+3)/(2√T), and (3G5+1)/√T respectively.
  2. [Appendix B, Lemma 10] There are two copy-paste typos in the proof: "Denote ˜x = αX xw ∈ αX X" should be "Let xw ∈ X" (there is no αX in this lemma), and "let y = ˜y − b such that b ∈ B+(˜R)" should use b ∈ B+(R), since the perturbation in Ỹ has radius R, not R̃.
  3. [Theorem 6] The proof says "By Applying Lemma 3 with our choice of N(T)"; it should reference Lemma 4, which is the analogue of Lemma 3 for the adversary-side oracle.
  4. [Lemma 4] The line "= αY/αY min_{x∈X} max_{y∈α_Y^{-1}(Y−B_+(R_Y))} g(x, y)" contains a superfluous αY/αY and an ambiguous re-indexing; rewriting the scaling step would improve clarity.
  5. [Assumption 1 and Section 4] The nonnegativity of ℓ on R^n_+ × R^m_+ is essential to the monotonicity argument that s_t ≤ x_t implies ℓ(s_t, y_t) ≤ ℓ(x_t, y_t). A short remark stating that the downward-closure guarantee would not follow from the present proof if this assumption were dropped would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the scaled-downward-closure theorems are derived from Blackwell's condition via oracle constructions, not assumed as inputs.

full rationale

The derivation chain does not reduce to its own inputs. The paper's inputs are Assumption 1 plus the assumption that S is approachable (Blackwell instance). Theorems 5–7 then construct infeasible saddle-point oracles and apply the OCO-based meta-algorithm (Algorithm 1/Theorem 4). The only use of the assumed approachability of S is through Blackwell's theorem to certify approachability of the modified instances (Lemmas 9 and 10), so the conclusion (αX S)↓, (αY^{-1}S)↓, or (αXαY^{-1}S)↓ is not inserted as an assumption. The extended approximation oracle (Lemma 1) is cited from [10] and [6], the latter a self-citation, but it is a parameter-free mathematical building block whose stated guarantees are used, and the needed OGDWOF regret bound is reproved in Appendix C; hence it is independent support rather than a load-bearing self-citation. No fitted parameter is renamed as a prediction, no uniqueness theorem from the authors is imported, and no ansatz is smuggled in by citing prior work. The downward-closure scaling is not self-definitional: the approximation oracle's guarantee concerns linear objectives over K, while the approachability target being approachable is the input, and the efficient approachability of the scaled downward closure is the proved conclusion. The invalid inequality in Lemma 10's proof is a local correctness gap (repairable as noted) rather than a circular step, so it does not affect the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

All numerical constants are problem parameters (radii, diameters, norms, ratios) rather than fitted values. The paper imports standard OCO regret bounds and Blackwell's theorem, and restricts to nonnegative, monotone games.

assumptions (5)
  • standard math Blackwell's approachability theorem (Theorem 1 in the paper)
    Serves as the characterization of approachable sets and the basis for the modified-instance arguments.
  • standard math Regret bound of online gradient descent (Theorem 3)
    Used as the OCO subroutine in Algorithms 1, 2, 3 and 6; a standard result from [8].
  • standard math Extended approximation oracle lemma (Lemma 1, from [6] and [10])
    Imported as a black box; its three properties are used throughout the infeasible saddle-point oracles.
  • domain assumption Assumption 1: X and Y lie in the nonnegative orthant and ℓ is nonnegative on R_+^n × R_+^m
    Load-bearing for the monotonicity step s_t ≤ x_t implies ℓ(s_t, y_t) ≤ ℓ(x_t, y_t); restricts the scope.
  • domain assumption Player preferences are monotone (not preferring a loss vector over a coordinatewise smaller one)
    Justifies targeting the downward closure of the scaled set; without it the guarantee has no normative meaning.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Blackwell's Approachability with Approximation Algorithms." pith.science (2026). https://pith.science/paper/5FJSTZGZ

@misc{pith2026250203919,
  author       = {Pith},
  title        = {Pith review of: Blackwell's Approachability with Approximation Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5FJSTZGZ}},
  note         = {Machine review of arXiv:2502.03919}
}
abstract

We revisit Blackwell's celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee \textit{efficiently}, when only having access to these sets via approximation algorithms with ratios $\alpha_{\mX} \geq 1$ and $ 1 \geq \alpha_{\mY} > 0$, respectively. Assuming the player has monotone preferences, in the sense that he does not prefer a vector-valued loss $\ell_1$ over $\ell_2$ if $\ell_2 \leq \ell_1$, we establish that given a Blackwell instance with an approachable target set $S$, the downward closure of the appropriately-scaled set $\alpha_{\mX}\alpha_{\mY}^{-1}S$ is \textit{efficiently} approachable with optimal rate. In case only the player's or adversary's set is equipped with an approximation algorithm, we give simpler and more efficient algorithms.

Figures

Figures reproduced from arXiv: 2502.03919 by the authors.

Figure 1
Figure 1. Illustration of the relationship between the target set [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [13]

    An online convex optimization approach to blackwell’s ap- proachability

    Nahum Shimkin. An online convex optimization approach to blackwell’s ap- proachability. Journal of Machine Learning Research , 17(129):1–23, 2016

    work page 2016

  2. [10]

    Playing games with approximation algorithms

    Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 546–555, 2007

    work page 2007

  3. [1]

    Blackwell approachability and no-regret learning are equivalent

    Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Con- ference on Learning Theory , pages 27–46. JMLR Workshop and Conference Proceedings, 2011

    work page 2011

  4. [2]

    A linear-time approximation algorithm for the weighted vertex cover problem

    Reuven Bar-Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms , 2(2):198–203, 1981

    work page 1981

  5. [3]

    An analog of the minimax theorem for vector payoffs

    David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics , 1956. 20

    work page 1956

  6. [4]

    Convex optimization

    Stephen Boyd. Convex optimization. Cambridge UP , 2004

    2004

  7. [5]

    Cam- bridge university press, 2006

    Nicolo Cesa-Bianchi and G´ abor Lugosi.Prediction, learning, and games. Cam- bridge university press, 2006

    work page 2006

  8. [6]

    Efficient online linear optimization with approximation algo- rithms

    Dan Garber. Efficient online linear optimization with approximation algo- rithms. Advances in Neural Information Processing Systems , 30, 2017

    work page 2017

Show all 15 references
  1. [7]

    Approximate convex optimization by online game playing

    Elad Hazan. Approximate convex optimization by online game playing. arXiv preprint cs/0610119, 2006

    2006 arXiv

  2. [8]

    Introduction to online convex optimization

    Elad Hazan. Introduction to online convex optimization. CoRR, abs/1909.05207, 2019

    1909 arXiv

  3. [9]

    Online improper learning with an approximation oracle

    Elad Hazan, Wei Hu, Yuanzhi Li, and Zhiyuan Li. Online improper learning with an approximation oracle. Advances in Neural Information Processing Systems, 31, 2018

    2018

  4. [11]

    Game theory

    Michael Maschler, Shmuel Zamir, and Eilon Solan. Game theory. Cambridge University Press, 2020

    2020

  5. [12]

    Approachability, regret and calibration: Implications and equivalences

    Vianney Perchet. Approachability, regret and calibration: Implications and equivalences. Journal of Dynamics and Games , 1(2):181–254, 2014

    2014

  6. [14]

    ℓ nX j=1 xjej, mX k=1 ykek !# i =

    Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003. A Proof of Lemma 2 We first restate the lemma and then prove it. Lemma 8 (structur...

    2003

  7. [15]

    22 Proof

    Then, for any R > 0, the Blackwell instance (X , ˜Y, ℓ,˜S), where ˜Y := Y − B+(R), ˜S := S − B+( ˜R), for ˜R = ∥ℓ∥RX R (where ∥ℓ∥ is defined in Lemma 2), is approachable. 22 Proof. Fix some w ∈ B. By the definition of the support function (Eq, 1) we have that, h ˜S(w) = hS−B+(...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.