Answers are grounded in this paper and cite their sources.
This analysis explores decision calibration under nonlinear loss functions, highlighting efficient algorithms with polynomial sample complexity.
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 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.
No takes yet. Share an insight, caveat, or question.
Tang et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: