Research map / Learning theory and algorithms / Sample complexity
Near-optimal Active Regression of Single-Index Models
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 (1+ε)-approximation algorithm for active regression of Lipschitz single-index models using Õ(d^{p/2∨1}/ε^{p∨2}) entry queries to b, with matching lower bounds up to logs for p in [1,2].
Problem
Active regression for single-index models min_x ||f(Ax)-b||_p with Lipschitz f, where entries of b are queried at cost and the goal is to minimize queries while achieving (1+ε)-approximation.
Approach
Uses Lewis-weight row sampling with a regularized objective ||S(f(Ax)-b)||_p^p + ε||Ax||_p^p, a bootstrapping argument that iteratively shrinks the bounded domain using a refined Dudley-integral concentration bound (with an F-restricted domain), and a two-stage sampling matrix to remove dependence on n; matching hard instances are built from two-point distributions and a locus-based reduction.
Key results
- Algorithm achieves (1+ε)-approximation with Õ(d^{p/2∨1}/ε^{p∨2}) queries to entries of b, improving over prior constant-factor results requiring ~d/ε^4 queries for p=2.
- Lower bound Ω(d/ε^2) for p in [1,2] matches the upper bound up to logarithmic factors.
- Lower bound Ω(d/ε^p) for p>2 matches the ε-dependence of the upper bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use regularized regression with τ = ε and iteratively tighten the solution domain using the error guarantee | Active regression for single-index models · Single-index regression, 1 ≤ p ≤ 2 | queries to b: \frac{d}{\varepsilon^4}\poly\log n to \frac{d}{\varepsilon^3}\poly\log n; O(d/\varepsilon^2 \poly\log n) | Helped |
Surprising findings
- Accommodating a general Lipschitz f raises the epsilon dependence from 1/ε to 1/ε^2 (p≤2) and 1/ε^p (p>2) relative to canonical active regression.
Limitations
- Assumes access to an oracle solver for the (possibly nonconvex) regression subproblem.
- Upper bound for p>2 is not matched in the d-dependence (lower bound Ω(d) vs. canonical d^{p/2}).
- Logarithmic factors remain in the query complexity.
Experimental setup
Metrics: query complexity approximation guarantee
Baselines: Musco et al. single-index active regression Chen-Derezinski active regression
Builds on: Lewis weights subspace embeddings active regression for l_p regression (Chen and Derezinski) single-index model active regression (Musco et al.) Dudley's integral
Closest papers by meaning
- Active Regression for Single-Index Models with Unknown Link Functions (ICML 2026 · similarity 0.91)
- Online Active Regression (ICML 2022 · similarity 0.87)
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.84)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.83)
- Robustly Learning Single-Index Models via Alignment Sharpness (ICML 2024 · similarity 0.83)
- Robust Regression of General ReLUs with Queries (NeurIPS 2025 · similarity 0.83)
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.