mlsanityData to 7 Oct 2026

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

arXiv 2610.00101 ↗First posted 8 Sep 2026stat.ML cs.LGcited by 0

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

  1. 2013A Statistical Perspective on Algorithmic Leveragingcited by 38
  2. 2014Randomized Sketches of Convex Programs with Sharp Guaranteescited by 25
  3. 2014A Statistical Perspective on Randomized Sketching for Ordinary Least-Squarescited by 21
  4. 2018Reverse iterative volume sampling for linear regressioncited by 9
  5. 2025Data Selection for ERMscited by 3
  6. 2026Exact Risk Ratios for Weighted Data Selection in Linear Regressioncited by 2

Built on by

Not cited yet.