A Fine-Grained Understanding of Uniform Convergence for Halfspaces

We study the fine-grainded 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 $\Theta(d\log(n/d)/n)$, and in the agnostic setting the deviation scales as $\sqrt{\tau\log(1/\tau)}$ at true error $\tau$. 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 $\log\log 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.

We study how well simple linear classifiers can generalize from training data, going beyond the usual worst-case guarantees. These classifiers, called halfspaces, are among the most basic tools in machine learning: they separate data points by a line, plane, or higher-dimensional analogue. For general halfspaces in dimension d≥2, we show that the standard theory is essentially the best possible. Even when a classifier perfectly fits the training data, its true error can still be as large as the classical bounds predict. In noisy settings, where perfect classification is impossible, the fluctuations in error also match the known worst-case behavior. Surprisingly, the picture changes completely for halfspaces through the origin in the plane. In this special two-dimensional setting, any classifier that fits the data has very small true error, proportional to 1/n. For noisy data, we prove nearly optimal bounds that avoid an extra logarithmic loss on each error scale. A small loglogn loss remains when combining all scales, and we show that this loss is unavoidable. Overall, the results identify exactly when the usual pessimistic bounds are tight and when the geometry of the classifier class leads to substantially better generalization.