🤖 machine learning

Active Regression for Single-Index Models with Unknown Link Functions

This paper presents a non-adaptive sampling algorithm that achieves a $(1+\epsilon)$ -approximation for active $\ell_p$ -regression in single-index models with unknown link functions using nearly optimal query complexity, while also establishing nearly tight lower bounds for $p>2$ to close significant gaps in the existing literature.

Original authors: Chansophea Wathanak In, Yi Li, Wai Ming Tai, Xuan Wu

Published 2026-08-04

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Chansophea Wathanak In, Yi Li, Wai Ming Tai, Xuan Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to predict the future based on a massive spreadsheet of data. The spreadsheet has thousands of rows (each a different scenario) and a few columns (the features that matter). In the world of data science, this is called a regression problem: finding the perfect rule that turns the columns into the rows. Usually, we assume the robot's brain is a simple, straight line. But the real world is messy. Sometimes the robot needs to bend that line, or snap it like a rubber band, to fit the data. This is where "single-index models" come in: they let the robot apply a flexible, wiggly function to a straight-line prediction.

The tricky part is that the robot doesn't know the shape of that wiggly function yet. It's like trying to solve a maze where you can see the walls (the data columns) clearly, but the exit (the label) is hidden behind a curtain. You can only peek at the exit by asking specific questions about individual spots. If you ask too many questions, you waste time; if you ask too few, you get lost. The big question scientists have been asking is: "What is the smartest, fastest way to peek at just the right spots to learn the rule, even when we don't know what the rule looks like?"

This paper tackles that exact puzzle. The researchers, working in the field of randomized numerical linear algebra, have developed a new method to solve these "single-index" problems much more efficiently than before. They created a clever, non-adaptive sampling algorithm—a fancy way of saying a pre-planned strategy for peeking at the hidden data. Their method works for a wide variety of error measurements (mathematical ways to measure how wrong the prediction is) and, crucially, it works even when the "link function" (the wiggly rule) is completely unknown.

Here is the magic they found: They proved that you can get a solution that is almost perfect (within a factor of $1 + \epsilon$ ) by asking a surprisingly small number of questions. Specifically, the number of questions needed grows roughly with $d^{p/2}$ (where $d$ is the number of features and $p$ is the type of error you care about) and shrinks as you allow for a bit more error ( $\epsilon$ ). For the first time, they showed that when the link function is unknown, you don't need to ask that many more questions than if you already knew the rule. They also proved that for certain types of problems, you simply cannot do better than their method; it's mathematically impossible to find a faster way.

Think of it like this: Imagine you are trying to guess the shape of a giant, invisible sculpture in a dark room by poking it with a long stick. Previous methods told you that if you didn't know the sculpture's shape, you'd have to poke it millions of times to get a good idea. This paper says, "Actually, if you poke it in the right spots—spots determined by the room's geometry—you only need to poke it a few thousand times, and you'll get a picture that's 99% accurate." They didn't just find a better way to poke; they also proved that you can't poke any fewer times and still get a good picture. This closes a huge gap in our understanding of how to learn from data when the rules of the game are a mystery.

Technical Summary: Active Regression for Single-Index Models with Unknown Link Functions

Problem Formulation

This paper addresses the active regression problem for single-index models under general $\ell_p$ -loss ( $p \ge 1$ ). The goal is to find a vector $x \in \mathbb{R}^d$ and a link function $f$ within the class of 1-Lipschitz functions ( $\text{Lip}_1$ ) that minimize the residual:
$\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|f(Ax) - b\|_p^p$
where $A \in \mathbb{R}^{n \times d}$ is a known data matrix ( $n \gg d$ ) and $b \in \mathbb{R}^n$ is a label vector. The setting is active, meaning the algorithm has full access to $A$ but can only access $b$ via coordinate queries. The specific challenge addressed is the case where the link function $f$ is unknown, contrasting with prior work that assumed $f$ was known.

Methodology

Upper Bound: Non-Adaptive Sampling Algorithm

The authors propose a non-adaptive sampling algorithm (Algorithm 2) that extends the framework of Lewis weight sampling used in linear regression and known-link single-index regression.

Lewis Weight Construction: The algorithm computes Lewis weights $w_1, \dots, w_n$ for the matrix $A$ .
Row Splitting and Sampling: Conceptually, the $i$ -th row of $A$ is split into $k_i \approx w_i \cdot (n/d)$ copies. These rows are sampled independently with a global probability $\alpha$ .
Sketched Optimization: The algorithm solves a regularized minimization problem on the sketched instance:
$(\hat{f}, \hat{x}) := \arg\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|S(f(Ax) - b)\|_p^p + \epsilon \|Ax\|_p^p$
where $S$ is a random diagonal sampling matrix.

Technical Analysis: Controlling the Unknown Link

The core technical contribution lies in bounding the uniform sampling error when $f$ is unknown. The analysis relies on controlling a Rademacher process $\Psi$ over the set $T \subseteq \text{Lip}_1 \times \mathbb{R}^d$ .

Symmetrization and Dudley's Integral: The error is bounded using Dudley's integral applied to a Rademacher process.
Decoupling Challenge: Unlike previous works where the index set had a product structure (allowing easy decoupling of $f$ and $x$ ), the requirement for a $(1+\epsilon)$ -approximation results in a non-rectangular index set. The authors decouple $f$ and $x$ midway through the inequality chain rather than at the set level.
Metric Entropy of $\text{Lip}_1$ : A novel contribution is the control of the metric entropy of the Lipschitz class under nonstandard weighted sup-norms. The authors introduce a covering lemma (Lemma 1.3) that bounds the covering number of $\text{Lip}_1$ under a weighted norm by the standard $L_\infty$ covering number on $[-1, 1]$ . This avoids the technical overhead of explicit discretization used in prior $p=2$ results.
Bootstrapping: A bootstrapping argument is employed to refine the solution from a constant-factor approximation to a $(1+\epsilon)$ -approximation.

Lower Bound: Hard Instance Construction

To establish tightness, the authors construct a hard instance for $p > 2$ involving:

Spherical Code: $N$ nearly orthogonal unit vectors with coherence $\tau$ .
Hidden Index: A uniformly random index $I \in [N]$ is "planted" in the response vector $b$ .
ReLU Link: The link function is fixed as $f(t) = \max\{0, t\}$ .
Short-list Guarantee: The analysis shows that any algorithm satisfying the approximation guarantee must identify a "short-list" of candidate indices containing the true $I$ . By bounding the size of this short-list and comparing the query sets of the baseline input $b(0)$ versus $b(I)$ , they derive a query lower bound using Yao's minimax theorem.

Key Contributions and Results

1. Upper Bound (Theorem 1.1 / 3.2)

The paper presents a randomized algorithm that achieves a $(1+\epsilon)$ -approximation for general $p \ge 1$ with unknown link functions.

Query Complexity: The algorithm makes $O(d^{1 \vee p/2} / \epsilon^{p \vee 2} \cdot \text{poly}(\log n))$ non-adaptive queries to $b$ .
Significance: This result strictly improves upon the only prior result for unknown links (which was limited to $p=2$ and constant-factor approximation) and matches the query complexity of the known-link case up to logarithmic factors in $n$ .

2. Lower Bound (Theorem 1.2 / 4.2)

For $p > 2$ , the paper establishes a nearly tight lower bound on the query complexity.

Complexity: Any randomized algorithm achieving the approximation guarantee must query $\Omega_p(d^{p/2} / (\epsilon^p (\log(d/\epsilon))^{p/2}))$ entries of $b$ in the worst case (assuming $d \gtrsim \log(d/\epsilon)$ ).
Significance: This closes the gap for $p > 2$ , showing that the existing upper bound of $\tilde{O}(d^{p/2}/\epsilon^p)$ is tight up to logarithmic factors, even for adaptive queries.

Significance and Claims

The paper claims to close much of the remaining gap in active $\ell_p$ -regression for single-index models.

Generalization: It extends the understanding of active regression from linear models and known-link single-index models to the more challenging setting of unknown link functions for general $p \ge 1$ .
Optimality: By providing matching upper and lower bounds (up to logarithmic factors) for $p > 2$ and improving the approximation guarantee for $p=2$ , the work provides a comprehensive characterization of the query complexity for this problem class.
Technical Novelty: The development of a covering lemma for Lipschitz functions under weighted norms and the handling of non-rectangular index sets in the Dudley integral analysis are presented as key technical advances that enable the general $p$ result.

The authors explicitly note that while the $\log n$ factors in the upper bound are currently present due to the intrinsic covering number of Lipschitz functions, it remains an open question whether these factors can be removed. The paper does not propose experimental validations or specific real-world applications beyond the theoretical framework of randomized numerical linear algebra.