Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
Abstract
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 n⋆(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.
Related
- Ordered Weighted Average Support Vector Regression
- Exact Risk Ratios for Weighted Data Selection in Linear Regression
- Strict monotonicity of weighted inhomogeneous percolation thresholds under covering maps
- Support Vector Machines for Classification, Regression, and Outlier Detection: A Tutorial
- Criteria for Weighted Homogeneity via Logarithmic Vector Fields
BibTeX
@misc{zhang2026exact,
title = {{Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression}},
author = {Guangjian Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.30254},
eprint = {2608.30254},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30254},
}
RIS
TY - UNPB
TI - Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
AU - Guangjian Zhang
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2608.30254
UR - https://arxiv.org/abs/2608.30254
AB - 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−yrVert_2^2, 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 n^⋆(d,m)=(m+1)d. We determine the weighted selection profile F_weighted(d,m,n) at the near-threshold budget: F_weighted(d,m,(m+1)d−1)=1+1/(dm^2). We recover the known spanning-budget value F_weighted(d,m,d)=d+1 for every m, and F_weighted(d,m,n)=∞ for n<d. For the smallest open intermediate cell (d,m)=(2,2) we prove F_weighted(2,2,3)∈[13/8,15/8] and F_weighted(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.
ER -