# Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 8 Sep 2026.

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

- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares](https://mlsanity.com/paper/1406.5986/) (2014)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [Data Selection for ERMs](https://mlsanity.com/paper/2504.14572/) (2025)
- [Exact Risk Ratios for Weighted Data Selection in Linear Regression](https://mlsanity.com/paper/2608.28007/) (2026)

## Abstract (arXiv)

How much risk does a small reweighted training support retain? For finite weighted least squares with the minimum-norm learner, we prove the exact law Gammad(n)=3-n/d throughout lceil3d/2rceil≤ n≤2d-1. The guarantee covers every observed feature rank and uses selections that preserve the full feature span. Balanced simplex anchors reduce dimension; positive-weight lifting and independent-line compression close the risk bound. Shifted coordinate pairs attain the matching lower bound. The complete dataset-level upper bound and sharpness construction are verified in Lean 4. At the smaller budget (d,n)=(5,6), we also prove Gamma5(6)=11/5, matching the simplex-block prediction from 5=3+2 over arbitrary interacting configurations. Circuit covers, comparison second moments, and circuit-plane probabilities give the sharp excess 6/5, while polar-face geometry resolves shared rank-three circuits. The general simplex-block frontier connects these laws within the intermediate-budget selection problem.