Exact Risk Ratios for Weighted Data Selection in Linear Regression

arXiv:2608.28007v1 Announce Type: new Abstract: Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem. A selector sees a finite dataset D subseteq R^d imes R, picks at most n examples together with nonnegative weights, and hands the weighted least squares objective to the minimum-norm ERM. Writing F_w(d,n) for the worst-case ratio between the loss of the returned predictor on all of D and the optimal loss, they proved F_w(d,n)=infty for n<d, F_w(d,d)=d+1 and F_w(d,n)=1 for n ge 2d, and asked for the value in the open regime d<n<2d. We determine this value in several cases. For every d we prove F_w(d,2d-1)=1+1/d, which confirms a claim stated without proof in the original note. We further prove F_w(3,4)=5/3 and F_w(4,5)=2, the two smallest cells not covered by the endpoint formula. For every intermediate budget n=d+k we prove the lower bound F_w(d,d+k) ge 1+Gamma_{d,k}, where Gamma_{d,k} is an explicit harmonic quantity over balanced partitions, and we show that this bound is the exact minimax value over the class of datasets whose whitened gradient systems carry an orthogonal circuit-block structure. All three exact values match 1+Gamma_{d,k}, and we conjecture that equality holds throughout the open regime. The upper bound proofs run on a common geometric spine: a rigidity theorem for positive spanning configurations of loss gradients, classifications and structural reductions of small positive bases in R^3 and R^4, and a dimension-free extremal-basis argument that converts sign-cone geometry into five-point selections. We also give explicit counterexamples showing that several shorter routes fail, and constructive polynomial-time selection algorithms for all proved cases.

Source: arXiv cs.LG | 2026-08-31

Related