Source-linked AI summary
Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws
Zhongxuan Liu, Hongzhi Wang
TL;DR
The paper studies how much finite-distribution risk a small reweighted training support retains under a fixed minimum-norm least-squares learner. It uses geometric and certificate arguments to prove sharp laws for the upper-half budget interval and the five-dimensional six-example case. The general simplex-block frontier connects these laws while other intermediate budgets remain unresolved.
Problem
For finite weighted least squares, the question is how well a predictor trained on a few reweighted original examples performs on the full dataset, with the minimum-norm choice mattering when selected features lose rank.
Source: §1 · p. 1Method
Balanced anchors, positive-weight full-span lifting, and independent-line compression establish the upper-half law, while circuit geometry handles the (5,6) case.
Source: §1 · p. 1Results
Takeaways & Limitations
The upper-half and five-dimensional results connect through a general simplex-block frontier within the intermediate-budget selection problem.
Source: §2.1 · p. 4, §6 · p. 9For other intermediate budgets, the general equality Γ_d(d+s)=1+Φ_d,s remains the target.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
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 $\Gamma_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 $\Gamma_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.
1 INTRODUCTION
The paper asks how much finite-distribution risk remains when minimum-norm least squares trains on a small, reweighted support. It establishes sharp laws in the upper-half budget interval and at (5,6), using geometric arguments that ensure selected supports can realize the relevant learner outputs.
1 INTRODUCTION
- Γ_d(n)=3−n/d holds throughout the upper-half budget interval, and Γ_5(6)=11/5 is matched by a seven-point example.The (5,6) result supplies the universal matching upper bound to a lower bound already known from a simplex-block construction.Source: §1 · p. 1
- At (5,6), the new contribution is a universal matching upper bound; the 11/5 lower bound was already present in Zhang (2026), version 1.The paper also uses Zhang’s four-dimensional five-point theorem as an input and gives a self-contained weighted, minimum-norm-safe matching example.Source: §1 · p. 1
- A positive circuit combined with independent interpolating rows gives a six-row full-rank training problem whose actual learner outputs can be analyzed geometrically.This training-realization interface lets polar geometry, comparison second moments, and circuit-plane graphs control the risk of fits.Source: §1 · p. 2
- Full-span certificate complexity links exact recovery and maximal complexity to independent one-dimensional blocks, yielding the weighted boundary law and its extremal conditions.The boundary and interior results share an interface between positive dependence and the fixed learner’s output, but require different geometry.Source: §1 · p. 2
- Unlike coreset and sampling guarantees, this work determines a deterministic risk infimum over reweighted original supports at fixed small budgets, including deficient-rank designs.Evaluation uses the target finite distribution with weights p, while the selector chooses training weights q; the guarantee is not about population generalization or selection runtime.Source: §1 · pp. 1–2
2 PROBLEM AND SHARP INTERMEDIATE-BUDGET LAWS
For weighted minimum-norm least squares, the section establishes sharp risk laws in the upper-half intermediate-budget range and at (d,n)=(5,6). It connects these results to a simplex-block frontier and develops proof routes that realize the selected fits with full span.
2 PROBLEM AND SHARP INTERMEDIATE-BUDGET LAWS
- For ⌈3d/2⌉≤n≤2d−1, the exact law is Γd(n)=3−n/d, with matching lower bounds from shifted coordinate pairs.The upper bound uses selections that preserve the feature span.Source: §2 · p. 3
2.2 PROOF ARCHITECTURE
- Dimension induction combines a balanced simplex anchor and full-rank selection in its orthogonal complement, while maximal certificates reduce to independent lines compressed by dropping the t least costly coordinates.The budget and risk ratios close when d≥2t.Source: §2 · p. 3
2 PROBLEM AND SHARP INTERMEDIATE-BUDGET LAWS
- At (d,n)=(5,6), every finite R5 instance admits a positive-weight selection of at most six points with risk ratio at most 11/5 in the infimum, and a seven-point instance attains 11/5.The upper bound allows a limiting sequence; it does not assert attainment for every instance.Source: §2 · p. 3
2.1 INTERMEDIATE-BUDGET LANDSCAPE
- For n=d+s, the simplex-block allocation frontier includes Φd,1=⌊d²/4⌋/d; at d=5, the 3+2 partition predicts excess 6/5, which the unrestricted five-dimensional result matches.The general equality Γd(d+s)=1+Φd,s remains a target for other intermediate budgets.Source: §2.1 · p. 4
2.3 NORMALIZATION AND THE TRAINING INTERFACE
- A rank-r positive circuit plus 5−r roots independent modulo its span gives a six-row full-rank training interface for realizing admissible fits.The circuit has r+1 roots, and the fit construction is supported by the one-sided inequalities vᵢᵀz≤1.Source: §2.3 · p. 5
3 THE EXHAUSTIVE GEOMETRY BEHIND THE UPPER BOUND
The five-dimensional upper bound is reduced to exhaustive circuit-rank cases and two mechanisms that bound the normalized excess. The argument turns geometric bounds into risks of actual full-rank training fits, including in the shared-root branch.
3 THE EXHAUSTIVE GEOMETRY BEHIND THE UPPER BOUND
- The four circuit-rank configurations are exhaustive; together they bound the normalized five-dimensional excess by 6/5, with simpler branches attaining bounds at most one.The shared-root rank-three case is handled by signed polar faces; the other cases use quotient lines, circuit covers, or circuit-plane intersections.Source: §3 · pp. 5–6
3.1 FIRST MECHANISM: A THREE-PLUS-TWO COVER
- For a rank-three and rank-two circuit-span cover of E, the outside sets are disjoint, so α + β ≤ 1; the cited maximum occurs at 2α = 3(1 − α), giving α = 3/5.For a (3,3) cover, the same calculation gives bound one.Source: §3.1 · p. 6
3.2 SECOND MECHANISM: CIRCUIT-PLANE GRAPHS AND ACTUAL RISK
- Circuit-plane graph probabilities control the risk of realizable fits, yielding a finite distribution with excess at most 6/5.The graph argument handles graphs with triangles or four-cycles separately from those without them; the abstract five-cycle bound is sharp but is not itself a regression lower bound.Source: §3.2 · pp. 6–7
3.3 THE SHARED-ROOT BRANCH: THE INVARIANT THAT CLOSES THE CASES
- In the shared-root branch, crossing-root exclusions constrain the remaining configurations; polar-face geometry then supplies a realizable face or vertex with squared norm at most one.The exclusions rule out coexistences that would make a root good or create a rank-four or rank-five circuit.Source: §3.3 · pp. 7–8
4 TRANSFER, ATTAINMENT, AND THE MATCHING EXAMPLE
The transfer argument proves the full upper bound across zero-residual and deficient-rank cases. A seven-point construction attains the matching lower bound Γ5(6) ≥ 11/5.
4 TRANSFER, ATTAINMENT, AND THE MATCHING EXAMPLE
- The root construction proves the full upper bound, handling zero-residual rows, deficient ranks, and positive-weight limits.For rows with η0 = 0 and ξ0 ≠ 0, it constrains z to ξ⊥, applies the four-dimensional five-row theorem, then lifts with a positive weight; the excess is at most 6/5.Source: §4 · p. 8
- Γ5(6) ≥ 11/5 is attained by a seven-point example with three- and two-dimensional blocks of masses 2/5 and 3/5.Any full-rank support of size at most six leaves one block with exactly its dimension in rows, forcing excess 6/5; retaining the full tetrahedron and two triangle rows attains it.Source: §4 · p. 8
5 CERTIFICATE RIGIDITY AND THE PENULTIMATE BOUNDARY
Full-span certificate complexity characterizes exact recovery and identifies a rigid extremal structure. The resulting one-point penalties yield the sharp penultimate-boundary law and its extremal conditions.
5 CERTIFICATE RIGIDITY AND THE PENULTIMATE BOUNDARY
- Exact minimum-norm recovery requires stationarity and orthogonality to the selected Hessian’s kernel; a full-span certificate enforces Uq = U.κ(D) is the minimum support size of a full-span certificate.Source: §5 · p. 9
- The full-span certificate complexity satisfies m ≤ κ(D) ≤ m + r ≤ 2m ≤ 2d, with κ(D) = 1 when m = 0.Here m = dim U and r = dim span{gi : gi ≠ 0}. The maximum κ(D) = 2m holds exactly when nonzero features lie on m independent lines and all have nonzero gradients.Source: §5 · p. 9
- Two points recover µj exactly; the one-point penalty is sharp at two equidistant target levels of equal effective mass when block loss is positive.When κ(D) ≤ 2d − 1, selection is exact; otherwise, the construction compresses the least costly line to one point and retains two points on each other line.Source: §5 · p. 9
- Γd(2d −1) = 1 + 1/d for every d ≥ 1, attained by uniform coordinate pairs (ej, 0), (ej, 2).All upper bounds in the section are attained by explicit selections.Source: §5 · p. 9
- Every extremizer has maximal certificate complexity, zero zero-feature loss, equal positive block losses, and factor-two extremal blocks; these conditions are necessary, not sufficient.The analysis also gives lower bounds on canonical rank-deficient projection selections.Source: §5 · p. 9
6 CONCLUSION
The paper establishes sharp weighted-support risk laws in the upper-half budget interval and at (d, n) = (5, 6). The conclusion connects them through the simplex-block frontier and reports formal verification.
6 CONCLUSION
- For the upper-half interval, Γd(n) = 3 − n/d holds exactly, and its dataset-level statement has a complete Lean 4 verification; balanced anchors, positive-weight lifting, and independent-line compression close the dimension induction.Source: §6 · p. 9
- At (d, n) = (5, 6), circuit analysis proves the simplex-block prediction 11/5 for arbitrary configurations.The general simplex-block frontier connects this result with the upper-half budget laws.Source: §6 · p. 9
- The supplied formal project checks the upper-half theorem and its foundational dependencies; the symbolic checker verifies the stated finite algebraic identities.Appendix D proves the block frontier and gives a matrix formulation for further intermediate budgets.Source: REPRODUCIBILITY STATEMENT · p. 9
A.1 EXACT CERTIFICATES AND INTRINSIC-RANK RIGIDITY
Exact recovery is characterized by a selected gradient balance together with preservation of the full feature span, and certificate complexity is bounded using intrinsic rank. In the resulting line decomposition, one-point compression has a sharp factor-two profile.
A.1 EXACT CERTIFICATES AND INTRINSIC-RANK RIGIDITY
- A selection exactly recovers the full-data minimum-norm solution when its selected gradient balances and its selected feature span equals the full span.The full-span certificate complexity is the minimum support size among selections satisfying both conditions.Source: §A.1 · p. 11
- When the nonzero-gradient rank r is below the observed dimension m, κ(D) ≤ 2m − 1; when m < d, κ(D) ≤ 2d − 2.The proof compresses gradient balance to at most 2r atoms, then adds at most m − r zero-gradient features to restore the full span while keeping positive weights.Source: §A.1 · p. 11
- At maximal intrinsic complexity, κ(D) = 2m forces opposite gradient pairs on m independent basis lines, provided every nonzero feature has a nonzero gradient.The maximal ambient case κ(D) = 2d holds exactly when U = R^d and the stated basis-line condition holds.Source: §A.1 · pp. 11–12
A.2 EXACT ONE-DIMENSIONAL COMPRESSION
- A one-point line selection has loss at most twice the optimal line loss, with equality exactly for two equally weighted target levels symmetric about their mean.When the optimal line loss is zero, a one-point selection is exact; retaining a nonzero feature on each independent line preserves the full span.Source: §A.2 · pp. 12–13
A.3 INSTANCE-DEPENDENT AND SHARP BOUNDARY LAWS
The penultimate-budget result separates instances with a small exact certificate from those requiring a linewise compression bound. Its sharp boundary extremizers have rigid line structure, while the certificate proofs preserve positive weights and full span.
A.3 INSTANCE-DEPENDENT AND SHARP BOUNDARY LAWS
- When κ(D) = 2d, equality requires d independent lines, zero zero-feature loss, equal positive block losses, and factor-two one-point extremizers on every block.The effective targets on each block take two symmetric levels with equal total effective mass.Source: §A.3 · p. 14
- At budget 2d − 1, the sharp worst-case risk ratio is 1 + 1/d, attained by a shifted coordinate-pair instance.Any feasible selection leaves some coordinate with at most one selected endpoint, while selecting full pairs on d − 1 coordinates and one endpoint on the last attains the bound.Source: §A.3 · pp. 14–15
A.4 CONVEX-GEOMETRIC PRELIMINARIES
- Steinitz’s relative-interior theorem preserves full-dimensional balance using at most 2r points in an r-dimensional space; ordinary Carathéodory compression need not preserve that property.The retained subset still has zero in the relative interior of its convex hull.Source: §A.4 · p. 16
A.5 PROOF OF THE INTRINSIC-DIMENSION CERTIFICATE BOUND
- The intrinsic certificate bound is κ(D) ≤ m + r ≤ 2m ≤ 2d, with sharper consequences when r < m or m < d.The construction balances active gradients using at most 2r points and adds zero-gradient features only as needed to complete the observed span.Source: §A.5 · p. 16
A.6 PROOF OF MAXIMAL CERTIFICATE-COMPLEXITY RIGIDITY
Maximal certificate complexity forces a rigid geometry: the active features lie on independent basis lines with opposite gradient pairs, and a full-span certificate must use both signs on every line.
A.6 PROOF OF MAXIMAL CERTIFICATE-COMPLEXITY RIGIDITY
- If κ(D) = 2m, a full-dimensional interior balancing set must be an inclusion-minimal positive spanning set of maximal size, hence consists of opposite pairs on basis lines.A smaller positively spanning subset would yield a smaller full-span certificate.Source: §A.6 · p. 17
- Mixed active gradients and nonzero zero-gradient features would each create a certificate with at most 2m − 1 points, so neither can occur under maximality.Thus every nonzero feature lies on one of the independent basis lines.Source: §A.6 · p. 17
- Conversely, balancing separately on each of m independent lines requires at least two selected points per line, giving κ(D) = 2m.The coordinate map from U to basis inner products is invertible even when the basis is not orthogonal.Source: §A.6 · pp. 17–18
B.1 NORMALIZED ROOTS AND REALIZABLE TRAINING OUTPUTS
The five-dimensional six-row analysis represents admissible training outputs through positive circuits and interpolation, then bounds their risk using circuit covers and polar geometry. For shared-vertex circuit configurations, the proof classifies exceptional roots and restricts which can coexist.
B.1 NORMALIZED ROOTS AND REALIZABLE TRAINING OUTPUTS
- A rank-r positive circuit plus 5 − r independent quotient roots yields a limit of admissible six-row training outputs when the circuit evaluations stay below one.Positive circuit weights balance the normal equations, while the quotient roots interpolate and make the selected span full.Source: §B.1 · p. 19
- For two circuit spans covering the exceptional roots, δ6 ≤ 1 when both have rank three, and δ6 ≤ 6/5 when their ranks are three and two.The bounds follow from the outside-mass constraint α + β ≤ 1 and the corresponding circuit-plane probability bounds.Source: §B.1 · p. 20
B.2 SIGNED POLAR FACES AND CONFIGURATIONS OF CIRCUIT SPANS
- Polar-face geometry gives δ6 ≤ 1 under either a three-span cover condition or the specified four-span configuration; two nonparallel active roots in the relevant region also force a realizable vertex or its negative.These arguments handle tied and degenerate faces through active-space rigidity.Source: §B.2 · p. 21
B.3 ALL EXTENSIONS OF A SHARED-VERTEX DOUBLE TETRAHEDRON
- With a shared-vertex double tetrahedron, exceptional roots are classified into crossing-root forms, and compatibility excludes simultaneous exceptional roots of different types.The text also restricts coexisting exceptional roots to common indices in the stated A, B, and C cases.Source: §B.3 · pp. 21–22
- When exceptional A or B roots occur, the corresponding branch reduces to the three- or four-span cases; crossing C roots are handled separately by a two-line argument for stars.The cited branch results give δ6 ≤ 1 for the stated A/B cases and for the C-star case.Source: §B.3 · p. 22
B.4 SYSTEMS WHOSE POSITIVE CIRCUITS HAVE RANK AT MOST TWO
The low-rank circuit analysis bounds selected excess risk by organizing positive triangles through their circuit planes. The remaining rank-three cases and the seven-point construction complete the five-dimensional six-point law.
B.4 SYSTEMS WHOSE POSITIVE CIRCUITS HAVE RANK AT MOST TWO
- Distinct circuit planes with nonzero intersection share an oriented vertex direction, while a family in a three-space with no common line has at most three planes.A plane sharing a line with a family of distinct circuit planes has zero intersection with at most two members.Source: §B.4 · p. 24
- δ6 ≤1 when circuit planes contain a triangle or four-cycle in their disjointness graph, or when no circuit planes exist.For the short-cycle case, all roots lie in a four-space plus a complementary line; the no-plane case uses five independent lines.Source: §B.4 · pp. 25–26
B.5 THE REMAINING RANK-THREE CASE AND THE GLOBAL ROOT BOUND
- In the remaining rank-three branch, crossing exceptional roots form a star in a bipartite graph, yielding δ6 ≤1; without them, the (3, 2) cover gives δ6 ≤6/5.The branch assumes the shared-vertex configuration is absent.Source: §B.5 · pp. 26–27
B.6 TRANSFER TO THE ORIGINAL WEIGHTED REGRESSION PROBLEM
- The weighted-regression transfer handles deficient ranks and pure-residual rows, giving a risk-ratio infimum at most two in the latter case.The rank-four step uses the four-dimensional five-point bound of (Zhang, 2026, Theorem 47), extended to positive evaluation weights.Source: §B.6 · pp. 27–28
B.7 A MATCHING SEVEN-POINT CONSTRUCTION, INCLUDING DEFICIENT RANKS
- 11/5 is attained by a seven-point construction, proving Γ5(6) ≥11/5 and matching the upper bound.The construction also rules out deficient-rank selections as better choices: their excess is greater than 6/5.Source: §B.7 · p. 28
C COMPLETE PROOF OF THE UPPER-HALF LAW
The proof combines positive-spanning certificates, a full-span lifting argument, and dimension induction to obtain the upper-half budget bound. A coordinate-pair dataset attains the matching lower bound, and the dataset-level theorem is formally verified in Lean 4.
C.1 CERTIFICATES AND POSITIVE SPANNING SETS
- Positive-spanning compression bounds positive bases by 2r elements and supplies balanced simplex anchors for smaller certificates.A positive basis of size 2r −j contains a balanced simplex of dimension between 2 and j + 1.Source: §C.1 · pp. 29–30
C.2 THE MAXIMUM-CARDINALITY BRANCH USES THE COMPLETE DATASET
- When a minimum certificate has 2d active rows, the complete gradient set lies on d independent lines, enabling compression of the t least costly lines.The selected rows retain full span, and the independent-line construction returns the required minimum-norm fit.Source: §C.2 · p. 30
C.3 BALANCED ANCHORS AND AN ACTUAL POSITIVE-WEIGHT LIMIT
- A balanced anchor reduces the problem to its orthogonal complement, and positive-weight lifting produces a legal full-span selection with risk arbitrarily close to the projected bound.The anchor and projected selection together use at most the sum of their support sizes.Source: §C.3 · pp. 30–31
C.4 DIMENSION INDUCTION AND DEFICIENT RANKS
- A full-rank selection uses at most max{1, 2d −t} rows and has risk at most (1 + t/d)L⋆ + η when 2t ≤d.Dimension induction applies the projected result through balanced anchors and lifts it to an actual positive-weight selection.Source: §C.4 · p. 31
C.5 MATCHING LOWER BOUND, INCLUDING OMITTED COORDINATES
- The uniform dataset of coordinate pairs (e_j, 1) and (e_j, 3) attains the matching lower bound 1 + t/d by retaining one endpoint on exactly t coordinates.Omitted coordinates are handled by the minimum-norm rule, and the construction covers selections that omit features.Source: §C.5 · p. 32
C.6 FORMAL THEOREM AND DEPENDENCY MAP
- The Lean 4 formalization verifies the complete dataset-level upper bound and the attaining lower-bound construction underlying the equality for Γd.The dependency map identifies the independent-line structure, line compression, anchor lifting, and intrinsic-rank reduction components.Source: §C.6 · p. 32
D THE BLOCK FRONTIER AND THE MATRIX FORMULATION
The block frontier derives sharp budget-dependent excess bounds from orthogonal simplex blocks and balanced partitions. A matrix formulation expresses the broader span-preserving selection problem and identifies bounds already supplied by the paper.
D.1 A BASIS FACET FOR ONE BLOCK
- A basis facet in an a-dimensional block has risk at most (a+1) times the block optimum, with an interpolant independent of positive training weights.For zero optimal loss, any basis facet is exact.Source: §D.1 · p. 32
D.3 OPTIMIZATION OVER BLOCK LOSSES
- For orthogonal blocks, completing s blocks with largest a_jL⋆_j gives a full-rank selection with at most d+s rows and excess ratio at most Ψ_s(a).Translated block constructions attain the same worst-case value in the supremum.Source: §D.3 · p. 33, §D.2 · p. 33
D.4 EVALUATING THE FRONTIER
- The worst-case block value over partitions is Φ_d,s, and its maximizing partition is balanced for each fixed number of blocks.For s=1, Φ_d,1 = ⌊d^2/4⌋/d; at (d,s)=(5,1), the partition is 3+2 with masses 2/5 and 3/5.Source: §D.3 · p. 33, §D.4 · pp. 33–34
D.5 SPARSE WEIGHTED ORTHOGONALIZATION AS THE NEXT TARGET
- The proposed sparse diagonal-matrix bound is equivalent to a universal full-rank, span-preserving selected-risk infimum bound of 1+c.The exact-attainment version requires one admissible selection with ε=0.Source: §D.5 · p. 34
- Theorem 1 supplies c=(2d−n)/d on the upper-half budget interval, while Theorem 2 supplies c=6/5 at (5,6).The proposed general block prediction is c=Φ_d,s.Source: §D.5 · p. 34
E.1 REPRODUCTION AND SCOPE
- The exact-rational verification script checks specified identities, ranks, supports, and graph probabilities, but does not test all root configurations.Structural rank and positivity arguments remain part of the paper’s proof rather than the script’s finite checks.Source: §E.1 · p. 34
E.2 ALGEBRA-TO-PROOF MAPPING
The appendix maps symbolic checks to mathematical objects and distinguishes diagnostic computations from the structural arguments that establish the proof. It also indexes the dependencies used for the upper bound and lower construction.
E.2 ALGEBRA-TO-PROOF MAPPING
- The verification script’s identifiers map to named relations, block-restriction representations, the seven-point construction, and graph probabilities.The script checks do not replace the circuit-plane intersection lemmas or the transfer from graph probabilities to regression risk.Source: §E.2 · p. 35
E.3 DEPENDENCY INDEX
- The upper-bound dependency index assigns separate roles to the training interface, active-space restrictions, shared-root and other rank-three cases, rank-two plane graphs, and regression degeneracies.The only lower-dimensional interior input is the four-dimensional five-point upper bound from Zhang (2026, Theorem 47); the exact lower bound is in Appendix B.7.Source: §E.3 · p. 35