Inapproximability of VC Dimension and Littlestone’s Dimension

Pasin Manurangsi, Aviad Rubinstein
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1432-1460, 2017.

Abstract

We study the complexity of computing the VC Dimension and Littlestone’s Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x,C)$-th entry is $1$ iff element $x$ belongs to concept $C$), both can be computed exactly in quasi-polynomial time ($n^O(\log n)$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove nearly matching lower bounds on the running time, that hold even for \em approximation algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-manurangsi17a, title = {Inapproximability of VC Dimension and Littlestone’s Dimension}, author = {Manurangsi, Pasin and Rubinstein, Aviad}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1432--1460}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/manurangsi17a/manurangsi17a.pdf}, url = {https://proceedings.mlr.press/v65/manurangsi17a.html}, abstract = {We study the complexity of computing the VC Dimension and Littlestone’s Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x,C)$-th entry is $1$ iff element $x$ belongs to concept $C$), both can be computed exactly in quasi-polynomial time ($n^O(\log n)$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove nearly matching lower bounds on the running time, that hold even for \em approximation algorithms.} }
Endnote
%0 Conference Paper %T Inapproximability of VC Dimension and Littlestone’s Dimension %A Pasin Manurangsi %A Aviad Rubinstein %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-manurangsi17a %I PMLR %P 1432--1460 %U https://proceedings.mlr.press/v65/manurangsi17a.html %V 65 %X We study the complexity of computing the VC Dimension and Littlestone’s Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x,C)$-th entry is $1$ iff element $x$ belongs to concept $C$), both can be computed exactly in quasi-polynomial time ($n^O(\log n)$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove nearly matching lower bounds on the running time, that hold even for \em approximation algorithms.
APA
Manurangsi, P. & Rubinstein, A.. (2017). Inapproximability of VC Dimension and Littlestone’s Dimension. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1432-1460 Available from https://proceedings.mlr.press/v65/manurangsi17a.html.

Related Material