Unverified 2026

One-Point-Below-Threshold Data Budget

Usefulness6/10

Difficulty4/10

Novelty4/10

Regularization Memory Accuracy Sample efficiency Embedding Memory Data augmentation Optimization Linear algebra Convex analysis Combinatorics

Source paper: Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression arXiv:2608.30254 ⓘ · analyzed Sep 1, 2026

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

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.

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}.$$

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.

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.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.