Loading...
Please wait, while we are loading the content...
Similar Documents
Computational sample complexity and attribute-efficient learning (2000).
| Content Provider | CiteSeerX |
|---|---|
| Author | Servedio, Rocco A. |
| Abstract | Two fundamental measures of the efficiency of a learning algorithm are its running time and the number of examples it requires (its sample complexity). In this paper we demonstrate that even for simple concept classes, an inherent tradeoff can exist between running time and sample complexity. We present a concept class of 1-decision lists and prove that while a computationally unbounded learner can learn the class from O(1) examples, under a standard cryptographic assumption any polynomial-time learner requires almost \Theta(n) examples. Using a different construction, we present a concept class of k-decision lists which exhibits a similar but stronger gap in sample complexity. These results strengthen the results of Decatur, Goldreich and Ron [9] on distribution-free computational sample complexity and come within a logarithmic factor of the largest possible gap for concept classes of k-decision lists. Finally, we construct a concept class of decision lists which can be lear... |
| File Format | |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Concept Class Sample Complexity Attribute-efficient Learning Computational Sample Complexity K-decision List Possible Gap Inherent Tradeoff Different Construction Decision List Learning Algorithm Simple Concept Class Polynomial-time Learner Fundamental Measure 1-decision List Logarithmic Factor Unbounded Learner Distribution-free Computational Sample Complexity Standard Cryptographic Assumption Running Time |
| Content Type | Text |
| Resource Type | Article |
