# Omnipredicting Single-Index Models with Multi-Index Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 20 Nov 2024.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Robustly Learning Single-Index Models via Alignment Sharpness](https://mlsanity.com/paper/2402.17756/) (2024)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [The PAV algorithm optimizes binary proper scoring rules](https://mlsanity.com/paper/1304.2331/) (2013)

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

- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Robustly Learning Monotone Single-Index Models](https://mlsanity.com/paper/2508.04670/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Testable and Actionable Calibration for Full Swap Regret](https://mlsanity.com/paper/2605.17749/) (2026)
- [Optimal Recalibration of an Online Predictor](https://mlsanity.com/paper/2607.19689/) (2026)

## Abstract (arXiv)

Recent work on supervised learning [GKR+22] defined the notion of omnipredictors, i.e., predictor functions p over features that are simultaneously competitive for minimizing a family of loss functions L against a comparator class C. Omniprediction requires approximating the Bayes-optimal predictor beyond the loss minimization paradigm, and has generated significant interest in the learning theory community. However, even for basic settings such as agnostically learning single-index models (SIMs), existing omnipredictor constructions require impractically-large sample complexities and runtimes, and output complex, highly-improper hypotheses. Our main contribution is a new, simple construction of omnipredictors for SIMs. We give a learner outputting an omnipredictor that is varepsilon-competitive on any matching loss induced by a monotone, Lipschitz link function, when the comparator class is bounded linear predictors. Our algorithm requires ≈ varepsilon-4 samples and runs in nearly-linear time, and its sample complexity improves to ≈ varepsilon-2 if link functions are bi-Lipschitz. This significantly improves upon the only prior known construction, due to [HJKRR18, GHK+23], which used gtrsim varepsilon-10 samples. We achieve our construction via a new, sharp analysis of the classical Isotron algorithm [KS09, KKKS11] in the challenging agnostic learning setting, of potential independent interest. Previously, Isotron was known to properly learn SIMs in the realizable setting, as well as constant-factor competitive hypotheses under the squared loss [ZWDD24]. As they are based on Isotron, our omnipredictors are multi-index models with ≈ varepsilon-2 prediction heads, bringing us closer to the tantalizing goal of proper omniprediction for general loss families and comparators.