Inapproximability of VC Dimension and Littlestone’s Dimension

Pasin Manurangsi; Aviad Rubinstein

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

Download PDF