Back to Search
Start Over
On the Generalization Ability of On-Line Learning Algorithms.
- Source :
- IEEE Transactions on Information Theory; Sep2004, Vol. 50 Issue 9, p2050-2057, 8p
- Publication Year :
- 2004
-
Abstract
- In this paper, it is shown how to extract a hypothesis with small risk from the ensemble of hypotheses generated by an arbitrary on-line learning algorithm run on an independent and identically distributed (i.i.d.) sample of data. Using a simple large deviation argument, we prove fight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M<subscript>n</subscript> associated with the on-line performance of the ensemble. Via sharp pointwise bounds on M<subscript>n</subscript>, we then obtain risk tail bounds for kernel Perceptron algorithms in terms of the spectrum of the empirical kernel matrix. These bounds reveal that the linear hypotheses found via our approach achieve optimal tradeoffs between hinge loss and margin size over the class of all linear functions, an issue that was left open by previous results. A distinctive feature of our approach is that the key tools for our analysis come from the model of prediction of individual sequences; i.e., a model making no probabilistic assumptions on the source generating the data. In fact, these tools turn out to be so powerful that we only need very elementary statistical facts to obtain our final risk bounds. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 50
- Issue :
- 9
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 14351071
- Full Text :
- https://doi.org/10.1109/TIT.2004.833339