  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.
