An Almost Optimal PAC Algorithm

author: Hans U. Simon, Fakultät für Mathematik, Ruhr University Bochum
published: Aug. 20, 2015,   recorded: July 2015,   views: 110


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


The best currently known general lower and upper bounds on the number of labeled examples needed for learning a concept class in the PAC framework (the realizable case) do not perfectly match: they leave a gap of order $\log(1/\eps)$ (resp.a gap which is logarithmic in another one of the relevant parameters). It is an unresolved question whether there exists an ``optimal PAC algorithm'' which establishes a general upper bound with precisely the same order of magnitude as the general lower bound. According to a result of Auer and Ortner, there is no way for showing that arbitrary consistent algorithms are optimal because they can provably differ from optimality by factor $\log(1/\eps)$. In contrast to this result, we show that every consistent algorithm $L$ (even a provably suboptimal one) induces a family $(L_K)_{K\ge1}$ of PAC algorithms (with $2K-1$ calls of $L$ as a subroutine) which come very close to optimality: the number of labeled examples needed by $L_K$ exceeds the general lower bound only by factor $\ell_K(1/\eps)$ where $\ell_K$ denotes (a truncated version of) the $K$-times iterated logarithm. Moreover, $L_K$ is applicable to any concept class $C$ of finite VC-dimension and it can be implemented efficiently whenever the consistency problem for $C$ is feasible. We show furthermore that, for every consistent algorithm $L$, $L_2$ is an optimal PAC algorithm for precisely the same concept classes which were used by Auer and Ortner for showing the existence of suboptimal consistent algorithms. This can be seen as an indication that $L_K$ may have an even better performance than it is suggested by our worstcase analysis.

See Also:

Download slides icon Download slides: colt2015_simon_pac_algorithm_01.pdf (195.3 KB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: