# Gamma-aware gradient coreset selection

- ID: 2787
- Canonical URL: https://synthcore.org/idea/2787/gamma-aware-gradient-coreset-selection
- API JSON: https://synthcore.org/api/idea/2787.json
- API Markdown: https://synthcore.org/api/idea/2787.md
- Verification status: unverified
- Source: [arXiv:2608.28007](https://arxiv.org/abs/2608.28007)
- Category: training
- Solves: sample-efficiency, accuracy, scalability
- ML areas: training, fine-tuning, loss
- Math tags: linear-algebra, geometry, combinatorics, optimization
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Construct a weighted training subset of size d+k for a linear prediction head by whitening per-example gradients, identifying approximately orthogonal gradient blocks, and allocating selected examples according to the paper's balanced-partition risk law. Train the head, or a local linearized model, using this subset and its nonnegative weights. The main falsifiable claim is improved full-dataset risk at very small budgets, especially when the subset size is only slightly larger than the parameter dimension.

## Mathematical statement

Let D be a dataset of examples (x_i, y_i), with x_i in R^d, and let F_w(d,n) denote the worst-case ratio between the full-data squared loss of the minimum-norm weighted ERM trained on at most n selected examples and the optimal full-data loss. The paper proves F_w(d,d+k) >= 1 + Gamma_{d,k}, for 1 <= k <= d-1, where Gamma_{d,k} = max_{k+1 <= s <= d} (s-k) / min_{r_1+...+r_s=d, r_j in Z_{>0}} sum_{j=1}^s 1/r_j. Here s is the number of orthogonal circuit blocks, and r_j is the dimension or rank assigned to block j. For each fixed s, the minimizing integer partition is balanced: the r_j values differ by at most one. On the paper's orthogonal circuit-block model class, this lower bound is the exact worst-case excess ratio. For a neural-network adaptation, let g_i = gradient of example i with respect to the trainable parameter vector at the current checkpoint. Estimate H = (1/N) sum_i g_i g_i^T + lambda I, where lambda > 0 stabilizes inversion, and whiten with z_i = H^{-1/2} g_i. Cluster or decompose the z_i vectors into approximately orthogonal blocks, estimate their ranks r_j, and use the resulting Gamma estimate to guide subset allocation. In neural networks the exact theorem does not automatically apply; the mathematical asset is the balanced-rank allocation principle and the explicit budget-risk curve.

## Key formulas

- $$F_{\mathrm{w}}(d,d+k)\geq 1+\Gamma_{d,k},\qquad \Gamma_{d,k}=\max_{k+1\leq s\leq d}\frac{s-k}{\displaystyle\min_{\substack{r_1+\cdots+r_s=d\\ r_j\in\mathbb{Z}_{>0}}}\sum_{j=1}^{s}\frac{1}{r_j}}.$$
- $$R_D(\theta)=\sum_{i=1}^{N}(x_i^{\top}\theta-y_i)^2,\qquad \widehat{\theta}_{S,w}=\arg\min_{\theta:\ \|\theta\|_2\ \mathrm{minimal}}\sum_{i\in S}w_i(x_i^{\top}\theta-y_i)^2.$$
- $$g_i=\nabla_{\theta}\ell_i(\theta),\qquad H=\frac{1}{N}\sum_{i=1}^{N}g_i g_i^{\top}+\lambda I,\qquad z_i=H^{-1/2}g_i.$$
- $$\widehat{\Gamma}(d,k;z)=\max_{k+1\leq s\leq d}\frac{s-k}{\displaystyle\min_{r_1+\cdots+r_s=d}\sum_{j=1}^{s}1/r_j},\qquad |r_a-r_b|\leq 1\ \text{for a balanced minimizing partition}.$$

## Implementation notes

Integrate this method into the data loader or fine-tuning pipeline for a linear probe, final classifier head, or local linearized neural-network objective. First freeze the encoder at parameters theta and retain only a d-parameter head. For every candidate example, compute the per-example head gradient g_i and store the resulting N by d matrix G. Estimate H = G^T G divided by N plus lambda times the identity; compute H^{-1/2} with an eigendecomposition for small d or a randomized low-rank SVD for larger d, then form z_i = H^{-1/2} g_i. For each s from k+1 through d, partition the whitened gradients into s groups using spherical k-means or greedy assignment by orthogonal residual. Estimate the effective rank r_j of group j as the number of singular values above threshold tau. Choose the candidate partition whose rank vector is closest to a balanced integer partition and compute the corresponding Gamma estimate. Set the total subset size to n = d+k. Allocate representatives across blocks, ensuring coverage of every estimated rank direction, then assign remaining slots to examples with largest within-block leverage score h_i = z_i^T (Z_j^T Z_j + epsilon I)^{-1} z_i. Fit nonnegative weights by solving nonnegative least squares so that the selected weighted gradients match the full gradient mean and, optionally, the leading covariance directions; enforce weights w_i >= 0 and sum_i w_i = N. The paper supplies the Gamma formula and balanced-rank rule; whitening, rank thresholds, clusters, and weights are empirical approximations. Begin with synthetic regression having explicitly orthogonal blocks, then test a frozen ResNet or ViT encoder on CIFAR-10 with head dimensions 32, 64, and 128. Compare against uniform sampling, gradient-norm sampling, and standard leverage-score sampling at n = d+k. Measure full validation loss, loss per selected example, selection overhead, and wall-clock training time. Success means lower full-data risk at equal subset size, with the strongest gains near n = d+1, and risk behavior that follows the predicted Gamma trend on the synthetic benchmark.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.