Tight Lower Bounds on the VC-dimension of Geometric Set Systems

被引：0

作者：

Csikos, Monika ^{[1
]}

Mustafa, Nabil H. ^{[1
]}

Kupayskii, Audrey ^{[2
,3
]}

机构：

[1] Univ Paris Est, LIGM, Equipe A3SI, ESIEE Paris, Cite Descartes 2 Blvd Blaise Pascal, F-93162 Noisy Le Grand, France

[2] Moscow Inst Phys & Technol, Lab Adv Combinator & Networks Applicat, 9 Inst Skiy, Dolgoprudnyi 41701, Russia

[3] Univ Oxford, Math Inst, Woodstock Rd, Oxford OX2 6GG, England

来源：

JOURNAL OF MACHINE LEARNING RESEARCH | 2019年 / 20卷

基金：

英国工程与自然科学研究理事会;

关键词：

VC-dimension; union of concepts; intersection of concepts; combinatorial problems; PAC learning;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 foundational paper of Blumer et al. (1989) as well as by Eisenstat and Angluin (2007) and Johnson (2008).

引用

页数：8

共 16 条

[1]

Bachem O., 2018, THESIS

[2]

Balcan M.-F., 2013, P NEUR INF PROC SYST

[3] LEARNABILITY AND THE VAPNIK-CHERVONENKIS DIMENSION [J].

BLUMER, A ;

EHRENFEUCHT, A ;

HAUSSLER, D ;

WARMUTH, MK .

JOURNAL OF THE ACM, 1989, 36 (04) :929-965

[4] A DETERMINISTIC VIEW OF RANDOM SAMPLING AND ITS USE IN GEOMETRY [J].

CHAZELLE, B ;

FRIEDMAN, J .

COMBINATORICA, 1990, 10 (03) :229-249

[5]

Dobkin D. P., 1995, Proceedings of the Eighth Annual Conference on Computational Learning Theory, P329, DOI 10.1145/225298.225338

[6] The VC dimension of k-fold union [J].

Eisenstat, David ;

Angluin, Dana .

INFORMATION PROCESSING LETTERS, 2007, 101 (05) :181-184

[7]

Ezra E., 2017, ARXIV E PRINTS

[8]

Johnson H., 2008, THESIS

[9]

Kupavskii A., 2016, P S COMP GEOM SOCG

[10]

Lucic M., 2016, P ART INT STAT AISTA

← 1 2 →