2023/01/20 by Nader H. Bshouty, Bshouty, Nader H.
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning and Algorithms #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2301.08486
openalex publication_date 2023/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(loglog 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.