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

arXiv: https://arxiv.org/abs/2608.30254 · HTML: https://mlsanity.com/paper/2608.30254/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 31 Aug 2026.

## Builds on (most cited first, 5 of 5)

- [DataComp: In search of the next generation of multimodal datasets](https://mlsanity.com/paper/2304.14108/) (2023)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Data Selection for ERMs](https://mlsanity.com/paper/2504.14572/) (2025)
- [Exact Risk Ratios for Weighted Data Selection in Linear Regression](https://mlsanity.com/paper/2608.28007/) (2026)
- [Sharp approximate Carath'eodory theorem and application to iterated Delaunay refinement](https://mlsanity.com/paper/2606.25854/) (2026)

## Abstract (arXiv)

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.