<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

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

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Feb 2022Embargo end date: 01 Jan 2020Publisher:Elsevier BVJournal:Journal of Complexity, volume 68, page 101,600 (issn: 0885-064X,

Authors: Pierre Gillibert; Clemens Müllner; Thomas Lachmann;

doi: 10.1016/j.jco.2021.101600 , 10.48550/arxiv.2004.13861

arXiv: http://arxiv.org/abs/2004.13861

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

- Summary
- Subjects
- Metrics

Abstract

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 the VC-dimension usually grows linearly with $d$ in similar settings.

Related Organizations

TU Wien
Austria

Keywords

FOS: Computer and information sciences, Computer Science - Machine Learning, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics, Machine Learning (cs.LG)

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Found an issue? Give us feedback

Average

Green

bronze

Fields of Science

Fields of Science