Agnostically Learning Single-Index Models using Omnipredictors
Aravind Gollakota Parikshit Gopalan Adam R. Klivans Konstantinos Stavropoulos
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 $\ell_p$ distances. We also
provide new guarantees for standard algorithms like GLMtron and logistic
regression in the agnostic setting.