Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity.

Stephen Gross Elliot Anshelevich Lirong Xia

Published in: AAAI (2017)

Keyphrases

sample complexity
theoretical analysis
lower bound
active learning
pac learning
supervised learning
vc dimension
special case
upper bound
learning problems
generalization error
small number
concept classes
pac learnability
training examples
learning algorithm
sample complexity bounds
sample size
learning experience