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 条

[11] Sample Compression Schemes for VC Classes [J].

Moran, Shay ;

Yehudayoff, Amir .

JOURNAL OF THE ACM, 2016, 63 (03)

[12]

Moran Shay, 2017, A Journey Through Discrete Mathematics: A Tribute to Jir.i Matousek, P633

[13]

Rudolf D., 2018, Contemporary Computational Mathematics-A Celebration of the 80th Birthday of Ian Sloan, P1099

[14]

Shalev-Shwartz S., 2014, UNDERSTANDING MACHIN, P137, DOI DOI 10.1017/CBO9781107298019

[15]

van der Vaart A. W., 1996, Weak Convergence and Empirical Processes

[16]

van der Vaart Aad, 2009, Inst Math Stat Collect, V5, P103

[17]

Vapnik V., 1998, Statistical Learning Theory

[18] UNIFORM CONVERGENCE OF RELATIVE FREQUENCIES OF EVENTS TO THEIR PROBABILITIES [J].

VAPNIK, VN ;

CHERVONENKIS, AY .

THEORY OF PROBILITY AND ITS APPLICATIONS,USSR, 1971, 16 (02) :264-+

← 1 2 →