Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 6 of its 24 references that are in the map. First posted on arXiv 8 Sep 2026.
Builds on
6 of 24 references.
References · 6
- 2013A Statistical Perspective on Algorithmic Leveragingcited by 38
- 2014Randomized Sketches of Convex Programs with Sharp Guaranteescited by 25
- 2014A Statistical Perspective on Randomized Sketching for Ordinary Least-Squarescited by 21
- 2018Reverse iterative volume sampling for linear regressioncited by 9
- 2025Data Selection for ERMscited by 3
- 2026Exact Risk Ratios for Weighted Data Selection in Linear Regressioncited by 2
Built on by
Not cited yet.