## The Computational Complexity of Machine LearningThe Computational Complexity of Machine Learning is a mathematical study of the possibilities for efficient learning by computers. It works within recently introduced models for machine inference that are based on the theory of computational complexity and that place an explicit emphasis on efficient and general algorithms for learning. Theorems are presented that help elucidate the boundary of what is efficiently learnable from examples. These results take the form of both algorithms with proofs of their performance, and hardness results demonstrating the intractability of learning in certain natural settings. In addition the book contains lower bounds on the resources required for learning, an extensive study of learning in the presence of errors in the sample data, and several theorems demonstrating reducibilities between learning problems. Michael J. Kearns is Postdoctoral Associate in the Laboratory for Computer Science at MIT. Contents: Definitions, Notations, and Motivation. Overview of Recent Research in Computational Learning Theory. Useful Tools for Distribution-Free Learning. Learning in the Presence of Errors. Lower Bounds on Sample Complexity. Cryptographic Limitations on Polynomial-Time Learning. Distribution-Specific Learning in Polynomial Time. Equivalence of Weak Learning and Group Learning. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Recent Research in Computational Learning Theory | 22 |

Tools for Distributionfree Learning | 33 |

Learning in the Presence of Errors | 45 |

Lower Bounds on Sample Complexity | 85 |

Cryptographic Limitations on Polynomialtime Learning | 101 |

Distributionspecific Learning in Polynomial Time | 129 |

Equivalence of Weak Learning and Group Learning | 140 |

Conclusions and Open Problems | 145 |

### Common terms and phrases

accuracy allow appear apply approximation assume assumptions Blum Boolean Chapter choose circuits classification coloring combinatorial optimization computational concept consider consistent constant Corollary cost cover define definitions denote depend describe determine distribution-free model draw drawn equivalent expect Fact factor finding finite fixed follows formulae functions give given hardness results high probability holds hypothesis input instance interesting kDNF known learning algorithm learning problem least length lower bound machine malicious error rate monomial monotone natural negative examples Note NP-hard obtain optimal oracle output parameterized pc(I Pitt polynomial-time polynomial-time algorithm polynomially learnable positive examples possible problem Proof prove random reducibility representation class respectively restricted sample sample complexity satisfying significant simply simulation Step target distributions target representation Theorem theory tolerated trapdoor uniform Valiant variables

### Popular passages

Page 151 - IEEE Symp. on Foundations of Computer Science, 1988, pp. 100-109. [20] S. Judd. Learning in neural networks. Proc. of the 1988 Workshop on Computational Learning Theory, Morgan Kaufmann Publishers, 1988, pp 2-8. [21] M. Kearns, M. Li, L. Pitt, LG Valiant. On the learnability of Boolean formulae.

Page 151 - M. Kearns and L. Pitt. A polynomial-time algorithm for learning fc-variable pattern languages from examples.