math.STNov 9, 2026
SaveA Strict Upper Bound for Three-Point Weighted Selection in Planar Vector-Valued Regression
Abstract
We prove for minimum-Frobenius-norm least-squares regression with two input and two output coordinates, improving the upper bound . More precisely, a universal satisfies for every finite residual frame. The proof combines an exact scalar certificate, rigidity of equality in planar selection, and a compactness argument that controls disappearing weights. Together with the known lower bound, this gives . No numerical value of is claimed.
More in this topic
Linear Regression
Linear regression models how outcomes depend on features through weighted sums, supporting prediction, inference, and analysis of learning algorithms.
See all 84 papersWe 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 , where and . 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 . We determine the weighted selection profile at the near-threshold budget: . We recover the known spanning-budget value for every , and for . For the smallest open intermediate cell we prove and . We reduce the conjectured exact values and 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 on which no weighted selection of points recovers the optimal loss. Thus the scalar sufficient budget does not extend to vector-valued outputs. Our new regression-profile results for extend the scalar theory for .
Exact Risk Ratios for Weighted Data Selection in Linear Regression
How much data must a fixed learner retain? Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed this question for linear regression with the minimum-norm empirical risk minimizer. A selector sees a finite dataset , keeps at most examples with nonnegative weights, and is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is for , at and for , and the regime was left open. We settle several cases. For every we prove , which confirms a claim stated without proof in the original note. We also prove , and , the three smallest cells not covered by that formula. For every intermediate budget we prove the lower bound , where is an explicit harmonic quantity over balanced partitions of . This bound is the exact minimax value on the class of datasets whose whitened systems split into orthogonal circuit blocks. All proved values equal , and we conjecture that this holds throughout the open regime. Our upper bounds combine a rigidity theorem for positive spanning configurations of loss gradients with normal forms of the small positive bases in and . These forms are special cases of the classification of Cornaz, Kerleau and Royer; we also control all gradients outside the basis. A dimension-free extremal-basis argument converts sign-cone geometry into selections of points. Explicit counterexamples rule out several shorter routes. Every upper bound is constructive, with selection procedures polynomial in the number of points for fixed dimension. Every numerical claim about a specific instance is an exact rational or algebraic identity, recomputed in exact arithmetic in the supplementary material.
Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws
How much risk does a small reweighted training support retain? For finite weighted least squares with the minimum-norm learner, we prove the exact law throughout . The guarantee covers every observed feature rank and uses selections that preserve the full feature span. Balanced simplex anchors reduce dimension; positive-weight lifting and independent-line compression close the risk bound. Shifted coordinate pairs attain the matching lower bound. The complete dataset-level upper bound and sharpness construction are verified in Lean 4. At the smaller budget , we also prove , matching the simplex-block prediction from over arbitrary interacting configurations. Circuit covers, comparison second moments, and circuit-plane probabilities give the sharp excess , while polar-face geometry resolves shared rank-three circuits. The general simplex-block frontier connects these laws within the intermediate-budget selection problem.