Generalization Bounds for Linear Learning Algorithms
We study generalization properties of linear learning algo rithms and develop a data dependent approach that is used to derive genera lization bounds that depend on the margin distribution. Our method ma kes use of random projection techniques to allow the use of existing VC dimension bounds in the effective, lower, dimension of the data. C omparisons with existing generalization bound show that our bounds are tighter and meaningful in cases existing bounds are not. Our methods is a l o shown to be useful as an analysis tool, alternative to learning cur ves.