Optimal Bounds on the VC-dimension
read the original abstract
The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: $k$-fold unions/intersections of half-spaces, and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the 1989 foundational paper of Blumer, Ehrenfeucht, Haussler and Warmuth as well as by Eisenstat and Angluin and Johnson.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
Alternating minimization with spectral-plus-random-search initialization converges geometrically and attains near-minimax optimal estimation rates for max-affine regression when k is fixed and the design is random.
-
Sparse Max-Affine Regression
Sp-GD recovers sparse max-affine parameters to epsilon accuracy with O(s log(d/s)) samples in the noise-free case under sub-Gaussian assumptions, supported by sparse-PCA initialization and an RMD transformation for ge...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.