Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws

Zhongxuan Liu; Hongzhi Wang

stat.MLSep 8, 2026

Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws

Authors: Zhongxuan Liu, Hongzhi Wang

Organizations: Faculty of Computing, Harbin Institute of Technology

Abstract

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

Figures & tables

Figure 1: Weighted selection with a fixed learner. A support of at most $n$ original examples is reweighted for minimum-norm least-squares training; evaluation uses the complete dataset and its original weights $p$ . The two sharp laws cover the upper-half budget interval and the five-dimensional six-example problem, respectively. Tables and fitted lines are schematic; selected rows retain their original features and responses.

Result	Zhang (2026), v1	Role in this paper
$\Gamma_{d}(2d-1)=1+1/d$	Proved	Weighted certificate proof and rigidity
$\Gamma_{4}(5)=2$	Proved (Theorem 47)	Lower-dimensional input
$\Gamma_{5}(6)\geq 11/5$	Known lower bound	Explicit attained weighted example
$1+\Phi_{d,s}$	Block bound and structured frontier	Weighted formulation and connection to $(5,6)$
$\Gamma_{5}(6)\leq 11/5$	Left open	Universal upper bound

Table 1: Result-level positioning relative to Zhang (2026) , version 1. Its original evaluation model is uniform. The weighted transfer of the four-dimensional input is proved in Appendix B.6 .

Figure 2: Proof routes for the two main theorems. Top: full-span certificate analysis gives exact recovery within budget, a balanced anchor for projection and positive-weight lifting, or independent lines whose

t

cheapest coordinates can be compressed. Shifted coordinate pairs give the matching lower bound. Bottom: four exhaustive circuit-rank configurations bound the five-dimensional normalized excess by

6/5

; transfer and a seven-row example yield

11/5

. The bounds concern selected-risk infima;

B

denotes a certificate support and the geometry is schematic.

Stage	Invariant maintained	Full argument
Realization	Positive weights; six rows; full rank	Lemma 14
Exceptional reduction	Signed hull; $C\succeq I$ , without centering	Lemma 15
Shared circuits	No good crossing root or higher-rank circuit	Appendix B.3
Polar faces	Failed signs force one transverse direction	Lemmas 17 – 18
Circuit planes	Minimal positive relations constrain intersections	Lemmas 19 – 20
Graph to risk	Mean-zero vertex mixture of actual fits	( B.21 )–( B.22 )

Table 2: Invariants and where their full proofs are used.

Explore similar work

Exact Risk Ratios for Weighted Data Selection in Linear Regression
Aug 28, 2026Guangjian ZhangTraining Data Selection Linear Regression
University of New South Wales
Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
Aug 31, 2026Guangjian ZhangData Selection Training Data Selection
Exact Calibration and Sharp Risk Geometry for Volume-Sampled Ridge Regression
Oct 6, 2026Kihun RheeRidge Regression

Aug 28, 2026J/K move · Enter open · S save

Exact Risk Ratios for Weighted Data Selection in Linear Regression

Guangjian Zhang

University of New South Wales

Training Data Selection Linear Regression Empirical Risk Minimization Coreset Selection Minimax Estimation

Open paper AskPDF arXiv

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\subseteq R^d\times R

, keeps at most

n

examples with nonnegative weights, and

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<d

d+1

n=d

and

1

for

n\ge2d

, and the regime

d<n<2d

was left open. We settle several cases. For every

d

we prove

F_w(d,2d-1)=1+1/d

, which confirms a claim stated without proof in the original note. We also prove

F_w(3,4)=5/3

F_w(4,5)=2

and

F_w(4,6)=3/2

, the three smallest cells not covered by that formula. For every intermediate budget

n=d+k

we prove the lower bound

F_w(d,d+k)\ge1+Γ_{d,k}

, where

Γ_{d,k}

is an explicit harmonic quantity over balanced partitions of

d

. 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,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

R^3

and

R^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+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.

Abstract

Explore similar work

Exact Risk Ratios for Weighted Data Selection in Linear Regression

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

Exact Calibration and Sharp Risk Geometry for Volume-Sampled Ridge Regression