将二分类全能预测扩展到多分类，实现更优的误差控制。
Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
- 设计新算法同时逼近多个目标，解决多分类下的全能预测问题。
- 在k类问题中，样本复杂度或后悔界约为ε^(-(k+1))，优于传统方法。
- 适用于需要统一处理多种损失函数的复杂预测场景。
全能预测是一种学习任务，要求对一组损失函数集合ℒ与一组比较预测器集合𝒞，提供次优性边界。本文首次研究了多分类情形下的全能预测，其中比较器集合𝒞可为无限集。主要成果是将[OKK25]提出的二分类全能预测算法推广至多分类设置，实现了在统计设定下的样本复杂度或在线设定下的后悔界约为ε^{-(k+1)}，以达成ε-全能预测，其中ε为误差容忍度，k为类别数。在证明过程中，我们提出一个具有广泛适用性的框架，用于解决需通过耦合动作同时逼近多个集合的Blackwell可逼近性问题。
原文摘要 · Abstract (English)
Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses $\mathcal{L}$ against a family of comparator predictors $\mathcal{C}$. We initiate the study of omniprediction in a multiclass setting, where the comparator family $\mathcal{C}$ may be infinite. Our main result is an extension of the recent binary omniprediction algorithm of [OKK25] to the multiclass setting, with sample complexity (in statistical settings) or regret horizon (in online settings) $\approx \varepsilon^{-(k+1)}$, for $\varepsilon$-omniprediction in a $k$-class prediction problem. En route to proving this result, we design a framework of potential broader interest for solving Blackwell approachability problems where multiple sets must simultaneously be approached via coupled actions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。