Coin betting and parameter-free online learning

Francesco Orabona, Dávid Pál

Research output: Chapter in Book/Report/Conference proceedingConference contribution

98 Scopus citations

Abstract

In the recent years, a number of parameter-free algorithms have been developed for online linear optimization over Hilbert spaces and for learning with expert advice. These algorithms achieve optimal regret bounds that depend on the unknown competitors, without having to tune the learning rates with oracle choices. We present a new intuitive framework to design parameter-free algorithms for both online linear optimization over Hilbert spaces and for learning with expert advice, based on reductions to betting on outcomes of adversarial coins. We instantiate it using a betting algorithm based on the Krichevsky-Trofimov estimator. The resulting algorithms are simple, with no parameters to be tuned, and they improve or match previous results in terms of regret guarantee and per-round complexity.
Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems
PublisherNeural information processing systems foundation
Pages577-585
Number of pages9
StatePublished - Jan 1 2016
Externally publishedYes

Fingerprint

Dive into the research topics of 'Coin betting and parameter-free online learning'. Together they form a unique fingerprint.

Cite this