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

Guangjian Zhang

Source-linked AI summary

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

Guangjian Zhang

arXiv:2608.30254v1Aug 31, 2026cs.LGmath.ST

TL;DR

The paper asks for the weighted-selection profile and the smallest budget achieving ratio 1. It formalizes weighted selection for minimum-Frobenius-norm ERM, resolves the profile at both ends, and identifies the remaining intermediate regime.

Problem
The central question is determining Fweighted(d, m, n), especially the minimal n for which the ratio equals 1.
Method
The paper analyzes weighted convex combinations of selected loss functions for the minimum-Frobenius-norm empirical risk minimizer, including a kernel-based line-structure argument.
Results
The profile is ∞ for n < d, d + 1 at n = d, 1 + 1/(dm^2) at n = (m + 1)d − 1, and 1 for n ≥ (m + 1)d.
Takeaways & Limitations
The threshold question is resolved, while determining Fweighted(d, m, n) for d < n < (m + 1)d − 1 remains open.
Takeaways & Limitations
The intermediate profile remains unresolved, and the paper’s correction concerns a false general-m claim about ratio 1 for all n ≥ 2d.

Abstract

from arXiv · show

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.

1 Introduction

This paper resolves the exact recovery threshold for weighted selection in vector-valued linear regression and determines several endpoint values of the selection profile. It also bounds the smallest intermediate case, develops structural proof techniques, and identifies remaining open regimes.

Problem: The weighted-selection profile asks for the worst-case loss ratio after selecting n examples for minimum-Frobenius-norm empirical risk minimization.The selection may repeat dataset points and assign them a convex combination of example losses.
Main results: (m + 1)d is the exact minimum budget n⋆(d, m) for full-data loss recovery when d, m ≥2.For every dataset of feature rank r, an exact certificate exists using (m + 1)r weighted points; an explicit dataset shows the threshold cannot be lowered.
Intermediate regime: For (d, m) = (2, 2), the paper proves Fweighted(2, 2, 3) ∈ [13/8, 15/8] and Fweighted(2, 2, 4) ∈ [5/4, 3/2].The conjectured lower endpoints 13/8 and 5/4 are reduced to a moment problem on the unit circle with at most seven atoms.
Scope and open problems: The intermediate profile d < n < (m + 1)d − 1 remains open, and the paper’s new results are claimed only for m ≥2 because the scalar case was previously established.The authors also correct a circulating claim that ratio 1 holds for all m at budgets n ≥2d; an explicit d = m = 2 dataset disproves it.
Proof techniques: The threshold upper bound uses fixed-basis conic compression, while near-threshold analysis uses determinant–facet rigidity and sharp zero-mean sparsification lemmas.The rigidity theorem forces maximal certificates to decompose into disjoint (m + 1)-point circuits on independent feature lines.

2 Preliminaries

The preliminaries formalize weighted selection for vector-valued linear regression and establish the geometric conditions under which a selected objective returns the full-data minimum-norm solution.

Model and selection semantics: Weighted selection is represented by a nonnegative weight vector with support size at most n, allowing repeated examples to merge weights.The learning rule minimizes the weighted objective using minimum Frobenius norm.
Row decomposition: The vector-valued weighted objective decomposes across output rows, but all rows use the same shared weight vector.This permits scalar rowwise analysis while preserving the common selection constraint.
Full-data geometry: The full-data minimum-norm predictor lies in the feature span, while residual dyads satisfy a vanishing first-order condition.The full minimizer set is W◦ plus perturbations annihilating the feature span.
Exact recovery: A spanning zero certificate makes the weighted and full-data minimizer sets coincide, so the selected model attains the full-data optimal loss.The minimum-Frobenius-norm rule chooses the same predictor from these identical minimizer sets.

3 The exact threshold (m + 1)d

The paper proves that exact recovery for every vector-valued regression dataset requires and is achieved with budget (m + 1)d, and gives the matching near-threshold obstruction.

Upper bound: (m + 1)r weighted points suffice for every dataset of feature rank r, yielding exact recovery at budget (m + 1)d.A fixed-basis conic compression constructs a spanning zero certificate from a basis and at most mr additional points.
Lower bound: 1 + m+1 2md(m2 + m −1) is the exact ratio for the integer axial instance when one of its (m + 1)d points is omitted.This instance proves the threshold cannot be reduced by one point.
Threshold theorem: (m + 1)d is the exact threshold: Fweighted(d, m, n) = 1 for n ≥ (m + 1)d.The lower bound comes from an explicit axial instance whose every selection of one fewer point has ratio greater than 1.
Concrete example: For d = m = 2, the six-point axial instance has optimal five-point ratio 43/40, while its budget-4 selections attain a larger obstruction.The instance uses labels (0,1), (1,0), and (2,2) over each standard-basis feature.
Vector-output consequence: The scalar rule n ≥ 2d does not extend to vector outputs.For m ≥ 2, the threshold is (m + 1)d rather than 2d.

4 Budgets n ≤d

At low budgets, the weighted selection profile is infinite below d and equals d + 1 at budget d, uniformly over the number of output dimensions.

Profile values: Fweighted(d, m, n) = ∞ for every n < d, and Fweighted(d, m, d) = d + 1.The lower bound embeds the scalar problem, while the upper bound selects one feature subset serving all output rows.
Upper bound: Size-d volume sampling supplies a common subset whose expected full-data loss is at most (d + 1) times optimum for all output rows.The feature-only sampling distribution is shared across rows, enabling one simultaneous selection.
Caveat: The volume-sampling equality requires general position; for degenerate feature matrices, only the inequality is guaranteed.A repeated-basis example has expected loss equal to 2L(w⋆), showing pointwise equality can fail.
Selection realization: A selected subset of at most d independent features is realizable by positive weights and the minimum-norm interpolant, completing the legal-selection argument.Padding allows the subset to use exactly d slots when needed.

5 The near-threshold value 1 + 1/(dm2)

The near-threshold profile is exactly 1 + 1/(dm^2), obtained by combining rigidity of maximal certificates with sharp sparsification of zero-mean systems.

Certificate rigidity: Maximal certificates split uniquely into d disjoint positive circuits of size m + 1, each supported on one of d independent feature lines.This determinant–facet rigidity forces hard datasets into a d-line form.
Sparsification lemma: The m-point mean lemma finds a convex combination of at most m points whose squared norm is at most E/m^2.The bound is sharp for uniformly weighted regular simplices.
Near-threshold theorem: 1 + 1/(dm^2) is the near-threshold value Fweighted(d, m, (m + 1)d −1) for all d, m ≥ 2.Datasets with smaller feature rank or certificate size are recovered exactly; maximal hard datasets require the structural argument.
Upper bound: Applying the lemma on one line and using m + 1 points on the others yields a support of (m + 1)d −1 with the stated upper bound.The selected features still cover every line, so the weighted minimizer is unique.
Sharpness: A regular-simplex axial instance attains the lower bound because every budget-(m + 1)d −1 selection omits a vertex or uses a proper facet subset.The facet distance is h^2 = 1/[m(m + 1)], producing the ratio 1 + 1/(dm^2).

6 The general k-point mean lemma

Section 6 proves a sharp k-point sparsification theorem: any weighted mean-zero system admits a convex combination of at most k points with controlled squared norm, and the bound is attained by a regular simplex.

Scope and dependencies: Only the k = M case and the trivial k = 1 case are used elsewhere in the paper; the general theorem relies on the Grace–Danielsson inequality.The section is otherwise logically independent of the paper’s main theorems.
The general k-point mean lemma: Theorem 6.1 guarantees, for every 1 ≤ k ≤ M + 1, a convex combination of at most k points with a dimension-dependent squared-norm bound.The proof reduces to a positive circuit of support s ≤ M + 1 and applies simplex skeleton sparsification.
The general k-point mean lemma: The bound is sharp for a uniformly weighted regular M-simplex: every k-point convex combination has squared norm at least the stated simplex value, with equality at equal weights.Thus the sparsification constant cannot be improved in general.
Proof strategy: The proof constructs a martingale of probability vectors that successively removes coordinates using a boundary-supported random probability vector.The boundary variance fact controls the loss of variance at each coordinate-killing step.
Proof strategy: A finite moment problem and strong duality establish the boundary variance fact underlying the iterative sparsification argument.The argument uses convexity and simplex–ball interpolation after regularizing the quadratic form on the tangent space.

7 The smallest intermediate cell: (d, m) = (2, 2)

Section 7 studies the open intermediate budgets for (d, m) = (2, 2), proving interval bounds, explicit lower-bound datasets, and a reduction to finite moment systems on the circle.

7 The smallest intermediate cell: (d, m) = (2, m): The open budgets in the smallest intermediate cell are n = 3 and n = 4, and the section proves interval theorems while reducing conjectured exact values to a finite moment problem.The reduction concerns moment systems with a bounded number of atoms.
Explicit lower bounds: For budget 3, an explicit dataset gives the lower bound Fweighted(2, 2, 3) ≥ 13/8.The construction uses two feature axes and three residual points arranged as a centered equilateral triangle.
Explicit lower bounds: For budget 4, the same dataset gives the lower bound Fweighted(2, 2, 4) ≥ 5/4.The optimal allocation places two selected points on each feature axis.
Explicit lower bounds: The construction’s allocation costs are c(3) = 0, c(2) = 1/6, c(1) = 2/3, and c(0) = 5/6 for an empty axis.These costs determine the minimum excess loss at each budget.
Moment reduction: After whitening, the (2, 2) problem is represented by complex feature and residual variables subject to moment conditions, with finite systems realizable as datasets.The selected model is encoded by a real-linear map, and zero-feature points can only enlarge the optimal loss.

7.3 Interpolation identities

The interpolation identities express selected-model coefficients as convex combinations of pairwise coefficients and characterize which coefficient combinations are attainable on two- and three-point supports.

7.3 Interpolation identities: For admissible selections, the model coefficients are represented through pairwise interpolation coefficients weighted by feature-direction distances.The conditioning factor is absorbed into this convex-combination representation.
Three-point closure: For sets of at most three points, the attainable coefficient set is the convex hull of valid pairwise coefficients, with boundary behavior determined by support degeneracies.Repeated directions yield exactly attainable segments, while some non-degenerate edge interiors arise only as limits.
Three-point closure: With three distinct directions, the relevant pairwise coefficient points are never collinear when distinct, giving geometric rigidity of the interpolation set.This supports the finite geometric reduction used for the intermediate-cell analysis.
Global identities: The global identities follow by expanding pairwise distances and summing over pairs, with same-direction pairs contributing a separate correction term.The two telescoping sums recover the moment quantity E under the stated conditions.

7.4 Star localization and the two unconditional bounds

Star localization yields a local geometric bound around a chosen atom, while Carathéodory’s theorem gives an unconditional four-point bound on the coefficient objective.

7.4 Star localization: Two star neighbors suffice to produce a segment point δ satisfying the stated local norm bound, and δ is a closure point of three-point selections.Choosing an atom with |zi|² ≤ E yields the corresponding localized estimate.
7.4 Star localization: For a fixed atom, valid star coefficients lie in a real two-dimensional affine plane, have mean mi, and have variance Vi determined by E, |zi|², and same-direction corrections.The local geometry supports replacing the star by a small number of neighbors.
Real-frame formulation: The real-frame representation encodes directions as unit vectors and pairwise weights through squared determinants, linking the complex moment formulation to planar geometry.The tight-frame identities provide the normalization used in the star analysis.
The two unconditional bounds: Every moment system admits selections with support at most 4 whose coefficient objective satisfies inf C(q) ≤ E/2.The proof uses Carathéodory in the star’s affine plane and a limiting selection concentrated on one atom.

7.5 The interval theorem

For (d,m)=(2,2), the interval theorem bounds the three- and four-point selection profiles while reducing the proof to lower bounds and a general upper-bound argument.

Bounds: 13/8 ≤ Fweighted(2,2,3) ≤ 15/8 and 5/4 ≤ Fweighted(2,2,4) ≤ 3/2.The lower bounds come from Proposition 7.1, while the upper bounds use the dictionary and Lemma 7.6.
Upper bounds: If the feature rank is at most one, three selected weighted points suffice for exact recovery, so the ratio is 1 for budgets three and four.The argument uses τ(D) ≤ (m+1)r ≤ 3.
Upper bounds: When the full-data optimum is nonzero and the certificate threshold exceeds the budget, the Section 7.2 dictionary and Lemma 7.6 yield the stated upper bounds.A three-point selection is also a four-point selection, so the four-point bound follows from the three-point analysis.
Infimum argument: Closure points in Lemmas 7.5–7.6 are limits of admissible selections within the same budget, which is sufficient because the inner optimization is an infimum.This justifies using limiting selections in the interval-theorem argument.

7.6 The conjecture and its evidence

The conjectured values for the (2,2) intermediate cell reduce to a finite moment problem, with extensive structural results identifying candidate extremizers and ruling out restricted proof strategies.

Conjectured bounds: The conjecture is equivalent to proving infimum costs at most 5E/8 with three points and E/4 with four points for every moment system.The reduction uses the branch analysis and Lemma 7.3.
Finite reduction: At most seven atoms suffice in the moment problem because an optimal admissible weight vector can be chosen as a basic feasible solution.The admissible weights satisfy at most seven linear constraints, and atom splitting permits exactly seven labelled atoms.
Two-direction systems: Two-direction systems are antipodal with equal class weights and zero conditional means, yielding an explicit formula for the selection cost.For these systems, C(q)=1/2(|m+|^2+|m−|^2).
Extremal systems: The sharp three-point constant is 5E/8 for six equally weighted atoms, while the four-point constant is E/4 for the same construction.Equality at 5E/8 has rigid equilateral-triangle structure; a five-atom two-direction system attains 4E/7 for three points.
Local maximality: The equality fiber is a stratified local maximum: energy imbalance lowers the three-point value, and genuine direction splitting has limsup below 5E/8.A paired splitting family can approach E/8 at three points while retaining four-point value E/4.
Proof obstructions: The conjecture cannot be proved by restricting to zero-mean selections or by preserving original weights on selected subsets.The seventh-roots and averaging obstructions exhibit better unconstrained or reweighted selections than those restricted classes.
Further evidence: Deletion arguments prove the conjectured inequalities for several classes, including systems with at most five atoms, all two-direction systems, and selected antipodal systems.Exact records include 1/2 for the hexagon three-point optimum, at most 19/169 for its four-point value, and 4/7 for the five-atom two-direction case.
Further evidence: Extensive exact searches over random six- and seven-atom systems found no value above the two-direction records.The closed-form values and extremal records were also independently verified by symbolic computation.

8 Discussion and open problems

The paper determines the weighted profile at both ends for all dimensions but leaves the intermediate curve and several related vector-valued selection questions open.

Known profile: ∞ for n<d, d+1 at n=d, 1+1/(dm^2) at n=(m+1)d−1, and 1 for n≥(m+1)d.These are the known endpoint values of the weighted selection profile for all d,m≥1.
Threshold interpretation: The threshold (m+1)d decomposes into d points for a feature basis and md points to cancel the residual gradient.The lower-bound instances realize this as d independent weighted mean-estimation problems in R^m.
Open problems: The intermediate curve for d<n<(m+1)d−1 remains open, including the scalar case.Axial instances reduce to an allocation problem, while non-axial higher-dimensional block constructions may dominate deeper in the range.
Open problems: For (d,m)=(2,2), the conjecture reduces to at most seven circle atoms, with evidence favoring two-direction extremizers.The stated obstructions require allowing nonzero µ and reweighting within the selected support.
Open problems: The unweighted vector-selection profile and the dependence of thresholds on alternative ERM tie-breaking rules remain unresolved.The paper’s certificate and rigidity machinery uses minimum-Frobenius-norm tie-breaking through Lemma 2.4.
Verification: Closed-form values, profile values, exact records, and lower-bound claims received symbolic and independent numerical verification.The verification covered the listed instance values and all relevant supports.