PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Risk Ratios for Weighted Data Selection in Linear Regression

Guangjian Zhang

arXiv:2608.28007v1cs.LGmath.ST

TL;DR

This paper studies the unresolved weighted data-selection ratio for linear regression between budgets d and 2d. Using geometric analyses of positive bases and sign cones, it proves exact values in three cases, establishes structured-class minimax results, and conjectures the formula holds throughout the open regime.

  • Problem

    The paper addresses the unresolved value of the worst-case weighted data-selection ratio for linear regression in the budget regime d<n<2d.

  • Method

    The proofs combine positive-basis classifications, circuit decompositions, sign-cone geometry, and an extremal-basis argument for reducing configurations to small selections.

  • Results

    The conjectured formula holds for n=2d−1, (d,n)=(3,4), and (4,5), and is exact for orthogonal circuit-block systems.

  • Takeaways & Limitations

    The proved cases support the conjecture F_w(d,d+k)=1+Γ_d,k throughout the open regime while identifying orthogonal circuit-block systems as an exactly solved class.

  • Takeaways & Limitations

    The orthogonal circuit-block characterization is stated for datasets rather than whitened systems alone because whitening does not preserve the underlying minimum-norm tie rule.

Abstract

from arXiv · show

Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem. A selector sees a finite dataset $D \subseteq \mathbb{R}^d \times \mathbb{R}$, picks at most $n$ examples together with nonnegative weights, and hands the weighted least squares objective to the minimum-norm ERM. Writing $F_w(d,n)$ for the worst-case ratio between the loss of the returned predictor on all of $D$ and the optimal loss, they proved $F_w(d,n)=\infty$ for $n<d$, $F_w(d,d)=d+1$ and $F_w(d,n)=1$ for $n \ge 2d$, and asked for the value in the open regime $d<n<2d$. We determine this value in 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 further prove $F_w(3,4)=5/3$ and $F_w(4,5)=2$, the two smallest cells not covered by the endpoint formula. For every intermediate budget $n=d+k$ we prove the lower bound $F_w(d,d+k) \ge 1+Γ_{d,k}$, where $Γ_{d,k}$ is an explicit harmonic quantity over balanced partitions, and we show that this bound is the exact minimax value over the class of datasets whose whitened gradient systems carry an orthogonal circuit-block structure. All three exact values match $1+Γ_{d,k}$, and we conjecture that equality holds throughout the open regime. The upper bound proofs run on a common geometric spine: a rigidity theorem for positive spanning configurations of loss gradients, classifications and structural reductions of small positive bases in $\mathbb{R}^3$ and $\mathbb{R}^4$, and a dimension-free extremal-basis argument that converts sign-cone geometry into five-point selections. We also give explicit counterexamples showing that several shorter routes fail, and constructive polynomial-time selection algorithms for all proved cases.

1. Introduction

This paper resolves several open cases for weighted data selection in linear regression, including the entire top layer of the open regime and the two smallest uncovered cells. It establishes a harmonic lower bound, proves exactness for an orthogonal circuit-block model class, and conjectures that bound is universally tight.

  • Exact values: Fw(d, 2d −1) = 1 + 1/d for all d ≥1, resolving the top of the open regime.This includes the smallest open cell d = 2 and proves a value previously stated without proof.
  • Exact values: Fw(3, 4) = 5/3, refuting the interpolation guess 1 + (2d −n)^2/d, which predicts 7/3.The result concerns one of the two smallest cells not covered by the endpoint formula.
  • Exact values: Fw(4, 5) = 2, determining the other smallest cell not covered by the endpoint formula.Together with the results for budgets 2d −1 and cell (3, 4), this is one of three exact values matching 1 + Γd,k.
  • General bounds: For every 1 ≤ k ≤ d −1, Fw(d, d + k) ≥ 1 + Γd,k, where Γd,k is defined through balanced positive-integer partitions.All three exact values above equal 1 + Γd,k.
  • Exact model class: On datasets whose whitened gradients split into orthogonal circuit blocks, the worst-case excess at budget d + k equals Γd,k via an explicit budget-allocation program.The paper conjectures Fw(d, d + k) = 1 + Γd,k throughout the open regime.
  • Proof architecture: The proofs combine gradient rigidity, classifications and reductions of small positive bases, and a dimension-free extremal-basis principle converting sign-cone geometry into selections.The endpoint argument uses whitening, positive spanning, orthogonality, and a harmonic cost for omitting one point on the lightest line.

2. Preliminaries

This section formalizes weighted selection with the min-norm ERM and develops the geometric and regression preliminaries used in later risk-ratio arguments. It also records a volume-sampling interpolation guarantee and structural lemmas for positive spanning configurations.

  • Selection framework: Weighted selection chooses at most n dataset examples with nonnegative weights, while the learner returns the unique minimum-norm element among ERM minimizers.Selections are counted by effective support: repeated points merge weights, zero-weight points are unselected, and unused slots may be filled by repetitions.
  • Regression certificate: (r + 1)ρ⋆ bounds the full-data loss of some interpolation point based on r linearly independent features.The guarantee follows from size-r volume sampling and also covers the realizable case ρ⋆ = 0.
  • Positive spanning geometry: m + 1 ≤ |B| ≤ 2m for every positive basis B of R^m, with maximal bases consisting of antipodal rescalings of a linear basis.When |B| = 2m, B has the form {a1, −λ1a1, …, am, −λmam} for positive scalars λj.
  • Positive spanning geometry: A positively spanning configuration that cannot be reduced to at most 2m − 1 points must lie on the m basis axes.The rigidity lemma forces every element onto one of the lines Ra_j.
  • Positive spanning geometry: A minimum-cardinality positive spanning set remains minimal after quotienting by the span of one of its positive circuits.The circuit is collapsed to the quotient origin, while all remaining images form a positive basis of the quotient space.

3. The budget 2d −1

The section proves the exact endpoint value F_w(d,2d−1)=1+1/d for every d≥1. Its upper bound uses a whitened-system interface theorem, while a 2d-point construction supplies the matching lower bound.

  • Exact value: 1+1/d is the exact value of F_w(d,2d−1) for every d≥1.The upper bound is established through an interface theorem for whitened systems; the result also resolves the smallest open cell in the cited question.
  • Upper bound: 2d−1 selected points suffice to form a strictly convex weighted objective whose minimizer has squared norm at most 1/d.The construction selects one point on one line and antipodal pairs on the other d−1 orthogonal lines, yielding 1+2(d−1)=2d−1 points.
  • Matching lower bound: At most 2d−1 selected point types must omit one of 2d signed coordinate examples, forcing some coordinate to deviate from the optimum by at least 1.The coordinate-separable construction uses D_d,c and the min-norm rule when neither point of a coordinate is selected.

4. A lower bound for every intermediate budget

For every intermediate budget n=d+k, the section constructs balanced block instances yielding the lower bound F_w(d,d+k) ≥ 1+Γ_{d,k}. The quantity Γ_{d,k} is governed by balanced integer partitions, and the construction is exactly solvable within its block structure.

  • Partition quantity: 1+Γ_{d,k} is obtained by maximizing over s∈{k+1,…,d} the reciprocal-partition quantity, whose minimum is attained by a balanced partition.The endpoints are Γ_{d,0}=d and Γ_{d,d−1}=1/d, matching the known values at n=d and n=2d−1.
  • Block construction: Block instances partition R^d into s orthogonal subspaces of dimensions r_1,…,r_s summing to d, placing simplex vertices in each block.The construction contains d+s points and assigns labels using a target vector and block-specific shifts.
  • Selection constraint: At least r_j vertices must be retained from every block, because losing two vertices creates excess risk strictly above the candidate optimum.The proof analyzes the minimum-norm interpolant on an under-selected block and compares its contribution with the candidate excess cost.
  • Counting argument: With only k extra selections beyond the d-point base, at least s−k blocks lose one vertex, each contributing C, so the construction attains exactly 1+(s−k)C.Keeping k full blocks with equal within-block weights and dropping one vertex in the others realizes the bound.

5. Orthogonal circuit-block systems: an exact minimax value

Within the orthogonal circuit-block model class, the harmonic quantity Γ_{d,k} is the exact minimax excess for budgets n=d+k, matching the conjectured whole-regime value. The proof combines constructive blockwise selections with balanced simplex-block datasets attaining the bound.

  • Exact minimax value: The harmonic quantity Γ_{d,k} is the exact minimax value for orthogonal circuit-block datasets at budget n=d+k.The upper and lower directions match within this model class, so the conjectured value is exact there.
  • Upper bound construction: d+k points suffice: selecting complete circuits in k blocks and reduced blockwise selections elsewhere yields a strictly convex objective and excess bounded by Φ(r,k) ≤ Γ_{d,k}.Orthogonality makes the joint minimizer the direct sum of block minimizers, eliminating dependence on the minimum-norm tie rule.
  • Budget regimes: For k ≥ s, completing every block makes the excess zero.Here s is the number of orthogonal blocks.
  • Extremal structure: Unbalanced dimension vectors may have worst cases supported on a proper subset of blocks, while optimizing over partitions recovers the balanced formula Γ_{d,k}.The relaxation permits zero-energy limits for shut-off blocks; balanced constructions attain the value when all relevant blocks are active.
  • Lower bound construction: Every strictly positive feasible energy vector is realizable, and balanced simplex-block datasets attain the outer supremum defining Γ_{d,k}.These constructions realize the lower bound while remaining inside the dataset-level class Dr.

6. The budget 4 in dimension 3

The section establishes the exact budget-4 result in dimension 3 through a classification of five-vector positive bases and structural reductions yielding four-point selections. It also refutes a natural interpolation formula and records a limitation for the coupled five-point class.

  • Positive-basis classification: Two positive-basis types occur: κ=0 splits into a rank-2 triangle circuit and an antipodal pair, while κ>0 forms a coupled orbit of two triangles sharing one vector.This classification underlies the subsequent branch analysis.
  • Structural reduction: At most one cross type can occur, so all nonzero gradients lie in two basis planes or those planes plus one cross-type plane.This three-plane cover reduces the possible gradient configurations before constructing the four-point selection.
  • Upper-bound branches: 2: The coupled, split, and six-axis branches each admit a strictly convex selection using at most four points with ||q_hat||^2 ≤ 2.The coupled and split branches are handled by Propositions 24 and 25, while the six-axis branch is handled by Proposition 26.
  • Refuted interpolation: 7/3: The interpolation guess 1+(2d−n)^2/d predicts F_w(3,4)=7/3, but Theorem 27 refutes it at this smallest differing cell.The known endpoint values remain consistent with the guess, despite its failure here.

7. The budget 5 in dimension 4

The section proves F_w(4,5)=2, matching the lower bound with an upper bound obtained through interface reductions, positive-basis classifications, circuit completion, and an extremal-basis argument. The proof establishes five-point selections with excess at most 1 across all configurations, including the rectangle branch.

  • Main result: F_w(4, 5) = 2, with the lower bound from Theorem 13 and the upper bound assembled from four geometric and structural ingredients.The ingredients are interface results, a quotient-volume-sampling completion lemma, classifications of minimal positive bases in R4, and a dimension-free extremal-basis argument.
  • Interface reduction: 1 + ∥ˆq∥2 ≤ 5, using at most 4 points in the whitened R3 interface.Theorem 31 provides strictly positive weights and a strictly convex objective with a unique minimizer.
  • Interface reduction: 1 + ∥ˆq∥2 ≤ 5, using at most 5 points for any whitened R4 system containing an anchored point with η0 = 0 and ξ0 ≠ 0.The anchored reduction adds an outer penalty to the four-point construction in the orthogonal quotient space.
  • Positive-basis classification: 5 points achieve ∥ˆq∥2 ≤ 1 when a minimal positive spanning set has size 6 and either contains a rank-3 positive circuit or splits into complementary triangle circuits.Circuit-flat completion handles the first case, while the two-block result handles disjoint triangles without cross gradients.
  • Positive-basis classification: 5 points achieve ∥ˆq∥2 ≤ 1 for shared-endpoint crosses and for minimal positive spanning sets of size 7.These results cover additional two-block configurations after excluding rank-3 four-circuits and five-gradient positive spans.
  • Rectangle branch: 5 points achieve ∥ˆq∥2 ≤ 3/4 for size-8 minimal positive spanning sets, while rectangle closure gives ∥ˆq∥2 ≤ 1 or excess at most 1.The rectangle argument uses off-side-point generation and an extremal-basis lemma when direct finite selection is unavailable.

8. Three obstructions

This section gives exact counterexamples showing that three shorter proof routes fail, although the obstructing systems can still admit low-risk selections. The examples expose failures of small circuit-flat covers, anchor-based recursion, and simultaneous cheap-and-generated points.

  • Rectangle obstruction: 4 planes of total dimension 8 are required to cover the rectangle system’s circuit flats, while no subset of at most five vectors positively spans R^4.The system has four listed positive circuits, but the obstruction concerns proof technique rather than the value of F_w(4,5).
  • Rectangle obstruction: 10/7 < 2 is achieved by a five-point selection in the rectangle example, confirming that its obstruction does not determine F_w(4,5).The selection uses the first five rows with explicit weights and returns a predictor with full risk 10/7.
  • Anchor obstruction: 1.1097 > 1 makes both branches of the anchor route fail, yet a five-point selection on the support {0, 4, 5, 6, 7} has exact ratio 2452861/2000000 < 2.The single point 0 alone gives ratio about 1.2219, so the counterexample remains cheap for the selector.
  • Threshold obstruction: No point is simultaneously cheap and generated in the threshold family: generated points have t > 1, whereas side points have t < 1.At ε = 1/100, the exact Mahalanobis norms and threshold behavior are verified by substitution and exact-arithmetic scripts.

9. Constructive selection algorithms

The paper’s upper bounds are constructive: for fixed dimensions, its procedures achieve the stated risk ratios up to ε using polynomially many exact-arithmetic operations. They provide explicit branches for general preprocessing, the d=3 budget-4 and d=4 budget-5 cases, and orthogonal circuit-block systems.

  • General implementation: Polynomial-time procedures achieve each stated upper bound plus ε in exact real arithmetic for fixed dimensions.The ε-dependent steps use finite penalty parameters or finite interior points; rank-deficient and realizable cases return exact certificates.
  • General implementation: Positive-spanning preprocessing repeatedly deletes gradients while preserving positive spanning, using one linear program per deletion, until obtaining a positive basis of size at most 2d.If gradients span a proper subspace, the procedure returns a Steinitz certificate with rank-completing zero-gradient points.
  • Small-budget cases: Budget 4 in dimension 3 is handled algorithmically through anchor reduction, minimum-cardinality positive spanning sets, circuit detection, and comparisons among circuit-plane selections.The split case tests gradient membership in V ∪ L and compares RL against 2RV; size-6 instances use canceling pairs on the heaviest line and best single points elsewhere.
  • Small-budget cases: Budget 5 in dimension 4 is implemented by enumerating gradient subsets of size at most 2d, testing positive spanning by linear programs, and reducing feasible cone representations to support-minimal forms.For K > 1, the algorithm chooses an interior point qc and a sufficiently small t so the returned interpolation is within ε of the target risk.
  • Block systems: Orthogonal circuit-block systems allocate the budget optimally by sorting rjRj and completing the k largest blocks.This applies when the blocks are known.

10. Discussion and open problems

The paper conjectures F_w(d,d+k)=1+Γ_d,k throughout the open regime, supported by all proved exact cases and the orthogonal circuit-block minimax result. It identifies a shared geometric route toward general upper bounds and leaves variants, optimization complexity, and further structural questions open.

  • The conjecture: F_w(d,d+k)=1+Γ_d,k is conjectured for every 1≤k≤d−1.This extends the exact values established in the paper to the entire open regime.
  • The conjecture: The conjecture holds for k=d−1, (d,k)=(3,1), and (d,k)=(4,1), and exactly describes orthogonal circuit-block systems.These cases correspond to Corollary 11, Theorems 27 and 47, and Corollary 16.
  • What remains for a general upper bound: The upper-bound proofs reduce nondegenerate systems to minimal positive bases, circuit decompositions, circuit flats, and controlled coupling gradients.Absent couplings yield exact orthogonal block systems, while present couplings open cheaper selections in every analyzed case.
  • Further questions: Open directions include unweighted and vector-valued variants, optimal weighted-selection complexity, and extending the classifications of small positive bases.The selections are constructive but not optimized, and the complexity of computing an optimal weighted selection remains open.
Loading 2608.28007v1…