{"id":"arxiv/2605.06004","url":"https://arxiv.org/abs/2605.06004","tags":["cs.LG","cs.AI","math.ST"],"score":0,"title":"A Fine-Grained Understanding of Uniform Convergence for Halfspaces","domain":"cs.LG","source":"arxiv","authors":["Aryeh Kontorovich","Kasper Green Larsen"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-07","reactions":{}}