🤖 machine learning

Active Learning with Low-Rank Structure for Data Selection

This paper introduces a new data selection framework that leverages low-rank approximation and residual-based sampling to efficiently choose a weighted subset of data points, offering theoretical guarantees and empirical improvements over traditional clustering-based methods for datasets with global algebraic structure.

Original authors: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

Published 2026-06-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

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 a chef trying to create the world's best soup. You have a massive warehouse filled with thousands of different vegetables, spices, and broths (your dataset). To make the perfect soup, you need to taste and mix all of them. But here's the problem: your kitchen is tiny, your stove is weak, and you only have a few hours. Cooking with the entire warehouse is impossible.

You need to pick a small, perfect handful of ingredients that will give you the exact same flavor as the whole warehouse. This is the Data Selection problem.

The Old Way: Picking by "Distance"

For a while, the best chefs used a method called Clustering. Imagine you walk into the warehouse and pick one vegetable from every distinct corner. You grab a carrot from the north, a potato from the south, a pepper from the east, and a tomato from the west.

The logic was: "If I pick things that are far apart from each other, I must be covering all the bases." This worked okay for simple recipes. But in the modern world, where data is huge and complex (like a warehouse with millions of items), this method has a flaw. It focuses on where the items are, not what they actually do. You might end up with a bag full of different-looking vegetables that all taste exactly the same, while missing the one secret spice that actually defines the soup's flavor.

The New Way: Picking by "Structure"

The authors of this paper say: "Stop looking at where the vegetables are standing. Look at the shape of the flavor."

They propose a new method based on Low-Rank Structure.
Think of your soup ingredients not as individual items, but as a complex 3D sculpture. Even though the sculpture looks complicated, it might actually be built from just a few main beams and supports. The rest is just decoration.

The Main Beams (Low-Rank): These are the most important directions of flavor. If you get these right, you get the soup right.
The Decoration (Residuals): These are the tiny, unimportant details that don't change the taste much.

The authors' method uses a mathematical "X-ray" (called Low-Rank Approximation) to find those main beams. Instead of picking vegetables that are far apart, they pick the specific ingredients that hold up the main beams of the flavor structure.

How They Do It: The "Sensitivity" Scale

To figure out which ingredients are the "main beams," they use a technique called Sensitivity Sampling.

Imagine you have a giant scale. You put a vegetable on it, and the scale tells you: "If you leave this out, how much will the soup's flavor change?"

If the flavor changes a lot, the scale goes off the charts. That vegetable is highly sensitive (very important).
If the flavor barely changes, the scale stays low. That vegetable is low sensitivity (redundant).

Their algorithm calculates this score for every single item in the warehouse, then randomly picks a small group of ingredients, but weighted by how important they are. You are much more likely to pick the "high sensitivity" items.

The Results: Why It Matters

The paper tested this idea in two ways:

The Credit Card Test: They tried to predict who would miss a credit card payment using a standard financial dataset. Their "Low-Rank" method picked a small group of customers that predicted the outcome much better than the old "Clustering" method or just picking randomly.
The Giant Brain Test (LLMs): They tried to teach a massive AI (Llama3-8B) to do math and answer questions. Training the AI on the whole dataset takes forever and costs a fortune. By using their method to pick just 6% to 25% of the data, they trained the AI to be smarter than if they had used random data or the old clustering method.

The Big Takeaway

The paper claims that for modern, massive datasets, the "shape" of the data (its algebraic structure) is more important than the "distance" between data points.

By focusing on the main structural beams of the data rather than just trying to cover all the corners, you can throw away 90% of your data and still train a machine learning model that performs just as well, or even better, than if you had used everything. It's like realizing you don't need to taste every grain of salt in the ocean to know how salty the soup is; you just need to taste the spoonful that represents the ocean's true character.

Technical Summary: Active Learning with Low-Rank Structure for Data Selection

Problem Definition

The paper addresses the data selection problem in machine learning, specifically the challenge of identifying a small, representative subset of data (a coreset) that allows for efficient training of models without significantly compromising performance. While modern datasets and foundation models have driven success, they incur steep computational costs for training and fine-tuning.

Existing approaches, such as those by Sener and Savarese [SS18] and Axiotis et al. [ACH+24], rely on clustering-based heuristics (e.g., $k$ -center or $k$ -means) applied to data embeddings. These methods assume that data possesses intrinsic geometric structure where diversity and distance between points are the primary drivers of informativeness. However, the authors argue that many modern datasets, particularly in high-dimensional spaces, exhibit global algebraic structure better captured by low-rank approximations (e.g., Principal Component Analysis) rather than local geometric clustering. Clustering methods may fail to capture dominant directions of variance, potentially missing critical components for model training.

Methodology

The paper proposes a new framework for data selection based on low-rank approximation and residual-based sensitivity sampling. The core idea is to prioritize the preservation of dominant spectral directions of the data rather than merely maximizing geometric diversity.

Theoretical Framework

The approach is grounded in the Row Subset Selection problem and loss-preserving coreset construction. The authors introduce Assumption 2.1, which posits that for a dataset $D$ with an embedding matrix, the loss function $\ell$ can be decomposed relative to a $k$ -dimensional subspace $V$ (spanned by top singular vectors or principal components):

Orthogonal Penalty: The loss deviation for a point $y$ outside the subspace $V$ is bounded quadratically by the norm of its residual component $r(y)$ orthogonal to $V$ , scaled by a constant $\lambda$ .
Subspace Approximation: Within the subspace $V$ , the loss is well-approximated by a weighted sum of losses along the basis directions, scaled by a constant $\gamma$ .

This assumption formalizes the intuition that directions orthogonal to the dominant low-rank subspace contribute less to the loss or are less informative, a property observed in tasks like PCA, matrix completion, and Low-Rank Adaptation (LoRA).

Algorithm: Sensitivity Sampling

The proposed algorithm (Algorithm 2) constructs a weighted coreset $S$ through the following steps:

Low-Rank Sketch: Compute a rank- $k$ approximation of the dataset (e.g., via SVD) to define the subspace $V$ and its basis $\{v_1, \dots, v_k\}$ .
Decomposition: For each data point $x$ , decompose it into its projection $v(x)$ onto $V$ and its residual $r(x)$ orthogonal to $V$ .
Sensitivity Score Calculation: Compute a sensitivity score $\sigma(x)$ $σ (x)$ for each point that combines:
- The weighted loss along the basis directions: $(\gamma + 1)\sum \alpha_i^2 \ell(v_i)$ .
- A penalty for the residual: $\lambda \|r(x)\|_2^2$ .
- A constant term related to the maximum loss in the basis.
Sampling: Sample points from the dataset with replacement, proportional to their normalized sensitivity scores $p(x) = \sigma(x) / \sum \sigma(y)$ .
Weighting: Assign weights $w(x) = 1/(s \cdot p(x))$ to the sampled points to ensure the estimator is unbiased.

Key Contributions

Theoretical Guarantees (Theorem 2.2 & 2.3): The paper proves that a weighted subset of size $\tilde{O}(k + 1/\varepsilon^2)$ can approximate the average loss of the full dataset within a $(1 \pm \varepsilon)$ relative error, up to an additive term proportional to the optimal rank- $k$ approximation cost $\Phi_k(D)$ .
- Theorem 2.2 guarantees this for a general weighted subset.
- Theorem 2.3 extends this to Row Subset Selection, ensuring the selected subset consists of actual data points from the input dataset.
- The error bound explicitly depends on $\Phi_k(D)$ , indicating that datasets with strong low-rank structure yield tighter bounds and more accurate coresets.
Algorithmic Innovation: The authors introduce a sensitivity sampling algorithm that leverages low-rank structure to compute importance scores, diverging from the geometric distance metrics used in clustering-based methods.
Empirical Validation: The framework is validated on both tabular data (Credit Card Default dataset) and large-scale language model fine-tuning (Llama3-8B and Qwen2.5-3B on GSM8k, ViGGO, and SQL tasks).

Experimental Results

The paper evaluates the proposed Low-Rank Sensitivity Sampling (Low-rank SS) against several baselines: Uniform Sampling, $k$ -Center, Clustering-based Sensitivity Sampling, and Graph Cut.

Tabular Data (Credit Card Dataset):
- Low-rank SS achieved the lowest approximation error in sum-of-squares, reducing error by an order of magnitude compared to random sampling and ~50% compared to clustering at small sample sizes ( $s=1000$ ).
- In downstream logistic regression, Low-rank SS achieved up to 74% test accuracy at $s=5000$ , outperforming clustering (70%) and random sampling (67%).
LLM Fine-Tuning (Llama3-8B & Qwen2.5-3B):
- On GSM8k, ViGGO, and SQL tasks, Low-rank SS consistently outperformed uniform sampling and clustering-based methods.
- For example, on ViGGO with Llama3-8B at 25% data compression, Low-rank SS achieved 77.6% accuracy versus 74.9% for clustering-based SS.
- Transferability: Subsets selected using a larger model (Llama3-8B) successfully transferred to a smaller model (Qwen2.5-3B), even outperforming subsets selected directly by the target model, suggesting the low-rank criterion captures intrinsic data properties.
- Ablation: The method proved robust to the choice of basis selection, with leverage score sampling performing best, though even uniform basis selection yielded competitive results.
Structure Analysis: Experiments on GSM8k demonstrated that the dataset exhibits a lower approximation error under low-rank assumptions compared to clustering, validating the applicability of Assumption 2.1.

Significance and Claims

The paper claims to provide a robust and efficient alternative to naive subsampling and clustering-based data selection, particularly for high-dimensional and large-scale settings.

Theoretical Contribution: It establishes rigorous guarantees for data selection under low-rank loss assumptions, linking the coreset quality directly to the dataset's alignment with a low-rank structure ( $\Phi_k(D)$ ).
Practical Impact: The authors demonstrate that simple embeddings from pre-trained models (like BERT) are sufficient to approximate the low-rank structure needed for selecting informative points, even for much larger target models (LLMs).
Efficiency: The approach avoids the computational prohibitions of computing uncertainty scores on entire datasets (common in active learning) and the redundancy issues of clustering-based batch selection.
Modesty: The authors acknowledge that while clustering retains value in some cases, their low-rank approach provides a more reliable foundation for data-efficient training on large-scale models where dominant spectral directions are critical. They do not claim universal optimality but rather a significant improvement in settings where data exhibits global algebraic structure.