A Fine-Grained Understanding of Uniform Convergence for Halfspaces
This work provides a nearly complete fine-grained understanding of uniform convergence for halfspaces, revealing sharp dimensional and structural thresholds that refine classical VC theory.
The paper characterizes the uniform convergence behavior of halfspaces, showing that first-order VC bounds are tight for inhomogeneous halfspaces in d≥2, while homogeneous halfspaces in R^2 achieve O(1/n) error in the realizable case and a log-free deviation bound with only a ln ln n overhead in the agnostic case, with matching lower bounds.
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.