Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression

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 ℓ(x,y)(W)=lVert Wx-yrVert22, where x∈ℝd and y∈ℝ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 nstar(d,m)=(m+1)d. We determine the weighted selection profile Fweighted(d,m,n) at the near-threshold budget: Fweighted(d,m,(m+1)d-1)=1+1/(dm2). We recover the known spanning-budget value Fweighted(d,m,d)=d+1 for every m, and Fweighted(d,m,n)=∞ for n<d. For the smallest open intermediate cell (d,m)=(2,2) we prove Fweighted(2,2,3)∈[13/8,15/8] and Fweighted(2,2,4)∈[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≥2 extend the scalar theory for m=1.