Sample Complexity for Winner Prediction in Elections.
Arnab BhattacharyyaPalash DeyPublished in: Electron. Colloquium Comput. Complex. (2015)
Keyphrases
- sample complexity
- theoretical analysis
- general loss functions
- upper bound
- learning problems
- pac learning
- social choice
- active learning
- generalization error
- learning algorithm
- supervised learning
- special case
- training examples
- vc dimension
- lower bound
- concept classes
- sample size
- covering numbers
- uniform convergence
- linear threshold
- pac learnability
- irrelevant features
- data sets
- optimal solution