# Loss Minimization through the Lens of Outcome Indistinguishability arXiv: https://arxiv.org/abs/2210.08649 ยท HTML: https://mlsanity.com/paper/2210.08649/ ## Key facts - Cited by 62 papers in the map (data through 14 Oct 2026). - Builds on 11 of its 52 references that are in the map. - First posted on arXiv 16 Oct 2022. ## Builds on (most cited first, 11 of 11) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018) - [An elementary introduction to information geometry](https://mlsanity.com/paper/1808.08271/) (2018) - [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020) - [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021) - [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022) - [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021) - [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016) - [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022) - [Patterns, predictions, and actions: A story about machine learning](https://mlsanity.com/paper/2102.05242/) (2021) - [Multicalibrated Partitions for Importance Weights](https://mlsanity.com/paper/2103.05853/) (2021) ## Built on by (most cited first, 30 of 62) - [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022) - [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023) - [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024) - [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023) - [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023) - [When Does Optimizing a Proper Loss Yield Calibration?](https://mlsanity.com/paper/2305.18764/) (2023) - [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023) - [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024) - [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023) - [When is Multicalibration Post-Processing Necessary?](https://mlsanity.com/paper/2406.06487/) (2024) - [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023) - [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) - [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023) - [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) - [Tractable Agreement Protocols](https://mlsanity.com/paper/2411.19791/) (2024) - [Revisiting the Predictability of Performative, Social Events](https://mlsanity.com/paper/2503.11713/) (2025) - [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022) - [Oracle Efficient Algorithms for Groupwise Regret](https://mlsanity.com/paper/2310.04652/) (2023) - [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025) - [Networked Information Aggregation via Machine Learning](https://mlsanity.com/paper/2507.09683/) (2025) - [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024) - [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025) - [When does a predictor know its own loss?](https://mlsanity.com/paper/2502.20375/) (2025) - [Three Types of Calibration with Properties and their Semantic and Formal Relationships](https://mlsanity.com/paper/2504.18395/) (2025) - [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025) - [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025) - [A Perfectly Truthful Calibration Measure](https://mlsanity.com/paper/2508.13100/) (2025) - [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025) ## Abstract (arXiv) We present a new perspective on loss minimization and the recent notion of Omniprediction through the lens of Outcome Indistingusihability. For a collection of losses and hypothesis class, omniprediction requires that a predictor provide a loss-minimization guarantee simultaneously for every loss in the collection compared to the best (loss-specific) hypothesis in the class. We present a generic template to learn predictors satisfying a guarantee we call Loss Outcome Indistinguishability. For a set of statistical tests--based on a collection of losses and hypothesis class--a predictor is Loss OI if it is indistinguishable (according to the tests) from Nature's true probabilities over outcomes. By design, Loss OI implies omniprediction in a direct and intuitive manner. We simplify Loss OI further, decomposing it into a calibration condition plus multiaccuracy for a class of functions derived from the loss and hypothesis classes. By careful analysis of this class, we give efficient constructions of omnipredictors for interesting classes of loss functions, including non-convex losses. This decomposition highlights the utility of a new multi-group fairness notion that we call calibrated multiaccuracy, which lies in between multiaccuracy and multicalibration. We show that calibrated multiaccuracy implies Loss OI for the important set of convex losses arising from Generalized Linear Models, without requiring full multicalibration. For such losses, we show an equivalence between our computational notion of Loss OI and a geometric notion of indistinguishability, formulated as Pythagorean theorems in the associated Bregman divergence. We give an efficient algorithm for calibrated multiaccuracy with computational complexity comparable to that of multiaccuracy. In all, calibrated multiaccuracy offers an interesting tradeoff point between efficiency and generality in the omniprediction landscape.