# One-Point-Below-Threshold Data Budget

- ID: 2879
- Canonical URL: https://synthcore.org/idea/2879/one-point-below-threshold-data-budget
- API JSON: https://synthcore.org/api/idea/2879.json
- API Markdown: https://synthcore.org/api/idea/2879.md
- Verification status: unverified
- Source: [arXiv:2608.30254](https://arxiv.org/abs/2608.30254)
- Category: regularization
- Solves: memory, accuracy, sample-efficiency
- ML areas: embedding, memory, data-augmentation
- Math tags: optimization, linear-algebra, convex-analysis, combinatorics
- Ratings: usefulness 6/10; difficulty 4/10; novelty 4/10

## Idea description

Use one fewer point than the exact support threshold for a weighted multi-output linear head. The paper proves that the worst-case multiplicative loss penalty at this budget is only 1+1/(dm^2), giving a principled memory-saving option rather than an arbitrary subset-size heuristic.

## Mathematical statement

Theorem 1.2 proves that for all d,m\ge 1, the weighted selection profile at the near-threshold budget is F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2). Here F_{\mathrm{weighted}}(d,m,n) is the worst-case ratio between the loss obtained from the best weighted selection of at most n examples and the full-data optimum, over finite datasets with x_i\in\mathbb{R}^d and y_i\in\mathbb{R}^m. The exact threshold is (m+1)d, so removing one support point has a bounded worst-case degradation. Define rho(d,m)=1+1/(dm^2). This is a theorem for the optimal weighted selection in vector-valued square-loss regression, not an automatic guarantee for a greedy neural-network heuristic; actual excess loss must therefore be measured empirically.

## Key formulas

- $$F_{\mathrm{weighted}}\bigl(d,m,(m+1)d-1\bigr)=1+\frac{1}{dm^{2}}.$$
- $$n^{\star}(d,m)=(m+1)d,$$
- $$\rho(d,m)=1+\frac{1}{dm^2},\qquad n_{\mathrm{exact}}=(m+1)d,\qquad n_{\mathrm{near}}=(m+1)d-1.$$
- $$A_w=\sum_{i\in S}w_i x_i x_i^{\top},\qquad B_w=\sum_{i\in S}w_i y_i x_i^{\top},\qquad \widehat W_w=B_wA_w^{\dagger}.$$

## Implementation notes

Apply this to a frozen feature extractor whose output dimension is d and a multi-class or multi-task linear head with m outputs. At each data-refresh step, compute the full-data reference statistics A=\sum_i x_ix_i^T and B=\sum_i y_ix_i^T, then set the support budget to n=(m+1)d-1. Build the support using greedy forward selection: for each candidate, estimate the reduction in the joint residual R=\|A-A_w\|_F^2/\|A\|_F^2+\|B-B_w\|_F^2/\|B\|_F^2, add the best candidate, and periodically refit nonnegative weights with NNLS. After reaching n points, perform local swaps and select the support minimizing validation loss of W_w=B_wA_w^{\dagger}. The paper provides the target factor rho(d,m)=1+1/(dm^2), but the engineer must estimate the realized loss ratio because greedy selection and floating-point arithmetic are outside the exact theorem. Compare against the exact-budget support of (m+1)d points, random weighted sampling, and leverage-score sampling on CIFAR-100 or synthetic rank-r regression. Record full-data excess loss, classification accuracy, support memory, and head-refit time as d and m vary. The predicted signal is negligible degradation for moderate m, with lower memory and solve time than the exact-budget or full-data alternatives.

## Disclaimer

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