Optimal Bounds on the VC-dimension
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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningOpen-Ended Question AnsweringSimilar Papers 제목 키워드 기반
Convergence rates for ordinal embedding
We prove optimal bounds for the convergence rate of ordinal embedding (also known as non-metric multidimensional scaling) in the 1-dimensional case. The examples witnessing optimality of our bounds arise from a result in…
Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
We provide upper bounds of the expected Wasserstein distance between a probability measure and its empirical version, generalizing recent results for finite dimensional Euclidean spaces and bounded functional spaces. Suc…
Gaussian ProcessesNaive Exploration is Optimal for Online LQR
We consider the problem of online adaptive control of the linear quadratic regulator, where the true system parameters are unknown. We prove new upper and lower bounds demonstrating that the optimal regret scales as $\wi…
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on …
Dimensionality ReductionOptimal Dimension-Free Sampling for Regularized Classification
We prove optimal sampling bounds achieving $(1\pm\varepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions …