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 $\mathbb{R}^d$ with $d\ge 2$, we show that standard first-order VC bounds are essentially tight: even consistent...