# Dimension-Free Decision Calibration for Nonlinear Loss Functions

arXiv: https://arxiv.org/abs/2504.15615 · HTML: https://mlsanity.com/paper/2504.15615/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 28 references that are in the map.
- First posted on arXiv 22 Apr 2025.

## Builds on (most cited first, 20 of 20)

- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [Mechanisms for a No-Regret Agent: Beyond the Common Prior](https://mlsanity.com/paper/2009.05518/) (2020)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses](https://mlsanity.com/paper/2502.12564/) (2025)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs](https://mlsanity.com/paper/2411.17582/) (2024)
- [Efficient Prior-Free Mechanisms for No-Regret Agents](https://mlsanity.com/paper/2311.07754/) (2023)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)

## Built on by (most cited first, 2 of 2)

- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Truthful Calibration Errors for Multi-Class Prediction](https://mlsanity.com/paper/2510.06388/) (2025)

## Abstract (arXiv)

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.