A Fine-Grained Understanding of Uniform Convergence for Halfspaces

arXiv:2605.06004v1 Announce Type: cross
Abstract: We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in $mathbbR^d$ with $dge 2$, we show that standard first-order VC bounds are essentially tight: even consistent hypotheses can incur population error $Theta(dln(n/d)/n)$, and in the agnostic setting the deviation scales as $sqrttauln(1/tau)$ at true error $tau$. In contrast, homogeneous halfspaces in $mathbbR^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 $lnln 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.