Loss Minimization through the lens of Outcome Indistinguishability
summary
Paper proves that requiring loss OI—Outcome Indistinguishability for a loss-derived distinguisher class—is sufficient to get an Omnipredictor, with learning complexity governed by the distinguisher class and independent of the true Bayes model. Key tools are reductions to calibration and multiaccuracy (Decision OI and Hypothesis OI), showing multicalibration is unnecessary. Instantiations include a construction for all losses, a simpler threshold multiaccuracy requirement for Lipschitz losses, and that GLM losses need only H-multiaccuracy plus calibration.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 0:20Part I Omnipredictors
- 8:49Part II Outcome Indistinguishability
- 13:05Part III Loss Indistinguishability
- 17:15Part IV Omnipredictors
- 19:51Part V Non convex loss classes
- 21:16Part VI Non convex loss classes
related talks
37mOmnipredictors
12mA Complexity-Theoretic Perspective on Fairness
40mOmnipredicting Single-Index Models with Multi-Index Models
29mEfficient Minimax Optimal Strategies for Universal Prediction
45mMulticalibration, Universal Adaptability and Causality
01h 11mA Theory of Multi-objective Machine Learning
01h 21mMulticalibration: Towards Fair Decision Making
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors