Data Dependent Concentration Bounds for Sequential Prediction Algorithms

Tong Zhang

Abstract

We investigate the generalization behavior of sequential prediction (online) algorithms, when data are generated from a probability distribution. Using some newly developed probability inequalities, we are able to bound the total generalization performance of a learning algorithm in terms of its observed total loss. Consequences of this analysis will be illustrated with examples.
BibTeX
@inproceedings{zhang2005data,
  author = {Tong Zhang},
  title = {{Data Dependent Concentration Bounds for Sequential Prediction Algorithms}},
  booktitle = {Conference on Learning Theory},
  year = {2005},
  doi = {10.1007/11503415\_12},
}

Loading related content...

Figure