Stability of Error Bounds in Statistical Learning Theory

The proposal considers a wide class of error bounds developed in the context of statistical learning theory which are expressed in terms of functionals of the target function, for instance its norm in a reproducing kernel Hilbert space or other functional space. These bounds are unstable in the sense that a small perturbation of the target function can induce an arbitrary large increase ofthe relevant functional and make the error bound useless. A recent result shows how to recover stability for two important classes of problems using a suitable version of Fano’s inequality. The first class includes problems in which the output samples are binary, the second class includes general linear regularization filters. The purpose of the project is to develop mathematical techniques which would allow to recover stability for much more general learning algorithms using information theoretical results, and apply these results to various error bounds available in the literature. On the computational side, the purpose of the project is to develop algorithms which can effectively estimate the "stabilized" complexity functionals from empirical samples, and to implement these algorithms on synthetic and real datasets.