Stochastic Streams: Sample Complexity vs. Space Complexity.
Michael S. CrouchAndrew McGregorGregory ValiantDavid P. WoodruffPublished in: ESA (2016)
Keyphrases
- space complexity
- sample complexity
- theoretical analysis
- learning problems
- pac learning
- upper bound
- learning algorithm
- generalization error
- worst case
- active learning
- vc dimension
- lower bound
- special case
- supervised learning
- arc consistency
- data streams
- concept classes
- training examples
- sample size
- space requirements
- worst case time complexity
- number of irrelevant features
- machine learning algorithms
- irrelevant features
- semi supervised learning
- data structure
- data sets