提出高效统一预测方法,让单一模型满足多个决策者需求。
Sample-Efficient Omniprediction for Proper Losses
- 直接设计结构化算法,避免随机化与复杂性
- 证明多校准比统一预测更难,现有方法样本效率低
- 适用于需兼顾多方利益的决策场景
我们研究如何构建概率预测,使下游用户用其做出准确决策。对单一决策者,最优预测等价于最小化对应适当损失函数。对多个决策者,问题可视为统一预测的变体,目标是设计一个能同时最小化多个损失的预测器。现有方法分为两类:一是通过优化多校准等辅助目标实现统一预测;二是基于对抗双人博弈在线估计并响应最坏情况损失。我们给出下界,证明多校准严格难于统一预测,因此前类方法必然导致次优样本复杂度。针对后类方法,我们通过在线到批量转换构造出样本高效的算法,但结果为复杂随机预测器。我们改进该方法,设计出更直接、非随机的算法,利用适当损失集合的结构特性。
原文摘要 · Abstract (English)
We consider the problem of constructing probabilistic predictions that lead to accurate decisions when employed by downstream users to inform actions. For a single decision maker, designing an optimal predictor is equivalent to minimizing a proper loss function corresponding to the negative utility of that individual. For multiple decision makers, our problem can be viewed as a variant of omniprediction in which the goal is to design a single predictor that simultaneously minimizes multiple losses. Existing algorithms for achieving omniprediction broadly fall into two categories: 1) boosting methods that optimize other auxiliary targets such as multicalibration and obtain omniprediction as a corollary, and 2) adversarial two-player game based approaches that estimate and respond to the ``worst-case" loss in an online fashion. We give lower bounds demonstrating that multicalibration is a strictly more difficult problem than omniprediction and thus the former approach must incur suboptimal sample complexity. For the latter approach, we discuss how these ideas can be used to obtain a sample-efficient algorithm through an online-to-batch conversion. This conversion has the downside of returning a complex, randomized predictor. We improve on this method by designing a more direct, unrandomized algorithm that exploits structural elements of the set of proper losses.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。