Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws
The paper establishes sharp laws governing how much risk a small subset of training data for weighted least squares regression retains. It proves a universal upper bound, $\Gamma_d(n) = 3 - n/d$, for the intermediate budget interval. For smaller budgets like (5, 6), it derives a specific result of $\Gamma_5(6) = 11/5$, providing exact bounds and matching lower bounds to show sharpness.