# Omnipredictors for Regression and the Approximate Rank of Convex Functions

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 26 Jan 2024.

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

- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [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)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [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)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)
- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)

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

- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Revisiting the Predictability of Performative, Social Events](https://mlsanity.com/paper/2503.11713/) (2025)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [Provable Uncertainty Decomposition via Higher-Order Calibration](https://mlsanity.com/paper/2412.18808/) (2024)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Robust Decision Making with Partially Calibrated Forecasts](https://mlsanity.com/paper/2510.23471/) (2025)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Model Ensembling for Constrained Optimization](https://mlsanity.com/paper/2405.16752/) (2024)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Testable and Actionable Calibration for Full Swap Regret](https://mlsanity.com/paper/2605.17749/) (2026)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [Prediction Is Not a Sufficient Memory State](https://mlsanity.com/paper/2610.13881/) (2026)

## Abstract (arXiv)

Consider the supervised learning setting where the goal is to learn to predict labels mathbf y given points mathbf x from a distribution. An textitomnipredictor for a class mathcal L of loss functions and a class mathcal C of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in mathcal C for every loss in mathcal L. Since the work of [GKR+21] that introduced the notion, there has been a large body of work in the setting of binary labels where mathbf y ∈ 0, 1, but much less is known about the regression setting where mathbf y ∈ [0,1] can be continuous. Our main conceptual contribution is the notion of textitsufficient statistics for loss minimization over a family of loss functions: these are a set of statistics about a distribution such that knowing them allows one to take actions that minimize the expected loss for any loss in the family. The notion of sufficient statistics relates directly to the approximate rank of the family of loss functions. Our key technical contribution is a bound of O(1/varepsilon2/3) on the ε-approximate rank of convex, Lipschitz functions on the interval [0,1], which we show is tight up to a factor of polylog (1/ε). This yields improved runtimes for learning omnipredictors for the class of all convex, Lipschitz loss functions under weak learnability assumptions about the class mathcal C. We also give efficient omnipredictors when the loss families have low-degree polynomial approximations, or arise from generalized linear models (GLMs). This translation from sufficient statistics to faster omnipredictors is made possible by lifting the technique of loss outcome indistinguishability introduced by [GKH+23] for Boolean labels to the regression setting.