# Omnipredictors for Constrained Optimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 15 Sep 2022.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees](https://mlsanity.com/paper/1806.06055/) (2018)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [Learning Optimal Fair Policies](https://mlsanity.com/paper/1809.02244/) (2018)
- [Average Individual Fairness: Algorithms, Generalization and Experiments](https://mlsanity.com/paper/1905.10607/) (2019)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Probably Approximately Metric-Fair Learning](https://mlsanity.com/paper/1803.03242/) (2018)
- [Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability](https://mlsanity.com/paper/2203.04536/) (2022)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)

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

- [When Does Optimizing a Proper Loss Yield Calibration?](https://mlsanity.com/paper/2305.18764/) (2023)
- [Aleatoric and Epistemic Discrimination: Fundamental Limits of Fairness Interventions](https://mlsanity.com/paper/2301.11781/) (2023)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Generative Models of Huge Objects](https://mlsanity.com/paper/2302.12823/) (2023)
- [Multigroup Robustness](https://mlsanity.com/paper/2405.00614/) (2024)
- [Model Ensembling for Constrained Optimization](https://mlsanity.com/paper/2405.16752/) (2024)
- [Feature Importance Disparities for Data Bias Investigations](https://mlsanity.com/paper/2303.01704/) (2023)
- [On the Convergence of Multicalibration Gradient Boosting](https://mlsanity.com/paper/2602.06773/) (2026)
- [On the Meta-Design of Allocation Problems](https://mlsanity.com/paper/2602.08786/) (2026)
- [Augmented Feature Boosting for Multicalibration](https://mlsanity.com/paper/2609.33891/) (2026)

## Abstract (arXiv)

The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wieder ITCS 2021), suggested a new paradigm for loss minimization. Rather than learning a predictor based on a known loss function, omnipredictors can easily be post-processed to minimize any one of a rich family of loss functions compared with the loss of hypotheses in a class mathcal C. It has been shown that such omnipredictors exist and are implied (for all convex and Lipschitz loss functions) by the notion of multicalibration from the algorithmic fairness literature. In this paper, we introduce omnipredictors for constrained optimization and study their complexity and implications. The notion that we introduce allows the learner to be unaware of the loss function that will be later assigned as well as the constraints that will be later imposed, as long as the subpopulations that are used to define these constraints are known. We show how to obtain omnipredictors for constrained optimization problems, relying on appropriate variants of multicalibration. We also investigate the implications of this notion when the constraints used are so-called group fairness notions.