Robust Regression of General ReLUs with Queries

• URL: http://arxiv.org/abs/2606.11130v1
• Date: Tue, 09 Jun 2026 17:24:47 GMT
• Title: Robust Regression of General ReLUs with Queries
• Abstract summary: In the passive learning setting, recent work gave a computationally efficient algorithm that uses $poly(d,1/)$ labeled examples.<n>Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples.<n>Our main result is the first computationally efficient learner that uses $d polylog(1/)+tildeO(min1/p, 1/)$ black-box label queries.
• Score: 44.66700509667053
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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/ε)+\tilde{O}(\min\{1/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 $\tildeΩ(d/ε)$ labels, unless it draws a super-polynomial number of unlabeled examples.

Related papers

• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=1,..., n$, each assigned a positive weight.<n>A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight.<n>This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature.
  arXiv  Detail & Related papers  (2026-01-07T22:07:44Z)
• Near-Polynomially Competitive Active Logistic Regression [6.600655187282174]
  It is well known that active learning can require exponentially fewer label queries compared to passive learning.<n>We present the first algorithm that is competitive with the optimal algorithm on every input.<n>Our algorithm is based on efficient sampling and can be extended to learn more general class of functions.
  arXiv  Detail & Related papers  (2025-03-07T23:31:58Z)
• Active Learning of General Halfspaces: Label Queries vs Membership Queries [35.41111301965335]
  We show that any active learner requires label complexity of $tildeOmega(d/(log(m)epsilon))$, where $m$ is the number of unlabeled examples.<n>We give a computationally efficient learner with query complexity of $tildeO(min1/p, 1/epsilon + dcdot polylog (1/epsilon))$ achieving error guarantee of $O(opt)+epsilon$.
  arXiv  Detail & Related papers  (2024-12-31T15:40:48Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Semi-supervised Active Regression [21.51757844385258]
  This paper studies the use of partially labelled, potentially biased data for learning tasks. The learner has access to a dataset $X in mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 equation while making few additional label queries.
  arXiv  Detail & Related papers  (2021-06-12T03:28:43Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.