Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
arXiv:2608.30254
2026
Memory
2 ideas extracted · analyzed Sep 1, 2026
What the math gives to ML
The paper gives a sharp structural result for compressing multi-output linear regression datasets: exact recovery of the minimum-Frobenius-norm empirical-risk minimizer is possible with at most (m+1)r weighted examples, where r is the feature rank, and this is necessary in the worst case. This is more specific than generic coreset bounds because the support size scales linearly with both feature rank and output dimension. The most direct transfer is a deterministic weighted replay buffer or linear-probe coreset for neural networks, where a frozen embedding is followed by a repeatedly refit multi-output linear head. The near-threshold profile also supplies a principled accuracy-versus-memory tradeoff when using one fewer point.
Ideas from this paper
△ Mechanism confirmed, baseline not beaten
2026
Compress a dataset for a frozen neural embedding and multi-output linear head into at most (m+1)r weighted examples while preserving the full-data minimum-Frobenius-norm least-squares solution. This can make repeated linear probing, classifier refitting, or replay-buffer training much smaller without changing the optimum in exact arithmetic.
Useful7/10
Difficulty6/10
Novelty5/10
Unverified
2026
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.
Useful6/10
Difficulty4/10
Novelty4/10