The VC-dimension of axis-parallel boxes on the Torus

被引：1

作者：

Gillibert, P. ^{[1
]}

Lachmann, T. ^{[2
]}

Muellner, C. ^{[1
]}

机构：

[1] TU Wien, Inst Diskrete Math & Geometrie, Wiedner Hauptstr 8-10, A-1040 Vienna, Austria

[2] JKU Linz, Inst Finanzmath & Angew Zahlentheorie, A-4040 Linz, Austria

来源：

JOURNAL OF COMPLEXITY | 2022年 / 68卷

基金：

奥地利科学基金会;

关键词：

VC-dimension; Discrepancy Theory; Measure Theory; Machine Learning; Sample Compression; Points on the Torus; DISCREPANCY;

D O I：

10.1016/j.jco.2021.101600

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show in this paper that the VC-dimension of the family of d-dimensional axis-parallel boxes and cubes on the d-dimensional torus are both asymptotically d log(2) d. This is especially surprising as in most other examples the VC-dimension usually grows linearly with d in similar settings. (C) 2021 Elsevier Inc. All rights reserved.

引用

页数：14

共 18 条

[1]

[Anonymous], 1996, PROBABILISTIC THEORY

[2]

Despres C.J.J., VAPNIK CHERVONENKIS

[3]

Doliwa T, 2014, J MACH LEARN RES, V15, P3107

[4]

Dudley RM, 2014, CAM ST AD M, V142, P1

[5]

DUDLEY RM, 1984, LECT NOTES MATH, V1097, P1, DOI DOI 10.1007/BFB0099432

[6] The inverse of the star-discrepancy depends linearly on the dimension [J].

Heinrich, S ;

Novak, E ;

Wasilkowski, GW ;

Wozniakowski, H .

ACTA ARITHMETICA, 2001, 96 (03) :279-302

[7]

Hinrichs A, 2004, J COMPLEXITY, V20, P477, DOI [10.1016/j.jco.2004.01.001, 10.1016/j Jco.2004.01.001]

[8] DISCREPANCY AND APPROXIMATIONS FOR BOUNDED VC-DIMENSION [J].

MATOUSEK, J ;

WELZL, E ;

WERNISCH, L .

COMBINATORICA, 1993, 13 (04) :455-466

[9]

Matousek J, 1999, GEOMETRIC DISCREPANC, V18

[10]

Mohri M., 2018, Foundations of machine learning

← 1 2 →