GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling

*Ashish Jha, *Anh huy Phan, Razan Dibo, Valentin Leplat · 2025

Read GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling by *Ashish Jha, *Anh huy Phan, Razan Dibo, Valentin Leplat (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13653.txt.

Introduction

Ashish Jha, Anh huy Phan, Razan Dibo, and Valentin Leplat introduce GRAFT, a method for training neural networks on less data, in a two thousand twenty-five paper. Training large networks on full datasets costs heavy time, energy, and carbon emissions.

GRAFT selects a small, diverse subset from each training batch instead of using every example. It extracts a low-rank feature representation, applies a Fast MaxVol sampler to span the batch's dominant subspace, and adjusts subset size by a gradient-approximation rule. Across several benchmarks it matched or beat recent selection methods on accuracy while cutting wall-clock time and emissions.

Catalog record

CREATOR*Ashish Jha, *Anh huy Phan, Razan Dibo, Valentin Leplat
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-13653

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling *Ashish Jha, *Anh huy Phan, Razan Dibo, Valentin Leplat Abstract Training modern neural networks on large datasets is computationally and environmentally costly. We introduce GRAFT, a scalable in-training subset selection method that (i) extracts a low-rank feature representation for each per-iteration batch, (ii) applies a Fast MaxVol sampler to pick a small, diverse subset that spans the batch’s dominant subspace, and (iii) dynamically adjusts the subset size using a gradient-approximation criterion. By operating in low-rank subspaces and training on carefully chosen examples instead of full batches, GRAFT preserves the training trajectory while reducing wall-clock time, energy, and CO 2 \mathrm{CO}_{2} emissions. Across multiple benchmarks, it matches or exceeds recent selection baselines in accuracy and efficiency, while providing a favorable accuracy efficiency emissions trade-off. 1 Introduction Deep neural networks are powerful but costly to train, requiring substantial computational resources and energy, raising scalability and environmental concerns. A key driver of this cost is the large volume of training data, which increases optimization steps, memory use, and training time. Data subset selection offers a solution by using a smaller, well-chosen subset to maintain training efficiency while reducing redundancy. This can speed up training, cut energy use, and aid resource-constrained settings. However, many existing methods have drawbacks, such as costly preprocessing, reliance on proxy models, architecture restrictions, or repeated metric evaluations, limiting their flexibility. In this work, we introduce GRAFT (Gradient-Aware Fast MaxVol Technique), a scalable and lightweight framework designed to integrate subset selection directly into the training loop. GRAFT operates in two main stages - first, it extracts compact feature embeddings from per-iteration batch using a low-rank projection. This step ensures that the high-dimensional representation of the data is mapped onto a lower-dimensional subspace, capturing the most salient features with minimal redundancy. Next, GRAFT performs a fast MaxVol sampling to select a subset of examples that best span the dominant subspace of the projected features. Unlike heuristic-based selection strategies, the MaxVol criterion guarantees that the chosen subset retains maximal expressiveness in terms of subspace coverage. To maintain alignment with the training dynamics, GRAFT introduces an adaptive sampling mechanism that dynamically adjusts the number of selected samples per-iteration batch. This adjustment is guided by measuring the alignment between the gradient computed over the per-iteration subset and the gradient of the entire per-iteration batch. Specifically, GRAFT evaluates the subspace representation of the selected subset to ensure it remains representative of the full batch’s learning dynamics. If the alignment deviates, GRAFT automatically increases the subset size to better capture the gradient direction. Conversely, when alignment is strong, GRAFT reduces the subset size to optimize efficiency. This allows GRAFT to preserve training trajectory fidelity, ensuring that critical gradient information is not lost during optimization, even as subset compositions evolve throughout training. Furthermore, GRAFT introduces a fundamentally different mechanism compared to existing subset selection strategies such as GradMatch. GradMatch focuses on gradient matching, where the primary goal is to select a subset \mathcal{S} such that the gradient computed over \mathcal{S} closely approximates the gradient of the entire dataset. This is achieved through a greedy orthogonal matching pursuit (OMP) strategy that incrementally selects samples to minimize the residual gradient error. While effective, gradient matching methods require explicit comparisons of gradient vectors, which can be computationally expensive and sensitive to noise. In contrast, GRAFT shifts the focus from direct gradient matching to per-iteration subspace approximation combined with gradient alignment. Importantly, GRAFT ensures that this subspace representation remains gradient-aligned with the full per-iteration batch by dynamically adjusting the subset size based on the measured alignment. This mechanism guarantees that the chosen samples not only capture the most informative directions in the data but also maintain the critical gradient signals necessary for effective optimization. As a result, GRAFT achieves improved efficiency by reducing reliance on full-gradient computations while preserving the quality of the training trajectory, leading to more robust and stable convergence. Figure 1 : Overview of the GRAFT sampling framework. The method consists of two main stages: (1) Feature Extraction and Sample Selection , where input per-iteration batch X is transformed into a low-dimensional feature matrix Z=f(X) , followed by MaxVol-based selection of representative rows (samples); and (2) Gradient Alignment and Rank Selection , where the selected subset is evaluated based on how well its gradient aligns with the full per-iteration batch gradient. The selection rank R is dynamically adjusted using a projection error criterion. The final output is a subset of samples indexed by I=\{i_{1},\ldots,i_{R}\} used for gradient updates. This design enables GRAFT to operate efficiently within small localized data, using the local structure to guide training. By selecting representative samples in each iteration, GRAFT reduces the computational effort in subset selection while adapting to the evolving optimization landscape throughout the training. Our experimental results demonstrate that GRAFT achieves strong performance across multiple datasets and architectures, reducing both training time and energy usage with minimal accuracy degradation. These findings position GRAFT as a practical tool for sustainable and efficient deep learning on a scale. 2 Related Works Subset selection methods can be broadly categorized into pre-selection and integrated selection approaches. Pre-selection methods identify representative subsets before training. A notable example is EL2N (Early-Loss-to-Norm) scoring, defined as \text{EL2N}(x_{i})=\frac{1}{t}\sum_{k=1}^{t}|\nabla L(\theta_{k};x_{i})|^{2} , which leverages early-phase gradient norms to approximate sample informativeness [ 1 ] . Samples with higher early gradient norms tend to have a stronger impact on parameter updates and loss convergence. Forget Score [ 2 ] adopts a different strategy, measuring the misclassification frequency of samples as F(x_{i})=\sum_{k=1}^{t}\mathbb{1}[y_{i}\neq\hat{y}_{i}^{(k)}] , which favors harder-to-learn examples. However, this method is highly sensitive to noise and class imbalance, potentially overemphasizing mislabeled or ambiguous samples. Selection via Proxy (SVP) [ 3 ] introduces a lightweight proxy model f_{\phi} trained independently to estimate sample informativeness, formulated as \text{SVP}(x_{i})=L(f_{\phi}(x_{i}),y_{i}) . Although efficient, its effectiveness is tightly coupled to the fidelity of the proxy model, which may not always generalize well to the main model’s learning dynamics. DRoP [ 4 ] conceptualizes subset selection as a distributionally robust optimization (DRO) problem, expressed as \min_{\theta}\max_{q\in\mathcal{Q}}\sum_{i=1}^{n}q_{i}L(f_{\theta}(x_{i}),y_{i}) . This adversarial perspective enhances robustness against noise, but it introduces significant computational overhead due to adversarial evaluations during each optimization step. One inherent limitation of pre-selection methods is their inability to adapt to evolving training dynamics, often resulting in underfitting or misalignment with the model’s learning trajectory. In contrast, integrated selection methods address this shortcoming by adjusting subsets throughout training, aligning selection with gradient-aligned subspace approximations that reflect the current optimization landscape. This adaptability is especially critical in non-convex optimization settings where data importance fluctuates across iterations. Prominent examples include GradMatch [ 5 ] , which minimizes the gradient discrepancy |\nabla_{\theta}\mathcal{L}(S)-\nabla_{\theta}\mathcal{L}(\mathcal{X})|_{2}^{2} . Despite its theoretical alignment with full-batch gradients, GradMatch suffers from substantial computational overhead during optimization. GLISTER [ 6 ] and CRAIG [ 7 ] frame the subset selection problem as a submodular optimization task, which allows efficient greedy selection but lacks adaptive flexibility to dynamic gradient changes. GRAFT builds upon these limitations by improving scalability and optimization fidelity. It samples from a low-rank subspace, maximizing the spanned volume through Fast MaxVol-based selection, and dynamically adjusts subset sizes to preserve representational capacity throughout training. Empirical evaluations using the CORDS framework demonstrate that methods

Read the complete text