Exact Risk Ratios for Weighted Data Selection in Linear Regression
Machine Learning
Summary
The authors study a problem proposed by Hanneke, Moran, Shlimovich, and Yehudayoff about how well one can approximate the best prediction on a dataset by selecting only a limited number of examples with weights for least squares regression. They determine exact worst-case performance ratios for cases where the number of selected examples is between the data dimension and twice that dimension, confirming some previously unproven claims and finding new ones. Their proofs involve geometric properties of gradient vectors and special structures in small dimensions. They also provide algorithms that achieve these results and examples showing simpler approaches do not work. They further conjecture their lower bound formula gives the exact answer in all intermediate cases.
Authors
Guangjian Zhang
Abstract
Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem. A selector sees a finite dataset $D \subseteq \mathbb{R}^d \times \mathbb{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+Γ_{d,k}$, where $Γ_{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+Γ_{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 $\mathbb{R}^3$ and $\mathbb{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.