{"id":"arxiv/2608.30254","url":"https://arxiv.org/abs/2608.30254","tags":["cs.LG","math.ST"],"score":0,"title":"Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression","domain":"cs.LG","source":"arxiv","authors":["Guangjian Zhang"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}