Equivalence between Blackwell Approachability and Gradient Equilibrium
Score
53Why selected
The core contribution is the first proof of equivalence between Gradient Equilibrium and Blackwell approachability, thereby unifying several important online learning frameworks with high theoretical value and practical reduction methods.
AI commentary
「This research fills the gap in positioning Gradient Equilibrium within online learning theory, establishes equivalence with classical frameworks, and provides theoretical foundations for designing more efficient online optimization algorithms.」
Quick overview
This paper establishes the algorithmic equivalence between Gradient Equilibrium (GEQ) and Blackwell approachability. GEQ is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization and abstracts problems like online conformal prediction. By constructing bidirectional reductions, the paper reveals deep connections between GEQ and classical online learning frameworks such as regret minimization and calibration. It also identifies necessary and sufficient conditions for GEQ and provides reductions between different notions of GEQ under unconstrained and constrained decision sets. This work provides a key piece for unifying online learning theory.
- Gradient Equilibrium (GEQ) is algorithmically equivalent to Blackwell approachability, with bidirectional reductions preserving asymptotic error rates.
- Through known equivalences among approachability, regret minimization, and calibration, GEQ is also equivalent to these frameworks.
- Necessary and sufficient conditions for GEQ are identified, and reductions between different GEQ notions under unconstrained and constrained decision sets are established.
- The reductions are efficient and can transfer refined guarantees such as optimism and strong adaptivity from regret minimization to GEQ.
Full text
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
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, MediaCode, 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?) DemosDemos
Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related PapersRecommenders 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?) About arXivLabsarXivLabs: 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?)Related items
92
FeaturedOpenRouter Launches Prompt Caching with Sticky Routing to Drastically Reduce Multi-Turn Costs
OpenRouter 推出提示缓存与粘性路由，大幅降低多轮对话成本
For developers making frequent AI API calls, this feature is a direct money-saver. Sticky routing guarantees cache hit rates, and session_id requires zero configuration—every OpenRouter user should try it immediately.
91
FeaturedChatGPT Work: An AI Agent That Takes Action Across Apps and Files
ChatGPT Work：可在跨应用和文件中执行操作的AI Agent
I think this is a key step for AI assistants moving from Q&A to execution. Especially noteworthy for professionals who need to automate complex workflows. ChatGPT Work could become a new paradigm for productivity tools.
90
FeaturedAnatomy of a Frontier Lab Agent Intrusion: A Technical Timeline of the July 2026 Incident
前沿实验室代理入侵事件技术时间线：2026年7月事件剖析
This technical timeline is a must-read for all AI security researchers and agent developers—it doesn't just describe one attack but sounds an alarm on the weak defense systems of agent architectures. For teams deploying autonomous agents, this is an essential disaster prevention manual.
90
FeaturedBetter Tools Made Copilot Code Review Worse? Here's How GitHub Improved It
更好的工具反而让Copilot代码审查更糟？GitHub这样改进
This blog post deserves close reading by all AI product engineers and ML practitioners—it breaks the intuition that 'more powerful tools = better AI' and instead emphasizes an engineering philosophy aligned with agent reasoning patterns. Especially important for teams optimizing code review or similar agent-based products.
88
FeaturedOpenRouter Launches Unified Multimodal API: Single Endpoint for Image, Video, Audio, Embeddings, and Transcription
OpenRouter 推出统一多模态 API：单端点支持图像、视频、音频、嵌入与转录
This news is worth attention from all developers building multimodal AI applications: OpenRouter's unified API solves the pain of model switching, especially for startups or rapid prototyping. If you're struggling with multiple API keys and SDKs, this interface could be the unified layer you need.
87
FeaturedAnthropic Launches Claude for Teachers: AI Tools Designed for Educators
Anthropic 推出 Claude for Teachers：面向教师的教育 AI 工具
This announcement is valuable for educators and AI industry watchers alike. Instead of a generic chatbot, Anthropic designed a safety-first tool specifically for teachers, demonstrating the right approach for AI vertical deployment: solving real pain points rather than showing off technology. The built-in guardrails also set a reference for other AI companies, especially when serving scenarios involving children or teenagers.
86
FeaturedOpenRouter Introduces New Auto Router: Model Routing Powered by Market Wisdom
OpenRouter发布全新Auto Router：用市场智慧优化模型路由
This update is worth attention for anyone using APIs to build AI apps. Instead of guessing or testing model selection, market data now does the heavy lifting. Though sparse on details, the direction is right, especially for teams relying on aggregated model services.
86
FeaturedClaude Code v2.1.211 Release: Multiple Fixes and Improvements
Claude Code v2.1.211 发布：多项修复与改进
As a developer who frequently uses Claude Code for automated coding, I'm particularly interested in the security fixes, especially the permission preview character bypass and auto mode overriding hook decisions—these directly affect the security boundaries during team collaboration. The improvement in background agent reporting also makes long-running tasks more reliable. I recommend all users upgrade as soon as possible.