Dimension-Free Decision Calibration for Nonlinear Loss Functions

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-a classical statistical notion that requires the predictions to be unbiased conditional on the prediction values-suffices to guarantee that simple best-response to predictions is optimal. However, for high-dimensional prediction outcome spaces, obtaining an accurate calibrated predictor requires exponential computational and statistical complexity. The recent relaxation known as decision calibration [Zhao et al., 2021] circumvents this curse of dimensionality, as it only requires predictions to be unbiased conditional on the induced best-response actions-in effect ensuring 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 (e.g., RKHS-induced) 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-also known as the quantal 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 (1) determine if a predictor is decisioncalibrated, and (2) post-process the initial predictor to satisfy decision calibration without worsening accuracy. Our algorithms apply broadly to function classes that can be well-approximated by boundednorm functions in (possibly infinite-dimensional) separable RKHS; examples of such classes include piecewise linear loss functions and d-dimensional Cobb-Douglas loss functions.