License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.34
URN: urn:nbn:de:0030-drops-188594
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18859/
Go to the corresponding LIPIcs Volume Portal

Bshouty, Nader H.

Superpolynomial Lower Bounds for Learning Monotone Classes

pdf-format:
LIPIcs-APPROX34.pdf (0.8 MB)

Abstract

Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time n^Õ(log log s) for the classes of n-variable size-s DNF, size-s Decision Tree, and log s-Junta by DNF (that returns a DNF hypothesis). Assuming a natural conjecture on the hardness of set cover, they give the lower bound n^Ω(log s). This matches the best known upper bound for n-variable size-s Decision Tree, and log s-Junta.
In this paper, we give the same lower bounds for PAC-learning of n-variable size-s Monotone DNF, size-s Monotone Decision Tree, and Monotone log s-Junta by DNF. This solves the open problem proposed by Koch, Strassle, and Tan and subsumes the above results.
The lower bound holds, even if the learner knows the distribution, can draw a sample according to the distribution in polynomial time, and can compute the target function on all the points of the support of the distribution in polynomial time.

BibTeX - Entry

@InProceedings{bshouty:LIPIcs.APPROX/RANDOM.2023.34,
  author =	{Bshouty, Nader H.},
  title =	{{Superpolynomial Lower Bounds for Learning Monotone Classes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18859},
  URN =		{urn:nbn:de:0030-drops-188594},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.34},
  annote =	{Keywords: PAC Learning, Monotone DNF, Monotone Decision Tree, Monotone Junta, Lower Bound}
}

Keywords: PAC Learning, Monotone DNF, Monotone Decision Tree, Monotone Junta, Lower Bound
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI