# Robust Regression of General ReLUs with Queries

arXiv: https://arxiv.org/abs/2606.11130 · HTML: https://mlsanity.com/paper/2606.11130/

## 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 (most cited first, 17 of 17)

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Agnostic Learning of General ReLU Activation Using Gradient Descent](https://mlsanity.com/paper/2208.02711/) (2022)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise](https://mlsanity.com/paper/2012.10793/) (2020)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Robustly Learning Monotone Generalized Linear Models via Data Augmentation](https://mlsanity.com/paper/2502.08611/) (2025)
- [Near-optimal Active Regression of Single-Index Models](https://mlsanity.com/paper/2502.18213/) (2025)

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