# Exact Risk Ratios for Weighted Data Selection in Linear Regression

arXiv: https://arxiv.org/abs/2608.28007 · HTML: https://mlsanity.com/paper/2608.28007/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 28 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [Beyond neural scaling laws: beating power law scaling via data pruning](https://mlsanity.com/paper/2206.14486/) (2022)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Data Selection for ERMs](https://mlsanity.com/paper/2504.14572/) (2025)
- [Nicely structured positive bases with maximal cosine measure](https://mlsanity.com/paper/2112.08212/) (2021)

## Built on by (most cited first, 2 of 2)

- [Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression](https://mlsanity.com/paper/2608.30254/) (2026)
- [Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws](https://mlsanity.com/paper/2610.00101/) (2026)

## Abstract (arXiv)

How much data must a fixed learner retain? Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed this question for linear regression with the minimum-norm empirical risk minimizer. A selector sees a finite dataset Dsubseteq Rd× R, keeps at most n examples with nonnegative weights, and Fw(d,n) is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is ∞ for n<d, d+1 at n=d and 1 for n≥2d, and the regime d<n<2d was left open. We settle several cases. For every d we prove Fw(d,2d-1)=1+1/d, which confirms a claim stated without proof in the original note. We also prove Fw(3,4)=5/3, Fw(4,5)=2 and Fw(4,6)=3/2, the three smallest cells not covered by that formula. For every intermediate budget n=d+k we prove the lower bound Fw(d,d+k)≥1+Gammad,k, where Gammad,k is an explicit harmonic quantity over balanced partitions of d. This bound is the exact minimax value on the class of datasets whose whitened systems split into orthogonal circuit blocks. All proved values equal 1+Gammad,k, and we conjecture that this holds throughout the open regime. Our upper bounds combine a rigidity theorem for positive spanning configurations of loss gradients with normal forms of the small positive bases in R3 and R4. These forms are special cases of the classification of Cornaz, Kerleau and Royer; we also control all gradients outside the basis. A dimension-free extremal-basis argument converts sign-cone geometry into selections of d+1 points. Explicit counterexamples rule out several shorter routes. Every upper bound is constructive, with selection procedures polynomial in the number of points for fixed dimension. Every numerical claim about a specific instance is an exact rational or algebraic identity, recomputed in exact arithmetic in the supplementary material.