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

arXiv:2610.00101v1 Announce Type: cross Abstract: 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 Gamma_d(n)=3-n/d throughout lceil3d/2rceilleq nleq2d-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 Gamma_5(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.

Related

• Exact Risk Ratios for Weighted Data Selection in Linear Regression
• The Sharp Tail of Uniform Stability
• Distributed Sketching on Data Partitions for OLS Regression

Source: arXiv cs.LG | 2026-10-02