Name
Abstract | ||
|---|---|---|
This paper provides evidence that there is no polynomial-time optimal mistake bound learning algorithm. This conclusion is reached via several reductions as follows. Littlestone (1988, Math. Learning 2 , 285–318) has introduced a combinatorial function K from classes to integers and has shown that if a subroutine computing K is given, one can construct a polynomial-time optimal MB learning algorithm. We establish the reverse reduction. That is, given an optimal MB learning algorithm as a subroutine, one can compute K in polynomial time. Our result combines with Littlestone's to establish that the two tasks above have the same time complexity up to a polynomial. Next, we show that the VC-dimension decision problem is polynomially reducible to the K -decision problem. Papadimitriou and Yannakakis [PY93] have provided a strong evidence that the VC-dimension decision problem is not in P. Therefore, it is very unlikely that there is a polynomial-time optimal mistake bound learning algorithm |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1006/inco.1998.2709 | Inf. Comput. |
Keywords | Field | DocType |
optimal mistake,vc dimension,decision problem,polynomial time,time complexity | Integer,Discrete mathematics,Decision problem,Combinatorics,Polynomial,Mistake,Algorithm complexity,Subroutine,Time complexity,Mathematics,Polynomial-time reduction | Journal |
Volume | Issue | ISSN |
144 | 1 | Information and Computation |
Citations | PageRank | References |
4 | 0.60 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moti Frances | 1 | 84 | 5.20 |
| Ami Litman | 2 | 240 | 49.78 |