NeuroCOLT workshop
on
Generalisation Bounds Less than 0.5
Windsor, 29 April - 2 May 2002
Cumberland Lodge

"Algorithmic Luckiness"

Ralf Herbrich and Bob Williamson

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.