揭示了半空间模型在不同条件下泛化误差的精细行为，突破传统最坏情况界限。
A Fine-Grained Understanding of Uniform Convergence for Halfspaces
- 通过分层风险带与临界楔定位分析，构建对齐结构特性的新泛化边界。
- 同维下一致假设的样本误差可达 Θ(d ln(n/d)/n)，真实情形下误差为 O(1/n)。
- 适用于理论学习、统计推断与高维几何建模研究者，尤其关注泛化机制者。
我们研究了半空间在超越最坏情况 VC 界之外的细粒度统一收敛行为。对于 ℝᵈ（d≥2）中的非齐次半空间，我们证明标准一阶 VC 界本质上是紧致的：即使一致假设仍可能产生 Θ(d ln(n/d)/n) 的总体误差；在无假设设定下，偏差在真实误差 τ 处表现为 √(τ ln(1/τ))。相比之下，ℝ² 中的齐次半空间表现出显著不同行为：在可实现情形下，所有与样本一致的假设误差均为 O(1/n)；在无假设情形下，我们通过关键楔定位论证，对每个二进制风险带建立了无对数项的偏差上界。并集所有带仅引入 ln ln n 的额外开销，且我们建立了匹配的下界，表明该开销不可避免。这些结果共同给出了半空间统一收敛的细粒度、近乎完整的图像，揭示了精确的维度与结构阈值。
原文摘要 · Abstract (English)
We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in $\mathbb{R}^d$ with $d\ge 2$, we show that standard first-order VC bounds are essentially tight: even consistent hypotheses can incur population error $Θ(d\ln(n/d)/n)$, and in the agnostic setting the deviation scales as $\sqrt{τ\ln(1/τ)}$ at true error $τ$. In contrast, homogeneous halfspaces in $\mathbb{R}^2$ exhibit a markedly different behavior. In the realizable case, every hypothesis consistent with the sample has error $O(1/n)$. In the agnostic case, we prove a bandwise, log-free deviation bound on each dyadic risk band via a critical-wedge localization argument. Unioning over bands incurs only a $\ln\ln n$ overhead, and we establish a matching lower bound showing this overhead is unavoidable. Together, these results give a fine-grained and nearly complete picture of uniform convergence for halfspaces, revealing sharp dimensional and structural thresholds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。