math.STNov 9, 2026

A Strict Upper Bound for Three-Point Weighted Selection in Planar Vector-Valued Regression

Authors: Sergey Volkov

Abstract

We prove Fweighted(2,2,3)<11/6F_{\mathrm{weighted}}(2,2,3)<11/6 for minimum-Frobenius-norm least-squares regression with two input and two output coordinates, improving the upper bound 15/815/8. More precisely, a universal ε0>0\varepsilon_0>0 satisfies T3≤(5/6−ε0)E\mathcal T_3\le(5/6-\varepsilon_0)E 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 13/8≤Fweighted(2,2,3)<11/613/8\le F_{\mathrm{weighted}}(2,2,3)<11/6. No numerical value of ε0\varepsilon_0 is claimed.

Explore similar work

Aug 31, 2026

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

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)=∥Wx−y∥22\ell_{(x,y)}(W)=\lVert Wx-y\rVert_2^2, where x∈Rdx\in\mathbb{R}^d and y∈Rmy\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⋆(d,m)=(m+1)dn^{\star}(d,m)=(m+1)d. We determine the weighted selection profile Fweighted(d,m,n)F_{\mathrm{weighted}}(d,m,n) at the near-threshold budget: Fweighted(d,m,(m+1)d−1)=1+1/(dm2)F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2). We recover the known spanning-budget value Fweighted(d,m,d)=d+1F_{\mathrm{weighted}}(d,m,d)=d+1 for every mm, and Fweighted(d,m,n)=∞F_{\mathrm{weighted}}(d,m,n)=\infty for n<dn<d. For the smallest open intermediate cell (d,m)=(2,2)(d,m)=(2,2) we prove Fweighted(2,2,3)∈[13/8,15/8]F_{\mathrm{weighted}}(2,2,3)\in[13/8,15/8] and Fweighted(2,2,4)∈[5/4,3/2]F_{\mathrm{weighted}}(2,2,4)\in[5/4,3/2]. We reduce the conjectured exact values 13/813/8 and 5/45/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=2d=m=2 on which no weighted selection of 2d2d points recovers the optimal loss. Thus the scalar sufficient budget 2d2d does not extend to vector-valued outputs. Our new regression-profile results for m≥2m\ge2 extend the scalar theory for m=1m=1.
Aug 28, 2026

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 D⊆Rd×RD\subseteq R^d\times R, keeps at most nn examples with nonnegative weights, and Fw(d,n)F_w(d,n) is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is ∞\infty for n<dn<d, d+1d+1 at n=dn=d and 11 for n≥2dn\ge2d, and the regime d<n<2dd<n<2d was left open. We settle several cases. For every dd we prove Fw(d,2d−1)=1+1/dF_w(d,2d-1)=1+1/d, which confirms a claim stated without proof in the original note. We also prove Fw(3,4)=5/3F_w(3,4)=5/3, Fw(4,5)=2F_w(4,5)=2 and Fw(4,6)=3/2F_w(4,6)=3/2, the three smallest cells not covered by that formula. For every intermediate budget n=d+kn=d+k we prove the lower bound Fw(d,d+k)≥1+Γd,kF_w(d,d+k)\ge1+Γ_{d,k}, where Γd,kΓ_{d,k} is an explicit harmonic quantity over balanced partitions of dd. This bound is the exact minimax value on the class of datasets whose whitened systems split into orthogonal circuit blocks. All proved values equal 1+Γd,k1+Γ_{d,k}, 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 R3R^3 and R4R^4. 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 d+1d+1 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.
Sep 8, 2026

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 Γd(n)=3−n/dΓ_d(n)=3-n/d throughout ⌈3d/2⌉≤n≤2d−1\lceil3d/2\rceil\leq n\leq2d-1. 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 (d,n)=(5,6)(d,n)=(5,6), we also prove Γ5(6)=11/5Γ_5(6)=11/5, matching the simplex-block prediction from 5=3+25=3+2 over arbitrary interacting configurations. Circuit covers, comparison second moments, and circuit-plane probabilities give the sharp excess 6/56/5, while polar-face geometry resolves shared rank-three circuits. The general simplex-block frontier connects these laws within the intermediate-budget selection problem.