Algorithmic Luckiness

Over the last few decades a few frameworks to study the generalisation performance of learning algorithms have been emerged. Among the few, the most remarkable are the VC framework (empirical risk minimisation algorithms), compression framework (on-line algorithms and compression schemes) and the luckiness framework (structural risk minimisation algorithms). However, apart from the compression framework none of the frameworks has considered the generalisation error of the single hypothesis learned by a given learning algorithm but resorted to the more stringent requirement of uniform convergence. The algorithmic luckiness framework is an extension of the powerful luckiness framework which studies the generalisation error of particular learning algorithms relative to some prior knowledge about the target concept encoded via a luckiness function.

References

• Ralf Herbrich and Robert C. Williamson. Algorithmic Luckiness. 2002. Advances in Neural Information Processing Systems 14. (Gzipped PostScript)

• Ralf Herbrich and Robert C. Williamson. Algorithmic Luckiness. 2002. Journal of Machine Learning Research (Gziped Postscript)