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

How much data must a fixed learner retain? Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed this question for linear regression with the minimum-norm empirical risk minimizer. A selector sees a finite dataset $D\subseteq R^d\times R$, keeps at most $n$ examples with nonnegative weights, and $F_w(d,n)$ is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is $\infty$ for $n<d$, $d+1$ at $n=d$ and $1$ for $n\ge2d$, and the regime $d<n<2d$ was left open. We settle 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 also prove $F_w(3,4)=5/3$, $F_w(4,5)=2$ and $F_w(4,6)=3/2$, the three smallest cells not covered by that formula. For every intermediate budget $n=d+k$ we prove the lower bound $F_w(d,d+k)\ge1+Γ_{d,k}$, where $Γ_{d,k}$ is an explicit harmonic quantity over balanced partitions of $d$. This bound is the exact minimax value on the class of datasets whose whitened systems split into orthogonal circuit blocks. All proved values equal $1+Γ_{d,k}$, and we conjecture that this holds throughout the open regime. Our upper bounds combine a rigidity theorem for positive spanning configurations of loss gradients with normal forms of the small positive bases in $R^3$ and $R^4$. These forms are special cases of the classification of Cornaz, Kerleau and Royer; we also control all gradients outside the basis. A dimension-free extremal-basis argument converts sign-cone geometry into selections of $d+1$ points. Explicit counterexamples rule out several shorter routes. Every upper bound is constructive, with selection procedures polynomial in the number of points for fixed dimension. Every numerical claim about a specific instance is an exact rational or algebraic identity, recomputed in exact arithmetic in the supplementary material.

We resolve the threshold part of Question 4 of the COLT 2025 open problem "Data Selection for Regression Tasks" of Hanneke, Moran, Shlimovich and Yehudayoff. We study vector-valued linear regression with square loss $\ell_{(x,y)}(W)=\lVert Wx-y\rVert_2^2$, where $x\in\mathbb{R}^d$ and $y\in\mathbb{R}^m$. The learner returns the minimum-Frobenius-norm empirical risk minimizer. We prove that the minimal budget of weighted examples for recovering the full-data loss on every finite dataset is exactly $n^{\star}(d,m)=(m+1)d$. We determine the weighted selection profile $F_{\mathrm{weighted}}(d,m,n)$ at the near-threshold budget: $F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2)$. We recover the known spanning-budget value $F_{\mathrm{weighted}}(d,m,d)=d+1$ for every $m$, and $F_{\mathrm{weighted}}(d,m,n)=\infty$ for $n<d$. For the smallest open intermediate cell $(d,m)=(2,2)$ we prove $F_{\mathrm{weighted}}(2,2,3)\in[13/8,15/8]$ and $F_{\mathrm{weighted}}(2,2,4)\in[5/4,3/2]$. We reduce the conjectured exact values $13/8$ and $5/4$ to a finite moment problem on the circle with at most seven atoms and assemble structural evidence for it. The upper bounds use a fixed-basis conic compression lemma, a determinant--facet rigidity theorem for maximal certificates, and sharp sparsification lemmas for zero-mean weighted point systems. These tools may be of independent interest. We also exhibit an explicit six-point integer dataset with $d=m=2$ on which no weighted selection of $2d$ points recovers the optimal loss. Thus the scalar sufficient budget $2d$ does not extend to vector-valued outputs. Our new regression-profile results for $m\ge2$ extend the scalar theory for $m=1$.

We study ridge regression from exactly $s$ distinct rows of a fixed design. Responses are fixed, and only the subset is random. The determinant law and selected ridge fit share one positive definite penalty. Established mean identities and exponential-family duality give the unique penalty that matches a prescribed full-data ridge fit in expectation. It exists exactly when $s$ exceeds the target's effective dimension. Our main result concerns centered covariance risk normalized by full-data penalized loss. For balanced signed coordinate replicas, a strict sector inequality gives the sharp risk and all maximizing responses at every budget from the dimension to one below the row count. This holds for any nonzero positive semidefinite query. With the target and query fixed, the maximizing response space is unchanged across these budgets. For general designs, we characterize attainment of a leave-one-out envelope. For existing real equiangular tight frames, flat row query energy characterizes when every nonzero residual response maximizes at two deletions. At three deletions, we give the sharp risk and complete maximizing space for isotropic queries, using unequal triangle weights. The balanced geometry yields a same-sample unbiased ridge--Horvitz--Thompson mixture with lower sharp risk and an exact mean-share improvement boundary. Under full recalibration after feature changes, we prove quadratic regret from searching the complete old maximizing space and a query-uniform bound on the mixture's risk gain. The strongest sector inequalities have exact computer-assisted proofs.