Journal
JOURNAL OF COMPLEXITY
Volume 68, Issue -, Pages -Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jco.2021.101600
Keywords
VC-dimension; Discrepancy Theory; Measure Theory; Machine Learning; Sample Compression; Points on the Torus
Funding
- Austrian Science Foundation FWF [P32337, F5505-N26, F5505- Y-901, F5502]
- Special Research Program Quasi Monte Carlo Methods: Theory and Applications [F5505-N26, F5502]
- Austrian Science Fund (FWF) [P32337] Funding Source: Austrian Science Fund (FWF)
Ask authors/readers for more resources
This paper demonstrates that the VC-dimension of the family of d-dimensional axis-parallel boxes and cubes on the d-dimensional torus is asymptotically d log(2) d, which is different from most other examples where the VC-dimension usually grows linearly with d in similar settings.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
