Active Regression via Linear-Sample Sparsification

arXiv:1711.10051 · cs.LG, cs.DS · Submitted 2026-08-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Active Regression via Linear-Sample Sparsification".

Jane: The paper was written by Xue Chen and Eric Price from Northwestern University and The University of Texas at Austin.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Alright, welcome back to the show, everyone. Today we’re digging into a paper that’s got a deceptively simple title: “Active Regression via Linear-Sample Sparsification.” Jane, I’ll be honest, when I first read that title, I thought, okay, that’s a mouthful. What does it actually mean?

Jane: It sounds like a math problem, but the core question is something we all deal with. Imagine you have a huge spreadsheet of data, thousands of rows, and you want to find the best line or curve that fits it. But you can’t afford to check every single row. You can only look at a few. The paper asks, how few labels do you actually need to get a good answer?

Tom: Right, and that’s the “active” part. You get to choose which rows to look at, rather than just grabbing a random handful. The old approach, which people have used for years, was to sample based on something called leverage scores. That’s a fancy way of saying, focus on the rows that are most influential.

Jane: And that worked, but it had a catch. It needed a bit more than the bare minimum number of samples. There was this annoying extra factor of log d, where d is the number of features. Think of it like trying to collect all the cards in a set. You might get duplicates before you have one of everything.

Tom: Exactly, the coupon collector problem. The paper’s big win is that they get rid of that log factor entirely. They show you only need on the order of d samples, which is the theoretical minimum. No more wasted effort on duplicates.

Jane: And that’s a big deal because d is the number of columns in your spreadsheet, the number of features. If you have a hundred features, you need roughly a hundred labels, not a hundred times the log of a hundred, which would be more like four hundred and sixty.

Tom: So they’ve hit the floor. You can’t do better than that, and they prove it with a matching lower bound. That’s the kind of result that makes a researcher’s day.

Jane: It’s a clean, tight result. And the implications go beyond just fitting lines. This same trick applies to polynomial regression, and even to some more exotic problems like finding sparse signals in continuous data.

Tom: Which is where things get really interesting. But before we get into the nitty-gritty of the algorithm, let’s talk about who’s behind this. The authors are Xue Chen from Northwestern and Eric Price from UT Austin.

Jane: Both have strong track records in this area. Eric Price, in particular, has done a lot of work on sparse Fourier transforms, which we’ll touch on later. This paper feels like a natural extension of a lot of that prior work.

Tom: Definitely. And the fact that they’ve combined a classic problem with a modern technique, that’s the recipe for a paper that’s going to be cited for a long time. So, stick around, because we’re going to unpack how they actually pulled this off.

Jane: And why it matters for anyone who’s ever had to label a dataset by hand.

Paper discussion segment 2: Tom: So, Jane, we’ve established that this paper, “Active Regression via Linear-Sample Sparsification,” gets the sample count down to the bare minimum. But how do they actually do it? What’s the secret sauce?

Jane: The secret sauce is that they don’t just pick points randomly, and they don’t pick them all from the same distribution. They use a procedure that adapts. It looks at the points it has already chosen, and then it changes the odds of where to sample next.

Tom: Right, it’s like a smart dart player. Instead of throwing darts at the whole board, they start by hitting the center, then they adjust their aim based on where the last dart landed to cover the whole board efficiently.

Jane: That’s a good way to put it. The technical term for this is a “well-balanced sampling procedure.” The paper defines it carefully, but the intuition is that you want your sample to do two things at once. First, it has to preserve the shape of the data, so you can still find the right answer. Second, it has to keep the noise from blowing up in your face.

Tom: And that second part is crucial. If you sample too aggressively in one area, you might get a great estimate of the signal there, but a tiny bit of noise in that area could completely throw off your answer. The procedure has to balance those two forces.

Jane: Exactly. They use a randomized version of a known algorithm for spectral sparsification. That’s a technique from graph theory, but here it’s applied to matrices. The algorithm builds up a small set of rows that approximates the whole matrix’s behavior.

Tom: And the key insight is that the randomness isn’t just for show. It’s what protects you from adversarial noise. If the sampling were deterministic, a clever adversary could put all the noise in the spots you’re guaranteed to sample, and you’d be doomed.

Jane: So the randomness is a feature, not a bug. It makes the algorithm robust. And the paper shows that with this adaptive procedure, you get the guarantee you want with only O(d) samples, which, as we said, is optimal.

Tom: And they don’t just stop at the theoretical guarantee. They also show how to compute the answer efficiently. You don’t have to invert a giant matrix; you can use a simple iterative method that gets you close enough, fast.

Jane: That’s the kind of practical detail that makes a paper useful, not just interesting. It’s one thing to say, “this is possible in theory.” It’s another to say, “here’s a concrete algorithm that runs quickly.”

Tom: So, we’ve got the core algorithm. But the paper doesn’t stop there. It goes on to tackle a harder version of the problem where you don’t even know the distribution of your data. That’s where things get really wild.

Jane: Right, that’s the inductive setting. You’re not just trying to fit the points you have; you’re trying to make predictions about points you haven’t seen yet. That’s a much more realistic problem.

Tom: And that’s where we’re headed next. Let’s take a quick break, and when we come back, we’ll talk about how they handle that unknown distribution.

Paper discussion segment 3: Tom: Welcome back. We’re still on “Active Regression via Linear-Sample Sparsification.” So, Jane, we talked about the fixed case, where you know the distribution of your data. But what if you don’t? What if you’re just handed a pile of unlabeled points?

Jane: That’s the more common scenario in the real world. You have a bunch of emails, but you don’t know the overall distribution of topics. You have a bunch of patient records, but you don’t know the distribution of symptoms. The paper handles this by splitting the problem into two stages.

Tom: Two stages, okay. So, first, you take a bunch of unlabeled samples just to get a feel for the data. You don’t need labels for those, they’re cheap. Then, you use that information to decide which points are worth paying for labels on.

Jane: Exactly. They show that you need a certain number of unlabeled samples, which depends on the “condition number” of the problem. That’s a measure of how hard the problem is, how much the functions in your family can wiggle around. But the number of labels you need is still just O(d).

Tom: So, the unlabeled samples are cheap, and the labels are expensive. And they show that the number of cheap samples you need is essentially the same as if you had labeled everything. There’s no penalty for being smart about it.

Jane: Right. And this applies to a really cool example: polynomial regression. Suppose you’re trying to fit a degree-d polynomial to data on a line. The paper’s method will get you a good fit with only O(d) labels, no matter how you’re sampling the x-values, as long as you have enough unlabeled points.

Tom: And that’s a big improvement over the old way, which would have needed O(d log d) labels. For a degree ten polynomial, that’s the difference between ten labels and, like, twenty-three. It’s a real saving.

Jane: But the paper goes even further. It applies this same idea to a completely different problem: finding sparse signals in a continuous domain. This is the part that got me really excited.

Tom: Oh, the sparse Fourier transform part. That’s where things get spicy. You’re not looking for a polynomial anymore. You’re looking for a signal that’s a sum of a few sine waves, but you don’t know their frequencies.

Jane: And the frequencies can be any real number, not just nice, round numbers. That makes the problem much harder. The condition number of this problem is huge, which would normally mean you need a ton of samples.

Tom: But they show that by using a cleverly chosen sampling distribution, you can reduce the effective difficulty. They prove a bound on how much the signal can change from point to point, and that lets them design a sampling scheme that’s much more efficient.

Jane: The result is that you can recover the signal with a number of samples that’s polynomial in k, the number of sine waves, and only logarithmic in the frequency range. That’s a massive improvement over what was known before.

Tom: And this isn’t just a theoretical curiosity. Sparse Fourier transforms are used in all sorts of applications, from medical imaging to radar to audio processing. Anything where you’re trying to pull a few clean frequencies out of a noisy mess.

Jane: So, the paper isn’t just about fitting lines. It’s about a general principle for how to sample data smartly, and it has implications for a whole range of signal processing problems.

Tom: It’s a powerful toolkit. And we’ve only scratched the surface. Let’s bring in the rest of the team to get their take on what this means for the future.

Conclusion: Tom: Alright, we’re wrapping up our discussion of “Active Regression via Linear-Sample Sparsification.” Jane, give us the one-minute version.

Jane: The paper shows that for a huge class of problems, you only need a linear number of labels, which is the absolute minimum. It does this with a clever adaptive sampling scheme that balances signal preservation with noise control.

Tom: And it doesn’t just work for linear regression. It works for polynomial regression, and it even gives a big boost to the sparse Fourier transform problem. That’s a lot of bang for your buck.

Jane: It’s a paper that’s both theoretically deep and practically relevant. The lower bounds match the upper bounds, so we know the answer is optimal. And the algorithms are efficient enough to actually run.

Tom: So, what’s the big takeaway for our listeners? If you’re ever in a situation where labeling data is expensive, this is the kind of work that tells you exactly how few labels you can get away with.

Jane: And that’s a question that comes up everywhere, from training machine learning models to designing medical trials. Knowing the theoretical limit is the first step to building systems that work efficiently.

Tom: We’ve had Lu, Meng, and Lalam with us today, and they’ve given us some great perspectives on the practical and long-term implications. Thanks for joining us, everyone.

Jane: And thanks to our listeners for tuning in. We’re going to take a short break, and then we’ll be back with our next paper. Until then, keep asking questions, and keep sampling wisely.

Tom: See you soon.

Xue Chen, Eric Price

Northwestern University · The University of Texas at Austin

cs.LG, cs.DS

Submitted: 2026-08-14

Updated: 2026-08-17

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 80/100

The gist: Active Linear Regression on a Finite Domain In the active linear regression problem, one would like to estimate the least squares solution β* minimizing ‖Xβ − y‖22 given the entire unlabeled

Key concepts

Active Regression
This refers to the process of selecting which data points (rows) should be labeled. Instead of sampling randomly, the method intelligently chooses the most informative points to minimize required effort while maintaining accuracy.
Linear-Sample Sparsification
The paper's key finding is that only a linear number of samples (O(d)) are needed for accurate results, which is the theoretical minimum. This eliminates previous requirements for extra factors like log d.
Well-balanced sampling procedure
This adaptive technique guides the selection of data points by considering previously chosen points. It aims to both preserve the overall shape of the data and prevent noise from dominating the estimate.
Sparse Fourier Transform
A complex signal processing problem where one must find a signal composed of a few sine waves (frequencies) when those frequencies are unknown and continuous. The paper improves sample efficiency for this task.

Terminology

Summary

Summary

The paper Active Regression via Linear-Sample Sparsification by Xue Chen and Eric Price presents an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and continuous sparse Fourier transforms.

Problem 1: Active Linear Regression on a Finite Domain

In the active linear regression problem, one would like to estimate the least squares solution β* minimizing ‖Xβ − y‖22 given the entire unlabeled dataset X ∈ Rnˣd but only observing a small number of labels yi. The paper shows that O(d/ε) labels suffice to find a constant factor approximation β̃:

E[‖Xβ̃ − y‖22] ≤ 2 E[‖Xβ* − y‖22].

This improves on the best previous result of O(d log d) from leverage score sampling. The paper states this as Theorem 1.1: "Given any n × d matrix X and vector y ∈ Rn, let β* = arg min ‖Xβ − y‖22. For any ε < 1, we present an efficient randomized algorithm that looks at X and produces a diagonal matrix W S with support S ⊆ [n] of size S ≤ O(d/ε), such that β̃:= arg min ‖W S X · β − W S · y‖2 satisfies E[‖X · β̃ − X · β*‖22] ≤ ε · ‖X · β* − y‖22."

The paper notes that "The O(d log d) term in leverage score sampling comes from the coupon-collector problem, which is inherent to any i.i.d. sampling procedure. By using the randomized linear-sample spectral sparsification algorithm of Lee and Sun [LS15], we can avoid this term."

Problem 2: Generalization for Active Linear Regression (Inductive Setting)

The paper also presents results for the inductive setting, where the (x, y) pairs come from some unknown distribution over Rd × R. The goal is to output β̃ such that E[(xTβ̃ − y)2] ≤ (1 + ε) E[(xTβ* − y)2] with respect to the unknown distribution.

The main result, Theorem 1.2, states: "Let F be a linear family of functions from a domain G to C with dimension d, and consider any (unknown) distribution on (x, y) over G × C. Let D be the marginal distribution over x, and suppose it has bounded 'condition number' K:= sup h∈F:h≠0 sup x∈G h(x)2 / ‖h‖2 D. Let f* ∈ F minimize E[f(x) − y2]. For any ε < 1, there exists an efficient randomized algorithm that takes O(K log d + K/ε) unlabeled samples from D and requires O(d/ε) labels to output f̃ such that E f̃ E x∼D[f̃(x) − f*(x)2] ≤ ε · E x,y[y − f*(x)2]."

The paper explains: "Notice that if we merely want to optimize the number of labels, it is possible to take infinite number of samples from D to learn it and then query whatever desired labels on x ∈ supp(D). This is identical to the query access model, where Θ(d/ε) queries is necessary and sufficient from Theorem 1.1. On the other hand, if we focus on unlabeled sample complexity, a natural solution is to query every sample point and calculating the ERM f̃; one can show that this takes Θ(K log d + K/ε) samples [CDL13]. Thus both the unlabeled and labeled sample complexity of our algorithm are optimal up to a constant factor."

The paper provides Corollary 1.3: "Suppose that y(x) = f(x)+g(x), where f ∈ F is the 'true' signal and g is arbitrary and possibly randomized 'noise'. Then in the setting of Theorem 1.2, with ‖·‖ D defined as in (2), 1. E[‖f̃−f‖2 D] ≤ ε · E[‖g‖2 D], if each g(x) is a random variable with E x,g[g(x)] = 0. 2. Otherwise, ‖f̃−f‖ D ≤ (1 + O(ε)) · ‖g‖ D with probability 0.99."

Problem 3: Continuous Sparse Fourier Transform

The paper studies sampling methods for learning a non-linear family: k-Fourier-sparse signals in the continuous domain. The family is F = f(x) = Σⱼ=1k vⱼ · e 2πi·fⱼx fⱼ ∈ R ∩ [−F, F], Cⱼ ∈ C over the domain D uniform on [−1, 1].

The main contribution is Theorem 1.5: For any x ∈ (−1, 1), sup f∈F f(x)2 / ‖f‖2 D = O(k log k / (1 − x)).

This leads to Theorem 9.1: "For signals with k-sparse Fourier transform, E x∈[−1,1][sup f∈F f(x)2 / ‖f‖2 D] = O(k log2 k). Moreover, there exists a constant c = Θ(1) such that a distribution D F(x) = c/((1−x) log k) for x ≤ 1 − 1/(k3 log2 k), and D F(x) = c · k3 log k for x > 1 − 1/(k3 log2 k), guarantees for any f(x) = Σⱼ=1k vⱼ e 2πi·fⱼx and any x ∈ [−1, 1], f(x)2 · D(x)/D F(x) = O(k log2 k) · ‖f‖2 D."

The paper notes: "Because the frequencies fⱼ can be any real number in [−F, F], this family is not well conditioned. If all fⱼ → 0, a Taylor approximation shows that one can arbitrarily approximate any degree (k − 1) polynomial; hence K in (3) is at least Θ(k2)."

Key Technical Contributions

  1. Well-balanced sampling procedures: The paper defines a concept of well-balanced sampling procedures (Definition 2.1) that satisfy two properties: (1) with probability 0.9, the weighted samples preserve the norm of all functions in F (i.e., the matrix A has eigenvalues in [3/4, 5/4]); (2) the coefficients always have Σi αi ≤ 5/4 and αi · K Di ≤ ε/2.

  2. Recovery guarantee: Theorem 2.3 shows that for any ε-well-balanced sampling procedure P, the weighted ERM f̃ of a good execution satisfies ‖f − f̃‖2 D ≤ ε · E[y − f(x)2] in expectation.

  3. Linear-sample algorithm: Lemma 5.1 shows that there exists an efficient ε-well-balanced sampling procedure that terminates in O(d/ε) rounds with probability 1 − 1/200, based on the randomized BSS algorithm of [LS15].

  4. Optimal condition number: Lemma 6.1 shows that for any linear family F of dimension d and any distribution D, there always exists an explicit distribution D F such that the condition number K D F = d.

  5. i.i.d. sampling: Lemma 6.2 shows that m = O(K D0 log d + K D0/ε) i.i.d. random samples from any distribution D0 form an ε-well-balanced sampling procedure.

Lower Bounds

The paper provides two lower bounds:

  1. Query complexity: Theorem 8.1 states: "For any d and any ε < 1/10, there exist a distribution D and a linear family F of functions with dimension d such that for the i.i.d. Gaussian noise g(x) = N(0, 1/ε), any algorithm which observes y(x) = f(x)+g(x) for f ∈ F with ‖f‖ D = 1 and outputs f̃ satisfying ‖f − f̃‖ D ≤ 0.1 with probability ≥ 3/4, needs at least m ≥ 0.8d/ε queries."

  2. Sample complexity: Theorem 8.4 states: "For any K, d, and ε > 0, there exist a distribution D, a linear family of functions F with dimension d whose condition number sup h∈F:h≠0 sup x∈G h(x)2 / ‖h‖2 D equals K, and a noise function g orthogonal to V such that any algorithm observing y(x) = f(x) + g(x) of f ∈ F needs at least Ω(K log d + K/ε) samples from D to output f̃ satisfying ‖f̃ − f‖ D ≤ 0.1√ε · ‖g‖ D with probability 3/4."

The paper summarizes: "We first prove a lower bound on the query complexity using information theory. The Shannon-Hartley Theorem indicates that under the i.i.d. Gaussian noise N(0, 1/ε), for a function f with f(x) ≤ 1 at every point x, any observation y(x) = f(x) + N(0, 1/ε) obtains O(ε) information about f. Because the dimension of F is d, this indicates omega(d/ε) queries is necessary to recover a function in F. Next, for any K, d, and ε we construct a distribution D and dimension-d linear family F with condition number K over D, such that the sample complexity of achieving (2) is Ω(K log d + K/ε). The first term comes from the coupon collector problem, and the second comes from the above query bound."

Active Learning Algorithm

The paper presents Algorithm 3 for regression over an unknown distribution D. It takes m0 = O(K log d + K/ε) unlabeled samples from D, defines D0 as the uniform distribution over these samples, and then uses D0 to simulate D in a well-balanced sampling procedure P. The proof shows that with probability at least 1 − 2·10−3, the empirical norms approximate the true norms, and the final ERM f̃ satisfies the desired guarantee.

Sparse Fourier Transform Algorithm

The paper presents Algorithm 5 for recovering k-sparse Fourier transforms. It samples m = O(k4 log3 k + k2 log2 k · log(F/εT)) random samples from D F, queries the labels, and then searches over a net of frequencies to find the best k-sparse signal. Corollary 9.7 states that this algorithm outputs f̃ satisfying E x∼[−T,T][f̃(x) − f(x)2] ≲ E x∼[−T,T][g(x)2] + ε · E x∼[−T,T][f(x)2] with probability 0.9.

The paper notes: We believe that this sampling approach directly translates to improvements in the polynomial time recovery algorithm of [CKPS16], but that algorithm is quite complicated so we leave this for future work.

Improvements for AI systems

Based on the paper, here are specific improvements for AI systems:

Improvement: Replace standard leverage score sampling (O(d log d) labels) with the paper's linear-sample sparsification approach (O(d) labels).

What the improved AI system can do:

  • Given an unlabeled dataset X ∈ R(n×d), select only O(d/ε) points to label while achieving a (1+ε)-approximation of the optimal least-squares solution

  • Avoid the coupon-collector overhead inherent in i.i.d. sampling

  • Handle adversarial noise robustly (unlike deterministic sparsification methods)

  • Achieve optimal query complexity matching the information-theoretic lower bound of Ω(d/ε)

Sources

Related papers