揭示梯度均衡与布莱克威尔可逼近性等价,统一在线学习框架
Blackwell Approachability and Gradient Equilibrium are Equivalent
- 证明梯度均衡可通过黑盒查询求解布莱克威尔问题
- 建立梯度均衡与后悔最小化、校准等框架的等价关系
- 适用于追求自适应性与乐观性保证的研究者
梯度均衡(GEQ)是近期提出的在线优化框架,推广了离线优化中的一阶平稳性概念,并能抽象在线共形预测等问题。尽管GEQ与已知在线学习框架(如后悔最小化)存在相似性,已有研究表明其误差与后悔不可比较,导致对GEQ在在线学习整体图景中的定位尚不清晰。本文证明,在算法意义上,GEQ与布莱克威尔可逼近性完全等价:任何布莱克威尔可逼近问题均可通过调用黑盒GEQ预言机求解,且无需牺牲预言机的误差率;反之亦然。结合已知的可逼近性、后悔最小化与校准之间的等价关系,进一步表明GEQ与这些框架等价。我们的约化方法高效,可将后悔最小化中精细的保证(如乐观性、强自适应性)迁移至GEQ。同时,我们还给出了GEQ存在的充要条件,并建立了无约束与有约束决策集下不同形式GEQ间的约化关系。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。