Deep learning thrives on massive datasets, but training models on millions of examples is computationally exhausting, financially costly, and environmentally taxing. Traditional approaches to reducing dataset size rely on simple heuristics—such as random sampling or filtering by high loss values—which often ignore the underlying geometry of the optimization landscape.
Gradient-matching coreset selection offers a more principled alternative. Instead of treating data pruning as a static filtering problem, it frames data selection through the lens of optimization dynamics. The core insight is simple: if a tiny, carefully weighted subset of data can replicate the gradient of the full dataset, training on this subset will steer the model along the exact same optimization trajectory as training on the complete dataset.
The Core Intuition: Tracking the Optimization Trajectory
In standard gradient descent, a model updates its parameters $\theta$ at each step by moving in the direction of the full-dataset gradient:
$$\theta_{t+1} = \theta_t - \eta \nabla L_{\text{full}}(\theta_t)$$
If we can find a small subset of samples $S$ and assign them non-negative importance weights $w_i$, we can compute a weighted subset gradient. If this subset gradient closely matches the full gradient, the parameter update remains virtually unchanged:
$$\sum_{i \in S} w_i \nabla L_i(\theta_t) \approx \nabla L_{\text{full}}(\theta_t) \implies \theta_{t+1} \approx \theta_t - \eta \sum_{i \in S} w_i \nabla L_i(\theta_t)$$
As demonstrated by Baharan Mirzasoleiman et al. in their framework CRAIG (Coresets for Data-efficient Training of Machine Learning Models), this gradient matching approach ensures that optimization steps taken on the subset closely track the trajectory of full-batch gradient descent. By training on these representative "coresets," models can achieve significant training speedups while keeping final accuracy within a fraction of a percent of the full-dataset baseline.
Building on this, Krishnateja Killamsetty et al. introduced GRAD-MATCH (GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training), generalizing this formulation to match either the training gradient or a validation gradient. They showed that deep learning models can reach peak performance without processing the entire dataset, provided the subset selection captures the essential gradient information.
Formulating Selection as Sparse Approximation
To find this optimal subset, the selection process is framed as a sparse approximation or signal reconstruction problem. As noted by Lukas Balles et al. in A Negative Result on Gradient Matching for Selective Backprop, we treat the full-batch gradient as a target signal we want to reconstruct using a linear combination of a few dictionary elements (the individual sample gradients).
Mathematically, the objective is to minimize the squared difference between the weighted subset gradient and the target gradient:
$$\min_{w, S} \left\| \sum_{i \in S} w_i \nabla L_i(\theta) - \nabla L_{\text{target}}(\theta) \right\|^2 \quad \text{subject to } |S| \le k$$
By minimizing this error, the selection mechanism forces the chosen subset to match both the direction and magnitude of the aggregate learning signal. As Hongpeng Guo et al. highlight in FedCore: Straggler-Free Federated Learning with Distributed Coresets, matching both components ensures that updates derived from the subset remain structurally aligned with the true optimization path, preventing the model from diverging or stalling.
Solving the Combinatorial Problem Greedily
Finding the absolute best subset $S$ of size $k$ is an NP-hard combinatorial problem. To make selection computationally viable, researchers leverage greedy optimization algorithms. Instead of evaluating all possible combinations, the algorithm builds the subset iteratively, picking the single data point at each step that most significantly reduces the residual gradient error.
Amit Dhurandhar et al. utilized this strategy in ProtoDash (Efficient Data Representation by Selecting Prototypes with Importance Weights), demonstrating that using the gradient of the objective function as a look-ahead heuristic provides a massive computational speedup over full quadratic programming. This allows the selection phase to scale to large datasets that were previously too massive for standard prototype selection.
Similarly, Durga S et al. applied a greedy algorithm in Gradient Coreset for Federated Learning to iteratively minimize the residual difference between a local subset gradient and a target reference gradient. To scale gradient matching to massive instruction tuning datasets for large language models, Jipeng Zhang et al. developed TAGCOS (TAGCOS: Task-agnostic Gradient Clustered Coreset Selection for Instruction Tuning Data). TAGCOS first clusters gradient features and then uses a greedy selection algorithm to identify a minimal set of samples that best approximate the average gradient of each cluster, drastically reducing data redundancy.
Why It Works Across Diverse Domains
The beauty of gradient matching is its generality. Because it operates directly on the optimization signal, it does not care about the underlying data modality—whether it is text, audio, graphs, or reinforcement learning trajectories.
Preserving Performance Rankings
Because gradient matching preserves the trajectory of optimization, it also preserves the relative performance ranking of different model configurations. This insight is what powers AUTOMATA, a framework developed by Guttu Sai Abhishek et al. (AUTOMATA: Gradient Based Data Subset Selection for Compute-Efficient Hyper-parameter Tuning). By evaluating hyperparameter configurations on a tiny, gradient-matched fraction of the data, AUTOMATA identifies optimal settings at a fraction of the cost, because a configuration that performs well on the coreset is mathematically guaranteed to perform well on the full dataset.
Stabilizing Complex Objectives
In fields like offline reinforcement learning, dataset quality can vary wildly. Yiqin Yang et al. (Fewer May Be Better: Enhancing Offline Reinforcement Learning with Reduced Dataset) framed reinforcement learning dataset pruning as a gradient approximation problem. By selecting a subset whose weighted gradient sum matches the full dataset, they ensured that policy training on reduced data tracks the same optimization objective while shedding harmful or redundant trajectories.
The same principle stabilizes adversarial training. Training robust models requires expensive inner-loop optimization to generate adversarial examples. Hadi M. Dolatabadi et al. (ℓ ∞-Robustness and Beyond: Unleashing Efficient Adversarial Training) accelerated this process by identifying a small, weighted subset of data that approximates the total gradient of the adversarial loss, focusing heavy computation only on the most informative samples.
Mitigating Forgetting and Filtering Noise
Gradient matching also excels at preserving past knowledge. In continual learning, models sequentially learn new tasks and suffer from "catastrophic forgetting." Lukas Balles et al. (Gradient-matching coresets for continual learning) showed that by minimizing the squared difference between a coreset gradient and the full dataset gradient of past tasks, one can curate a high-quality rehearsal memory that effectively anchors the model's optimization trajectory, preventing it from drifting away from previously learned solutions.
Finally, the geometry of gradients can act as a quality filter. When generating synthetic data to augment training, many generated samples can be noisy or ambiguous. Omead Pooladzandi et al. (Generating High Fidelity Synthetic Data via Coreset selection and Entropic Regularization) used gradient matching to filter synthetic datasets. By selecting only the synthetic points whose gradients align with the true data distribution's geometry, they ensure that the model is trained on high-fidelity samples that genuinely aid optimization rather than degrading it.
Key Foundational Work
Maximum Margin Coresets for Active and Noise Tolerant Learning (2007) — contributed 1 concept elements to this direction.
Cross-Modality Submodular Dictionary Learning for Information Retrieval (2014) — contributed 1 concept elements to this direction.