arXiv:2608.28007cs.LGmath.ST2026-08被引 1

解决线性回归加权数据选择的最优风险比问题,给出精确解。

Exact Risk Ratios for Weighted Data Selection in Linear Regression

  • 提出基于梯度正向张成的几何分析框架,刻画最优加权策略。
  • 证明当 n=2d-1 时风险比为 1+1/d,d=3,n=4 时为 5/3,d=4,n=5 时为 2。
  • 适用于理论分析与小样本加权选择场景,适合关注泛化保证的研究者。

Hanneke 等人(COLT 2025)提出了一个开放问题:给定有限数据集 $D \subseteq \mathbb{R}^d \times \mathbb{R}$,选择最多 $n$ 个带非负权重的样本,提交给最小范数经验风险最小化(ERM)。记 $F_w(d,n)$ 为返回预测器在全集 $D$ 上损失与最优损失之比的最坏情况值。已知当 $n<d$ 时 $F_w(d,n)=\infty$,$n=d$ 时 $F_w(d,d)=d+1$,$n\ge 2d$ 时 $F_w(d,n)=1$,但 $d<n<2d$ 区间未知。本文确定了多个情形下的精确值:对任意 $d$,有 $F_w(d,2d-1)=1+1/d$;进一步证明 $F_w(3,4)=5/3$,$F_w(4,5)=2$。对于中间预算 $n=d+k$,给出下界 $F_w(d,d+k) \ge 1+Γ_{d,k}$,其中 $Γ_{d,k}$ 为平衡划分的调和量,并在具备正交电路块结构的数据集中达到该界。三者均等于 $1+Γ_{d,k}$,作者猜想此式在整个开区间成立。上界证明基于损失梯度的刚性定理、$\mathbb{R}^3$ 与 $\mathbb{R}^4$ 中小正基的分类与结构简化,以及不依赖维度的极值基论证,将符号锥几何转化为五点选择。同时提供反例说明若干简略路径失败,并给出所有证明情形下的多项式时间构造算法。

原文摘要 · Abstract (English)

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.

线性回归加权选择风险分析优化理论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。