Exact Risk Ratios for Weighted Data Selection in Linear Regression

• URL: http://arxiv.org/abs/2608.28007v1
• Date: Fri, 28 Aug 2026 07:19:17 GMT
• Title: Exact Risk Ratios for Weighted Data Selection in Linear Regression
• Abstract summary: Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem.<n>A selector sees a finite dataset $D subseteq mathbbRd times mathbbR$, picks at most $n$ examples together with nonnegative weights, and hands the weighted least squares objective to the minimum-norm ERM.<n>We give explicit counterexamples showing that several shorter routes fail, and constructive sign-time selection algorithms for all proved cases.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression [0.0]
  We prove that the minimal budget of weighted examples that recovers the full-data loss on every finite dataset is exactly $n*(d,m)=(m+1)d$.<n>As a we correct an erroneous claim circulating in a recent unrefereed preprint, exhibiting an explicit dataset with $m=2$ on which no weighted selection of $2d$ points recovers the optimal loss.
  arXiv  Detail & Related papers  (2026-08-31T05:04:49Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck, Li and Nagaraj conjectured that, for generic data, any two-layer neural network with $m$ neurons that fits noisy labels must have Lipschitz constant.<n>We prove the conjectured law, up to one logarithmic factor, for every continuous piecewise-linear activation in particular for ReLU networks.
  arXiv  Detail & Related papers  (2026-07-08T17:44:15Z)
• The Exact Worst-Case Tail Probability under Bounded Kurtosis [39.91890433860882]
  We determine exactly what a kurtosis bound buys for one-sided tail control.<n>For the class $mathcalC()$ of real random variables with mean $0$, variance $1$, and fourth moment at most $$, the skewness left free.
  arXiv  Detail & Related papers  (2026-07-06T15:40:54Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• $O(k)$-Equivariant Dimensionality Reduction on Stiefel Manifolds [2.0818404738530525]
  Many real-world datasets live on high-dimensional Stiefel and Grassmannian manifold, $V_k(mathbbRN)$ and $Gr(k, mathbbRN)$ respectively.<n>We propose an algorithm called textitPrincipal Stiefel Coordinates (PSC) to reduce data dimensionality from $ V_k(mathbbRN)$ to $V_k(mathbbRn)$ in an textit$O(k)$-equivariant manner
  arXiv  Detail & Related papers  (2023-09-19T17:21:12Z)
• Near-Optimal Model Discrimination with Non-Disclosure [19.88145627448243]
  We first consider the case of a well-specified linear model with squared loss. We derive sample complexity of a similar form, even under misspecification.
  arXiv  Detail & Related papers  (2020-12-04T23:52:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.