Research map / Learning theory and algorithms / Sample complexity
Robust Regression of General ReLUs with Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first computationally efficient agnostic learner for general (biased) ReLU regression under Gaussian marginals using d·polylog(1/ε)+Õ(min{1/p,1/ε}) black-box label queries, with near-matching query lower bounds and a separation from pool-based active learning.
Problem
Agnostically learning general ReLUs (arbitrary bias threshold t>0) under Gaussian marginals with squared loss, where passive learners need poly(d,1/ε) labels; the question is the label complexity when black-box label queries are allowed.
Approach
Projected gradient descent on the sphere for the direction w, with gradient variance reduced by querying points in the region {w·x > t} (rejection sampling where the ReLU is active), and a separate gradient-based update of (r,t) using a truncated-label warm start from halfspace learning; a new query-based hypothesis selection procedure replaces costly validation.
Key results
- Algorithm uses d·polylog(R²/ε)+Õ(min{1/p,R²/ε}) queries and achieves error O(opt)+ε under Gaussian marginals for general ReLUs.
- Query lower bound Ω̃(1/p^{1-o(1)}+d) shows the query complexity is near-optimal even ignoring computation.
- Pool-based active learning requires Ω̃(d/(p log m)) labels in the realizable setting, unless the pool is super-polynomially large.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive black-box queries instead of passive examples | General agnostic ReLU regression under Gaussian marginals · Gaussian general agnostic ReLU regression | label/query complexity: \tilde{\Theta}(d/\epsilon) passive labels; QueryLearning uses \tilde{O}_\delta(\min\{1/p, R^2/\epsilon\} + d\cdot\mathrm | Helped |
| restrict label queries to a pool of m unlabeled examples | Pool-based active ReLU regression · Gaussian realizable pool-based active ReLU regression | label queries: \tilde{\Omega}(d/(p\log(m))) | Hurt |
Surprising findings
- Passive-setting and warm-start ideas for halfspaces do not directly transfer to L2 loss; a truncated-label reduction and a new query-based hypothesis selection are needed.
- Query access is essentially necessary to improve label complexity over passive learning for general ReLUs, since pool-based active learning cannot match the query bound.
Limitations
- Results are theoretical; no experiments are reported.
- Dependence on the norm bound R² appears through rescaling of the error parameter.
Experimental setup
Metrics: squared loss error relative to opt query complexity
Baselines: passive agnostic ReLU regression algorithms pool-based active learning
Builds on: halfspace learning with queries Ornstein-Uhlenbeck semigroup analysis
Closest papers by meaning
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.88)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.87)
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.85)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.85)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.85)
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.