A complexity theoretic approach to learning
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2002.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/8395 |
| _version_ | 1811098443297325056 |
|---|---|
| author | Klivans, Adam R |
| author2 | Daniel A. Spielman. |
| author_facet | Daniel A. Spielman. Klivans, Adam R |
| author_sort | Klivans, Adam R |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2002. |
| first_indexed | 2024-09-23T17:14:58Z |
| format | Thesis |
| id | mit-1721.1/8395 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T17:14:58Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/83952019-04-11T04:41:53Z A complexity theoretic approach to learning Klivans, Adam R Daniel A. Spielman. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2002. Includes bibliographical references (leaves 127-138). This thesis details a new vantage point for attacking longstanding problems in machine learning. We use tools from computational complexity theory to make progress on problems from computational learning theory. Our methods yield the fastest and most expressive algorithms to date for learning several fundamental concept classes: * We show that any s-term DNF over n variables can be computed by a polynomial threshold function of order O(n1/3 log s). As an immediate consequence we obtain the fastest known DNF learning algorithm which runs in time 2O(n1/3). * We give the first polynomial time algorithm to learn an intersection of a constant number of halfspaces under the uniform distribution to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any function of a constant number of halfspaces with polynomial bounded weights under any distribution. * We give an algorithm to learn constant-depth polynomial-size circuits augmented with majority gates under the uniform distribution using random examples only. For circuits which contain a polylogarithmic number of majority gates the algorithm runs in quasipolynomial time. Under a suitable cryptographic assumption we show that these are the most expressive circuits which will admit a non-trivial learning algorithm. Our approach relies heavily on giving novel representations of well known concept classes via complexity theoretic reductions. We exploit the fact that many results in computational learning theory have a complexity theoretic analogue or implication. As such, (cont.) we also obtain new results in computational complexity including (1) a proof that the 30 year old lower bound due to Minsky and Papert [88] on the degree of a perceptron computing a DNF formula is tight and (2) improved constructions of pseudo-random generators, mathematical objects which play a fundamental role in cryptography and derandomization. by Adam Richard Klivans. Ph.D. 2005-08-23T19:50:53Z 2005-08-23T19:50:53Z 2002 2002 Thesis http://hdl.handle.net/1721.1/8395 50594564 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 138 leaves 9348960 bytes 9348716 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Klivans, Adam R A complexity theoretic approach to learning |
| title | A complexity theoretic approach to learning |
| title_full | A complexity theoretic approach to learning |
| title_fullStr | A complexity theoretic approach to learning |
| title_full_unstemmed | A complexity theoretic approach to learning |
| title_short | A complexity theoretic approach to learning |
| title_sort | complexity theoretic approach to learning |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/8395 |
| work_keys_str_mv | AT klivansadamr acomplexitytheoreticapproachtolearning AT klivansadamr complexitytheoreticapproachtolearning |