Fast Cross-Validation for Incremental Learning

Fast Cross-Validation for Incremental Learning. Joulani, P., György, A., & Szepesvári, C. In IJCAI, pages 3597–3604, 04, 2015.

Paper abstract bibtex

Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze how the delay effects the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with much lower complexity.

@inproceedings{JoGySz15,
	abstract = {Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze how the delay effects the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with much lower complexity.},
	acceptrate = {575 out of 1996=28.6\%},
	author = {Joulani, P. and Gy{\"o}rgy, A. and Szepesv{\'a}ri, Cs.},
	booktitle = {IJCAI},
	keywords = {theory, big data, complexity analysis, computation, cross-validation, performance bounds},
	month = {04},
	pages = {3597--3604},
	title = {Fast Cross-Validation for Incremental Learning},
	url_paper = {tree-cv.pdf},
	year = {2015}}

Downloads: 0