提出无需依赖特征维度的决策校准方法,让模型预测更可信。
Dimension-Free Decision Calibration for Nonlinear Loss Functions
- 用平滑最优响应替代确定性响应,突破维度限制
- 仅需多项式样本量即可实现决策校准
- 适用于可被有界范数函数近似的复杂函数类
当模型预测用于下游决策时,关键问题是:在何种条件下,决策者可直接依据预测结果做出最优响应?传统校准虽能保证此性质,但高维输出空间下计算与统计复杂度呈指数增长。近期提出的决策校准放宽条件,仅需多项式样本量,但其理论基础依赖线性损失函数。针对非线性损失,常见做法是将输出映射到特征空间ϕ(y),再用ϕ(y)的线性函数近似损失,然而简单非线性函数可能需要指数甚至无限维特征空间。一个核心开放问题在于:能否实现与特征维数m无关的决策校准?本文首先给出负结果:在标准确定性最优响应下,验证决策校准所需样本量至少为m的多项式。为此,我们引入平滑版决策校准,即决策者采用平滑最优响应。该松弛允许设计维度无关的校准算法:给定poly(|A|,1/ε)个样本和任意初始预测器p,可高效后处理使其满足平滑决策校准,且不降低预测精度。算法适用于可被有界范数函数近似于(可能无限维)可分再生核希尔伯特空间(RKHS)的函数类。
原文摘要 · Abstract (English)
When model predictions inform downstream decision making, a natural question is under what conditions can the decision-makers simply respond to the predictions as if they were the true outcomes. Calibration suffices to guarantee that simple best-response to predictions is optimal. However, calibration for high-dimensional prediction outcome spaces requires exponential computational and statistical complexity. The recent relaxation known as decision calibration ensures the optimality of the simple best-response rule while requiring only polynomial sample complexity in the dimension of outcomes. However, known results on calibration and decision calibration crucially rely on linear loss functions for establishing best-response optimality. A natural approach to handle nonlinear losses is to map outcomes $y$ into a feature space $ϕ(y)$ of dimension $m$, then approximate losses with linear functions of $ϕ(y)$. Unfortunately, even simple classes of nonlinear functions can demand exponentially large or infinite feature dimensions $m$. A key open problem is whether it is possible to achieve decision calibration with sample complexity independent of~$m$. We begin with a negative result: even verifying decision calibration under standard deterministic best response inherently requires sample complexity polynomial in~$m$. Motivated by this lower bound, we investigate a smooth version of decision calibration in which decision-makers follow a smooth best-response. This smooth relaxation enables dimension-free decision calibration algorithms. We introduce algorithms that, given $\mathrm{poly}(|A|,1/ε)$ samples and any initial predictor~$p$, can efficiently post-process it to satisfy decision calibration without worsening accuracy. Our algorithms apply broadly to function classes that can be well-approximated by bounded-norm functions in (possibly infinite-dimensional) separable RKHS.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。