research area Methods and Algorithmsconference NeurIPS
content type paperpublished November 2023

Agnostically Learning Single-Index Models using Omnipredictors

AuthorsAravind Gollakota, Parikshit Gopalan, Adam R. Klivans, Konstantinos Stavropoulos

View publication

We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable setting or required the activation to be known. Moreover, we only require the marginal to have bounded second moments, whereas all prior work required stronger distributional assumptions (such as anticoncentration or boundedness). Our algorithm is based on recent work by [GHK+23] on omniprediction using predictors satisfying calibrated multiaccuracy. Our analysis is simple and relies on the relationship between Bregman divergences (or matching losses) and ℓp distances. We also provide new guarantees for standard algorithms like GLMtron and logistic regression in the agnostic setting.

Related readings and updates.

How Global Calibration Strengthens Multiaccuracy

July 25, 2025research area Fairness, research area Methods and Algorithmsconference FOCS

Multiaccuracy and multicalibration are multigroup fairness notions for prediction that have found numerous applications in learning and computational complexity. They can be achieved from a single learning primitive: weak agnostic learning. Here we investigate the power of multiaccuracy as a learning primitive, both with and without the additional assumption of calibration. We find that multiaccuracy in itself is rather weak, but that the...

Read more

Loss Minimization through the lens of Outcome Indistinguishability

March 10, 2023research area Fairness, research area Methods and Algorithms

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...

Read more