AI summaryⓘ
The authors solved a specific question about how many weighted examples are needed to perfectly recover the loss in linear regression tasks involving multiple outputs (vector-valued). They showed that the exact minimum number of examples is (m+1) times the input dimension, where m is the output dimension. They also explored values near this threshold and for small cases, reducing some problems to finite moment problems with strong evidence supporting their conjectures. Additionally, they corrected a recent false claim by providing a dataset example where fewer points than the threshold fail to recover the optimal loss. Their new results apply primarily when the output dimension is two or more, extending earlier work for scalar outputs.
Vector-valued linear regressionSquare lossEmpirical risk minimizationFrobenius normWeighted data selectionThreshold budgetMoment problemSparsificationDeterminant-facet rigidityConic compression
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. In vector-valued linear regression with square loss $\ell_{(x,y)}(W)=|Wx-y|_2^2$, where $x\in\mathbb{R}^d$, $y\in\mathbb{R}^m$ and the learner is the empirical risk minimizer of minimal Frobenius norm, we prove that the minimal budget of weighted examples that recovers the full-data loss on every finite dataset is exactly $n^*(d,m)=(m+1)d$. We further determine two more values of the weighted selection profile $F_w(d,m,n)$: at the near-threshold budget, $F_w(d,m,(m+1)d-1)=1+\frac{1}{dm^2}$, and at the spanning budget, $F_w(d,m,d)=d+1$ for every $m$, while $F_w(d,m,n)=\infty$ for $n<d$. For the smallest open intermediate cell $(d,m)=(2,2)$ we prove $F_w(2,2,3)\in[13/8,15/8]$ and $F_w(2,2,4)\in[5/4,3/2]$, reduce the conjectured exact values $13/8$ and $5/4$ to a finite moment problem on the circle with at most seven atoms, and establish strong structural evidence for the conjecture. The upper-bound techniques (a fixed-basis conic compression lemma, a determinant-facet rigidity theorem for maximal certificates, and sharp sparsification lemmas for zero-mean weighted point systems) are of independent interest. As a byproduct we correct an erroneous claim circulating in a recent unrefereed preprint, exhibiting an explicit dataset with $m=2$ on which no weighted selection of $2d$ points recovers the optimal loss. All results are new only for $m\ge 2$; the scalar case $m=1$ is due to Hanneke et al.