The Coin Problem in Constant Depth: Sample Complexity and Parity Gates.
Nutan LimayeKarteek SreenivasaiahSrikanth SrinivasanUtkarsh TripathiS. VenkiteshPublished in: CoRR (2018)
Keyphrases
- sample complexity
- theoretical analysis
- pac learning
- upper bound
- special case
- learning problems
- supervised learning
- vc dimension
- constant factor
- lower bound
- active learning
- generalization error
- learning algorithm
- training examples
- concept classes
- pac learnability
- sample size
- learning tasks
- decision lists
- linear threshold
- feature extraction
- irrelevant features
- data mining
- covering numbers