A Fine-Grained Understanding of Uniform Convergence for Halfspaces

• URL: http://arxiv.org/abs/2605.06004v1
• Date: Thu, 07 May 2026 10:53:49 GMT
• Title: A Fine-Grained Understanding of Uniform Convergence for Halfspaces
• Abstract summary: We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds.<n>For inhomogeneous halfspaces in $mathbbRd$ with $dge 2$, we show that standard first-order VC bounds are essentially tight.<n>In contrast, homogeneous halfspaces in $mathbbR2$ exhibit a markedly different behavior.
• Score: 31.579168044707462
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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.

Related papers

• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition.<n>We propose a regularization-based framework combining a Huberized data fidelity with generalized folded-concave penalties.<n>We derive estimation error bounds of order $sqrtslog(n)/m$ that hold at emphevery localized stationary point.
  arXiv  Detail & Related papers  (2026-07-12T07:29:39Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  We study the complexity of smoothed learning of halfspaces on $pm 1n$ under the uniform distribution in the model of citetKM25.
  arXiv  Detail & Related papers  (2026-05-04T08:53:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation.<n>We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [21.64772960240025]
  We show that as the dimension $d$ of the problem increases, the number of iterations required to ensure convergence within a desired error increases.<n>A key technical challenge we address is the lack of a one-step contraction property in the $W_2,ellinfty$ metric to measure convergence.
  arXiv  Detail & Related papers  (2024-08-20T01:24:54Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Improved Hardness Results for Learning Intersections of Halfspaces [2.1393480341554736]
  We show strong (and surprisingly simple) lower bounds for weakly learning intersections of halfspaces in the improper setting. We significantly narrow this gap by showing that even learning $omega(log log N)$ halfspaces in $N$ takes super-polynomial time. Specifically, we show that for any $k$ halfspaces in dimension $N$ requires accuracy $N-Omega(k)$, or exponentially many queries.
  arXiv  Detail & Related papers  (2024-02-25T05:26:35Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
  We show the solution to the problem of learning surrogate learning homogeneous halfspaces in the distribution-specific model. In any convex distributions, we show that the misclassification error inherently leads to misclassification error of halfspace.
  arXiv  Detail & Related papers  (2020-06-11T18:55:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.