Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions
Long, Philip M., Servedio, Rocco
–Neural Information Processing Systems
We consider the well-studied problem of learning decision lists using few examples whenmany irrelevant features are present. We show that smooth boosting algorithms suchas MadaBoost can efficiently learn decision lists of length k over n boolean variables using poly(k, log n) many examples provided that the marginal distribution over the relevant variables is "not too concentrated" in an L
Neural Information Processing Systems
Dec-31-2007