Lower bounds for linear decision lists.

Arkadev Chattopadhyay Meena Mahajan Nikhil S. Mande Nitin Saurabh

Published in: Chic. J. Theor. Comput. Sci. (2020)

Keyphrases

decision lists
lower bound
concept classes
sample complexity
concept class
upper bound
vc dimension
decision trees
objective function
np hard
rule sets
pac learning
term dnf
low degree
lower and upper bounds
worst case
optimal solution
sample size
target function
training data