mlsanityData to 14 Oct 2026

Robust Regression of General ReLUs with Queries

arXiv 2606.11130 ↗First posted 9 Jun 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses poly(d,1/ε) labeled examples and outputs a hypothesis with error O(opt)+ε, where opt is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses d polylog(1/ε)+tildeO(min1/p, 1/ε) black-box label queries, where p is the bias of the target function, and achieves error O(opt)+ε. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires tildeOmega(d/ε) labels, unless it draws a super-polynomial number of unlabeled examples.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 17 of its 32 references that are in the map. First posted on arXiv 9 Jun 2026.

Builds on

17 of 32 references.

References · 17

  1. 2014Minimax Analysis of Active Learningcited by 61
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  4. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  5. 2020Approximation Schemes for ReLU Regressioncited by 34
  6. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  7. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  8. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  9. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  10. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  11. 2020On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecited by 11
  12. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
5 more
  1. 2024Active Learning of General Halfspaces: Label Queries vs Membership Queriescited by 6
  2. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  3. 2024Active Learning with Simple Questionscited by 4
  4. 2025Robustly Learning Monotone Generalized Linear Models via Data Augmentationcited by 3
  5. 2025Near-optimal Active Regression of Single-Index Modelscited by 2

Built on by

Not cited yet.