Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility¶

会议: NeurIPS 2026
arXiv: 2505.16494
领域: AI 安全
关键词: 算法公平性, 多校准, 决策精度, 效用权衡, 计算不可区分性

一句话总结¶

本文揭示了在具有丰富标签（类型、排序或风险分布）的学习任务中，子群体分类接受率保证（决策/分类精度）与预测校准度及效用最优化（损失极小化）之间存在本质的计算复杂度权衡：贝叶斯最优预测器可同时满足两类精度，但在单向函数假设下，任何多项式时间算法都无法同时兼顾。

研究背景与动机¶

算法公平性研究历来被各种不可调和的内在冲突所困扰，最经典的当属 Kleinberg 等人与 Chouldechova 提出的不可能定理，即在不同群体基线胜率不一致时，预测校准度与跨群体假正例/假反例率均衡在统计上必然发生冲突。传统文献通常将这一矛盾归结为信息论层面的内在数学互斥，即使拥有完美的贝叶斯最优预测器 $p^*(x)$，这种统计冲突依然无法消除。然而，在诸多高风险决策场景（如医疗处方、贷款发放与大学录取）中，最小化决策损失不仅是机构效益的诉求，也是保障受保护群体免遭错误干预或拒绝的关键，从而促使研究者重新审视基于证据的公平性准则。

这一矛盾在仅有二元历史观测标签（如是否还款、是否发病）的标准监督学习中尤为尖锐。在二元监督下，学习算法无法区分群体的内在风险分布：例如一组个体的违约率均为 50%，与该组由一半必违约和一半必还款的个体混合而成，在二元观测中产生完全相同的一阶统计量，但下游基于确定阈值的决策规则却会在两种情况下施加截然相反的分类待遇。为了化解这一表征瓶颈，研究者引入包含个体完整类型、相对全局排序或真实风险估计的“确定性丰富标签”（Rich Labels）。理论上，若能获得这类消除内在偶然不确定性的丰富标签，贝叶斯最优预测器便能同时实现完美校准与精确的子群体决策接受率。

然而，核心问题在于：当贝叶斯最优预测器本身无法在多项式时间内被完全学习时，仅通过高效逼近算法能否同时保全这两类自然且均受公平性驱动的精度目标？核心 idea：本文证明了分类率精度（Decision/Classification Accuracy）与效用最优化（Calibration/Loss Minimization）之间存在计算复杂度层面的分离定理——虽然贝叶斯最优解同时满足两者且各目标均可单独高效学习，但在单向函数存在的标准密码学假设下，任何多项式时间算法都无法在非仿射决策规则或非平凡损失函数下同时兼顾二者。

方法详解¶

整体框架¶

本文构建了一个统一的富标签预测与下游分类决策框架。自然界分布表示为 $\mathcal{D} = \mathcal{D}_{\mathcal{X}} \times R^*(\mathcal{D}_{\mathcal{X}})$，其中每个个体 $x \in \mathcal{X}$ 对应有限类型空间 $\mathcal{T}$（$|\mathcal{T}|=k$）上的真实随机向量 $R^*(x) \in \mathcal{Y} \subset \Delta(\mathcal{T})$。学习算法输出概率化预测器 $\tilde{R}: \mathcal{X} \to \mathcal{Y}$，并通过两类下游决策路径映射到二元决策 $a \in \{0, 1\}$： 1. 预测驱动路径：通过决策规则 $\rho: \mathcal{Y} \to \{0, 1\}$（例如风险阈值规则 $\rho(y) = \mathbb{I}[y_{\text{repay}} \geq 0.95]$）将预测分布映射为动作； 2. 直接动作路径：构建动作函数 $h: \mathcal{X} \to \{0, 1\}$，并针对给定损失函数 $\ell: \mathcal{T} \times \{0, 1\} \to [0, 1]$ 评估其期望损失 $\mathsf{exp\text{-}loss}_{\mathcal{D}}(h)$。

针对这一系统，论文形式化定义了子群体集合族 $\mathcal{C}$ 上的四维精度概念网格：多精度（MA）、多校准（MC）、决策多精度（MAD）与分类多精度（MAC），并建立了正向泛化与基于伪随机性硬度分离的完整图景。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["自然界分布 D & 丰富标签空间 T"] --> B["阶段 1：概率预测器训练<br/>学习逼近 R*(x) 的多精度/多校准预测器 R~"]
    B --> C{"阶段 2：下游决策路径选择"}
    C -->|仿射规则 / 随机实例化| D["路径 A：保全分类率精度 (MAD / MAC)<br/>群体接受率严格对齐贝叶斯基准"]
    C -->|损失极小化决策规则 ρ*| E["路径 B：保全效用/损失极小化<br/>损失对齐基准假设族 H_C"]
    D -.->|计算不可兼得：单向函数下互斥| E

关键设计¶

1. 决策规则仿射性等价刻画与精度保持
在将预测器 $\tilde{R}$ 投入决策规则 $\rho$ 时，模型预测在子群体 $S \in \mathcal{C}$ 上引发的期望动作分布可能发生严重漂移。本文证明了一个基础结构定理：决策规则 $\rho$ 满足仿射性（即对任意分布的凸组合保持线性），当且仅当它等价于“先实例化后执行”（Instantiate-Then-Act, ITA）规则。也就是说，存在随机函数 $g: \mathcal{T} \to \{0, 1\}$，使得 $\rho(y)$ 的输出分布与先从 $y$ 中采样类型 $t \sim y$ 再执行 $g(t)$ 完全相同： $$ \mathbb{E}{\rho}[\rho(y)] = \sum[g(t)] $$ 基于该等价性，定理 3.4 证明：若预测器 }} y_t \, \mathbb{E$\tilde{R}$ 满足 $(\mathcal{C}, \alpha)$-坐标多精度，且决策规则 $\rho$ 是 $\varepsilon$-近似仿射的，则 $\tilde{R}$ 自动满足 $(\mathcal{C}, \varepsilon')$-决策多精度（MAD），其中误差上界为 $\varepsilon' \leq \frac{k\alpha}{\delta} + 2\varepsilon$（$\delta = \Pr[x \in S]$）。若类型具有全序结构且预测器满足阈值多精度，该界中的类别数膨胀因子 $k$ 可被完全消除，误差缩减为 $\frac{\alpha}{\delta} + 2\varepsilon$。

2. 基于计算不可区分性的非仿射决策不可能定理
然而，实际应用中最常用的规则均非仿射，例如风险截断规则或期望损失极小化规则。定理 4.1 指出，一旦决策规则 $\rho$ 偏离仿射且满足 $M$-Lipschitz 连续性，校准度与决策精度在计算上不可兼得。其构造技术极其巧妙：假定存在具有安全参数 $\kappa$ 的单向函数，在全集 $\mathcal{X}$ 中构造一个比例为 $\gamma$、高效算法无法识别的子集 $\mathcal{X}_1$（即 $\mathcal{X} = \mathcal{X}_1 \mathbin{\dot{\cup}} \mathcal{X}_2$）。自然界 $R^*$ 在 $\mathcal{X}_1$ 上恒定赋予标签分布 $y$，在 $\mathcal{X}_2$ 上赋予 $y'$。由于 $\rho$ 偏离仿射，存在凸组合使得 $\rho(\gamma y + (1-\gamma) y') \neq \gamma \rho(y) + (1-\gamma) \rho(y')$。任何在多项式时间内学习到的坐标校准预测器 $\tilde{R}$，由于无法识别 $\mathcal{X}_1$ 的成员资格，其大部分预测值必须收缩平滑到平均分布 $\gamma y + (1-\gamma) y'$；但在评估决策精度时，$R^*$ 诱导的期望动作为 $\gamma \rho(y) + (1-\gamma) \rho(y')$，两者之差必然下界为 $\Omega(\varepsilon)$，从而在单群体上直接证伪了高效算法同时实现校准与决策精度的可能性。

3. 分类率精度与损失极小化的本质对立
针对脱离显式预测器、直接输出动作的分类器 $h: \mathcal{X} \to \{0, 1\}$，本文提出了更为深刻的不可能性结论（定理 5.1）。对于任意非平凡二元损失函数 $\ell \in \mathcal{L}_\alpha$（即存在至少一个类型使得采纳与拒绝的损失差绝对值不小于 $\alpha$），考虑仅由常数分类器构成的最弱基准族 $\mathcal{H} = \{h_0 \equiv 0, h_1 \equiv 1\}$。定理证明，任何在多项式时间内计算且满足 $(\ell, \varepsilon)$-分类多精度（MAC）的动作函数 $h$，其期望损失相比于常数拒绝分类器 $h_0$ 必然恶化至少 $\frac{\alpha}{8} - O(\varepsilon)$。核心原因在于：为匹配贝叶斯最优分类器 $h^*_\ell$ 的整体接受率（例如 $1/4$），高效分类器必须随机或伪随机地接受 $1/4$ 的个体；但受制于单向函数的计算不可区分性，这些被接受的样本中有 $3/4$ 错误地落在了本应被拒绝的高损失子集 $\mathcal{X}_1$ 中，进而招致显著的不可消除超额损失。

4. 全称预测器框架下的多校准效用传递与多维松弛
在正面构造方面，论文建立了将多校准预测器转化为强效用分类器的完备路线。定理 6.1 证明，若预测器 $\tilde{R}$ 满足全多校准（Full Multi-Calibration），直接将其与确定性损失极小化规则复合得到 $h = \rho^*_\ell \circ \tilde{R}$，即可保证其损失竞争性地贴近基准动作族 $\mathcal{H}_{\mathcal{C}}$，超额损失严格受控于 $3k(\alpha + \lambda)$。面对全多校准随类型数 $k$ 呈指数级样本膨胀的痛点，论文提出了三类高效松弛方案： - 线性损失与概率空间：将多维类型坍缩为期望标量预测值 $\tilde{q}(x) = \sum \beta \tilde{R}(x)_\beta$，利用一维多校准算法（如 HKRR 提升算法）在样本数 $\tilde{O}(\log(|\mathcal{C}|/\delta) / (\alpha^4 \lambda^{1.5}))$ 内实现 $6(\alpha+\lambda)$ 的损失竞争界； - 固定已知损失：构造损失加权标量预测器 $p_{\tilde{R}, \ell}(x) = \frac{1 - \mathbb{E}[(\ell(t,1)-\ell(t,0))]}{2}$，将任意类型空间的损失极小化问题完全等价化为一维半空间校准，损失超额仅为 $2\alpha$； - 损失族审计与结果不可区分性（OI）：针对未知损失族 $\mathcal{L}$，利用样本访问结果不可区分性（Sample-Access OI），仅需 $\tilde{O}(\frac{\log k (\log |\mathcal{C}| + \log |\mathcal{L}|)}{\varepsilon^4})$ 样本即可完成多损失联合效用保障。

一个完整示例¶

考虑一个由大学招生委员会制定的录取场景，申请者包含常规背景群体与隐性特质群体，其特征在当前可采集维度下计算不可区分（$|\mathcal{X}_1| = \frac{3}{4}|\mathcal{X}|, |\mathcal{X}_2| = \frac{1}{4}|\mathcal{X}|$）。 1. 真实世界标签分布：自然界 $R^*$ 确定性赋予 $\mathcal{X}_1$ 中个体类型 $t$（培养失败风险高，损失差 $\ell(t,1) - \ell(t,0) = 0.8$），赋予 $\mathcal{X}_2$ 中个体类型 $t'$（学术潜力极高，损失差 $\ell(t',1) - \ell(t',0) = -0.4$）； 2. 贝叶斯最优决策：最优分类器 $h^*_\ell$ 拒绝所有 $\mathcal{X}_1$ 个体并录取所有 $\mathcal{X}_2$ 个体，总体录取率为 $25\%$，总期望损失为 $L^* = \frac{3}{4}\ell(t,0) + \frac{1}{4}\ell(t',1)$； 3. 公平性路线（MAC）的选择代价：若决策者要求动作函数满足分类精度（MAC），高效模型必须录取全域中 $25\%$ 的学生。由于无法区分 $\mathcal{X}_1$ 与 $\mathcal{X}_2$，其录取的学生中必然有 $\frac{3}{4} \times 25\% = 18.75\%$ 来自高风险群体 $\mathcal{X}_1$。与全拒基准 $h_0$ 相比，模型造成的总期望损失额外增加了 $\frac{1}{4}(L_1 - L_0) \geq \frac{0.8}{8} = 0.10$； 4. 效用路线（Loss Minimization）的选择代价：若决策者改用多校准预测器并应用确定性极小化规则 $\rho^*_\ell$，模型将输出恒定常数预测 $\tilde{p}(x) = \frac{3}{4}t + \frac{1}{4}t'$，计算期望损失差为 $\frac{3}{4}(0.8) + \frac{1}{4}(-0.4) = 0.5 > 0$，决策规则判定全部拒绝（录取率 $0\%$）。此时效用达到可计算边界下的最优（匹配 $h_0$），但 $\mathcal{X}_2$ 群体原本应得的录取机会被全盘抹去，完全丧失了分类精度。

损失函数 / 训练策略¶

对于不同的精度保证路径，训练策略与目标设计遵循严格正交的路线： - 多精度/多校准审计提升算法：算法从初始常数预测器出发，引入判别器集合族 $\mathcal{A}$ 进行黑盒审计。若在子群体 $S \in \mathcal{C}$ 上检测到预测残差期望超过容差 $\alpha$，则沿梯度方向更新预测器分量： $$ \tilde{R}{\tau+1}(x) \leftarrow \tilde{R}\tau(x) + \eta \cdot A_S(x) $$ 通过弱不可知学习（Weak Agnostic Learning）求解子集成员识别问题，将样本复杂度和运行时间收敛至多项式级别； - 部署期决策推迟机制：由于两类目标由同一概率化预测器派生，系统在离线阶段仅需训练高阶多校准预测器 $\tilde{R}$。在实际部署上线时，决策者可根据具体监管要求选择将输出送入仿射随机采样模块以满足公平性审计（MAC），或送入非仿射确定性 Argmin 算子以满足业务效用考核。

实验关键数据¶

理论结果与分离界对比¶

论文给出了在不同决策规则与学习目标下的理论可行性与下界保证：

保证目标组合	适用决策规则类别	计算可行性	理论误差下界 / 复杂度上界	核心依赖假设
MA $\implies$ MAD	$\varepsilon$-近似仿射 (ITA 规则)	多项式时间高效可解	误差界 $\leq \frac{k\alpha}{\delta} + 2\varepsilon$	无额外假设 (统计成立)
阈值 MA $\implies$ MAD	单调确定性仿射规则	多项式时间高效可解	误差界 $\leq \frac{\alpha}{\delta} + 2\varepsilon$	排序类型全序假设
坐标校准 + MAD	$M$-Lipschitz 且 $\varepsilon$-远离仿射	计算不可行 (Hard)	决策误差下界 $> \frac{\varepsilon}{2}$	存在单向函数 (OWF)
MAC + 损失极小化	任意非平凡损失 $\ell \in \mathcal{L}_\alpha$	计算不可行 (Hard)	相比 $h_0$ 超额损失 $\geq \frac{\alpha}{8} - O(\varepsilon)$	存在单向函数 (OWF)
全多校准 $\implies$ 损失极小化	任意损失函数 $\ell$	样本指数级 / 理论可行	竞争损失界 $\leq 3k(\alpha + \lambda)$	无密码学假设 (全称预测)

算法松弛路径与复杂度对比¶

针对效用最优化路线中多校准的复杂度瓶颈，论文提出三种松弛算法的样本与时间复杂度：

松弛算法机制	适用标签类型	损失函数约束	样本复杂度	运行时间复杂度	最终超额损失界
原始全多校准 (Canonical)	离散有限类型 $\mathcal{T}$	任意二元损失	$O((1/\lambda)^k \cdot \text{poly})$	随类别数 $k$ 指数爆炸	$3k(\alpha + \lambda)$
期望标量预测器 $\mathbb{E}_{\tilde{R}}$	离散区间 $\Lambda[0,1]$	第一分量线性损失	$\tilde{O}\left(\frac{\log(	\mathcal{C}	/\delta)}{\alpha^4 \lambda^{1.5}}\right)$
损失加权预测器 $p_{\tilde{R}, \ell}$	任意有限类型 $\mathcal{T}$	训练期预先给定单一 $\ell$	$\tilde{O}\left(\frac{\log(	\mathcal{C}	/\delta)}{\alpha^4 \lambda^{1.5}}\right)$
结果不可区分性 (Sample OI)	任意有限类型 $\mathcal{T}$	训练期给定损失族 $\mathcal{L}$	$\tilde{O}\left(\frac{\log k (\log	\mathcal{C}	+ \log

关键发现¶

仿射性是决定可兼容性的充要边界：只要决策规则是仿射的，多精度条件就足以线性保全群体的决策接受率；一旦规则引入非仿射截断或极值算子，计算不可区分性就会强行抹平高效模型的辨识能力。
群体公平与个体效用的内在冲突不可靠丰富标签解决：即使领域专家提供了完全消除偶发不确定性的确定性丰富标签，只要多项式时间学习器无法破译底层伪随机结构，就必须在“维持代表性比例”与“最大化群体效用”之间二选一。

亮点与洞察¶

将密码学伪随机性深度融入算法公平性底层理论：突破了以往公平性不可行定理依赖统计互斥或信息论界限的传统框架，首次确立了贝叶斯最优解存在下的纯计算复杂度分离结论。
解耦训练阶段与下游决策部署目标：确立了高阶多校准预测器作为“万能预测器”（Omnipredictor）的核心地位，使系统能够通过调整后处理算子（仿射随机化 vs 确定性 Argmin）自适应应对动态政策需求。
从样本复杂度角度系统解决多类别校准爆炸问题：通过期望压缩、损失诱导标量投影以及 OI 判别器审计，为复杂结构标签下的算法公平性落地扫清了样本复杂度障碍。

局限与展望¶

理论依赖确定性自然界假设：尽管对于丰富标签的建模合情合理，但在真实场景中自然界本身往往包含不可消除的任意随机混合，推广至完全概率化自然界需要引入高阶校准与独立多标签采样。
二元动作空间约束：当前下界与转化定理主要建立在二元决策 $\{0, 1\}$ 之上，对于连续决策空间（如信用额度、定价或刑期判定）的拓扑连续性推导仍待进一步扩展。
实际分布与弱学习预言机的可实现性：定理要求基准子群族 $\mathcal{C}$ 具备高效弱不可知学习算法，在实际深度学习特征空间中构建可高效审计的假设集仍需工程近似。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从计算复杂度与密码学伪随机性角度剖析公平性与效用冲突，理论框架极具开创性。
理论深度: ⭐⭐⭐⭐⭐ 证明构造完整严密，精细刻画了 Lipschitz 常数、离散化步长与多精度误差的级联关系。
写作质量: ⭐⭐⭐⭐⭐ 逻辑推导层次分明，定理陈述与直觉解释结合紧密。
价值: ⭐⭐⭐⭐⭐ 为高风险决策系统的公平性审计与算法政策制定提供了坚实的理论基石。

保证目标组合	适用决策规则类别	计算可行性	理论误差下界 / 复杂度上界	核心依赖假设
MA \(\implies\) MAD	\(\varepsilon\)-近似仿射 (ITA 规则)	多项式时间高效可解	误差界 \(\leq \frac{k\alpha}{\delta} + 2\varepsilon\)	无额外假设 (统计成立)
阈值 MA \(\implies\) MAD	单调确定性仿射规则	多项式时间高效可解	误差界 \(\leq \frac{\alpha}{\delta} + 2\varepsilon\)	排序类型全序假设
坐标校准 + MAD	\(M\)-Lipschitz 且 \(\varepsilon\)-远离仿射	计算不可行 (Hard)	决策误差下界 \(> \frac{\varepsilon}{2}\)	存在单向函数 (OWF)
MAC + 损失极小化	任意非平凡损失 \(\ell \in \mathcal{L}_\alpha\)	计算不可行 (Hard)	相比 \(h_0\) 超额损失 \(\geq \frac{\alpha}{8} - O(\varepsilon)\)	存在单向函数 (OWF)
全多校准 \(\implies\) 损失极小化	任意损失函数 \(\ell\)	样本指数级 / 理论可行	竞争损失界 \(\leq 3k(\alpha + \lambda)\)	无密码学假设 (全称预测)

松弛算法机制	适用标签类型	损失函数约束	样本复杂度	运行时间复杂度	最终超额损失界
原始全多校准 (Canonical)	离散有限类型 \(\mathcal{T}\)	任意二元损失	\(O((1/\lambda)^k \cdot \text{poly})\)	随类别数 \(k\) 指数爆炸	\(3k(\alpha + \lambda)\)
期望标量预测器 \(\mathbb{E}_{\tilde{R}}\)	离散区间 \(\Lambda[0,1]\)	第一分量线性损失	$\tilde{O}\left(\frac{\log(	\mathcal{C}	/\delta)}{\alpha^4 \lambda^{1.5}}\right)$
损失加权预测器 \(p_{\tilde{R}, \ell}\)	任意有限类型 \(\mathcal{T}\)	训练期预先给定单一 \(\ell\)	$\tilde{O}\left(\frac{\log(	\mathcal{C}	/\delta)}{\alpha^4 \lambda^{1.5}}\right)$
结果不可区分性 (Sample OI)	任意有限类型 \(\mathcal{T}\)	训练期给定损失族 \(\mathcal{L}\)	$\tilde{O}\left(\frac{\log k (\log	\mathcal{C}	+ \log