Unitary Branching Programs: Learnability and Lower Bounds.
Fidel Ernesto Diaz AndinoMaria KokkouMateus de Oliveira OliveiraFarhad VadieePublished in: ICML (2021)
Keyphrases
- lower bound
- concept class
- upper bound
- vc dimension
- vapnik chervonenkis dimension
- branch and bound
- branch and bound algorithm
- finite automata
- concept classes
- pac learnability
- uniform convergence
- sample complexity
- worst case
- np hard
- dnf formulas
- optimal solution
- objective function
- learning algorithm
- equivalence queries
- learning theory
- boolean functions
- inductive inference
- pattern languages
- statistical queries
- pac learning
- upper and lower bounds
- concept learning
- lower and upper bounds
- exact learning
- inductive logic programming
- pac model
- optimal cost
- agnostic learning
- active learning