On the Minimal Degree Bias in Generalization on the Unseen for non-Boolean Functions.

Denys Pushkin Raphaël Berthier Emmanuel Abbe

Published in: CoRR (2024)

Keyphrases

boolean functions
prime implicants
uniform distribution
threshold functions
membership queries
relevant variables
multi valued
read once formulas
binary decision diagrams
relational databases
polynomial size
functional properties
efficient learning
training set
dnf formulae
pac learning
pseudo boolean functions