mlsanityData to 14 Oct 2026

Agnostically Learning Single-Index Models using Omnipredictors

arXiv 2306.10615 ↗First posted 18 Jun 2023cs.LG cs.DS stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 11 of its 22 references that are in the map. First posted on arXiv 18 Jun 2023.

Builds on

11 of 22 references.

References · 11

  1. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 222
  2. 2022Loss Minimization through the Lens of Outcome Indistinguishabilitycited by 62
  3. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  4. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  5. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  6. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  7. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  8. 2020Approximation Schemes for ReLU Regressioncited by 34
  9. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  10. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  11. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 6; 2025: 8; 2026: 1.

16 papers.

Sort:

By area:

  1. 2024When is Multicalibration Post-Processing Necessary?cited by 18
  2. 2024Omnipredictors for Regression and the Approximate Rank of Convex Functionscited by 15
  3. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  4. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  5. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  6. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  7. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  8. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  9. 2025Improved Bounds for Swap Multicalibration and Swap Omnipredictioncited by 4
  10. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  11. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  12. 2023Agnostically Learning Multi-index Models with Queriescited by 1
4 more
  1. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  2. 2025Provably Extracting the Features from a General Superpositioncited by 1
  3. 2025Auditability and the Landscape of Distance to Multicalibrationcited by 0
  4. 2026Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Methodcited by 0