Near-tight closure bounds for Littlestone and threshold dimensions.
Badih GhaziNoah GolowichRavi KumarPasin ManurangsiPublished in: CoRR (2020)
Keyphrases
- upper bound
- lower bound
- mistake bound
- worst case
- concept classes
- linear threshold
- sample complexity
- generalization error bounds
- upper and lower bounds
- lower and upper bounds
- perceptron algorithm
- error bounds
- vc dimension
- alternative formulations
- threshold selection
- noise tolerant
- pac learning
- decision lists
- noise tolerance
- winnow algorithm
- sample size
- training set