Agnostically Learning Single-Index Models using Omnipredictors
This solves the problem of agnostic learning for SIMs under minimal distributional assumptions, which is incremental but important for theoretical machine learning and applications relying on such models.
The paper presents the first algorithm for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations, requiring only bounded second moments for the marginal distribution, unlike prior work that needed stronger assumptions like anticoncentration or boundedness. It achieves this by leveraging omnipredictors and calibrated multiaccuracy, with analysis based on Bregman divergences and ℓ_p distances.
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.