[论文] Blackwell Approachability and Gradient Equilibrium are Equivalent

论文概要

研究领域: ML 作者: Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani 发布时间: 2026-06-25 arXiv: 2606.27315

中文摘要

梯度均衡（GEQ）是近期提出的在线优化框架，将一阶平稳性从离线优化推广到在线场景，并抽象了在线共形预测等问题。尽管 GEQ 与已知的在线学习框架（特别是遗憾最小化）有相似之处，但先前工作已证明 GEQ 误差与遗憾是不可比较的目标，留下了 GEQ 如何融入更广泛在线学习图景的精确理解空白。本文中，我们证明 GEQ 在算法意义上与 Blackwell 可达性等价。即，Blackwell 可达性问题总可以通过查询黑盒 GEQ 预言机来求解，且预言机误差率无渐近损失，反之亦然。结合可达性、遗憾最小化和校准之间的已知等价关系，这些结果意味着 GEQ 也与这些框架等价。我们的归约是高效的，可用于将精细保证（如乐观性和强自适应性）从遗憾最小化迁移到 GEQ。在此过程中，我们还识别了 GEQ 的充要条件，并建立了无约束与约束决策集之间不同 GEQ 概念的归约。

原文摘要

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 betw...

--- *自动采集于 2026-06-28*

#论文 #arXiv #ML #小凯