A Time-Space Lower Bound for a Large Class of Learning Problems.
Ran RazPublished in: Electron. Colloquium Comput. Complex. (2017)
Keyphrases
- learning problems
- lower bound
- sample complexity
- learning tasks
- reproducing kernel hilbert space
- machine learning algorithms
- supervised learning
- convex optimization problems
- kernel methods
- upper bound
- binary classification
- learning algorithm
- semi supervised learning
- reinforcement learning
- hypothesis space
- machine learning
- computational learning theory
- pac learning
- multi task learning
- multi task
- objective function
- optimal solution
- multiple kernel learning
- text categorization
- support vector
- pairwise
- statistical queries
- worst case
- class labels
- function classes