Blackwell可逼近性与梯度均衡的等价性研究

Computer Science > Machine Learning

arXiv:2606.27315v1 (cs) [Submitted on 25 Jun 2026]

Title:Blackwell Approachability and Gradient Equilibrium are Equivalent

Authors:Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani View a PDF of the paper titled Blackwell Approachability and Gradient Equilibrium are Equivalent, by Brian W. Lee and 3 other authors View PDF HTML (experimental)

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.

Comments:	30 pages, 1 figure, accepted for presentation at COLT 2026
Subjects:	Machine Learning (cs.LG)
Cite as:	arXiv:2606.27315 [cs.LG]
	(or arXiv:2606.27315v1 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2606.27315 Focus to learn more arXiv-issued DOI via DataCite

Submission history

From: Brian W. Lee [view email]
[v1] Thu, 25 Jun 2026 17:29:48 UTC (109 KB)
Full-text links:

Access Paper:

View a PDF of the paper titled Blackwell Approachability and Gradient Equilibrium are Equivalent, by Brian W. Lee and 3 other authors
• View PDF
• HTML (experimental)
• TeX Source

view license

Current browse context:

cs.LG < prev   |   next >
new | recent | 2026-06 Change to browse by: cs

References & Citations

• NASA ADS
• Google Scholar
• Semantic Scholar

export BibTeX citation Loading...

BibTeX formatted citation

× Data provided by:

Bookmark

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos

Demos

Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers

Recommenders and Search Tools

Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?) IArxiv recommender toggle IArxiv Recommender (What is IArxiv?)

• Author
• Venue
• Institution
• Topic

About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)