Parameter-Free Convex Learning through Coin Betting

Francesco Orabona, Dávid Pál
Proceedings of the Workshop on Automatic Machine Learning, PMLR 64:75-82, 2016.

Abstract

We present a new parameter-free algorithm for online linear optimization over any Hilbert space. It is theoretically optimal, with regret guarantees as good as with the best possible learning rate. The algorithm is simple and easy to implement. The analysis is given via the adversarial coin-betting game, Kelly betting and the Krichevsky-Trofimov estimator. Applications to obtain parameter-free convex optimization and machine learning algorithms are shown.

Cite this Paper

BibTeX
@InProceedings{pmlr-v64-orabona_parameter_2016, title = {Parameter-Free Convex Learning through Coin Betting}, author = {Orabona, Francesco and Pál, Dávid}, booktitle = {Proceedings of the Workshop on Automatic Machine Learning}, pages = {75--82}, year = {2016}, editor = {Hutter, Frank and Kotthoff, Lars and Vanschoren, Joaquin}, volume = {64}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v64/orabona_parameter_2016.pdf}, url = {https://proceedings.mlr.press/v64/orabona_parameter_2016.html}, abstract = {We present a new parameter-free algorithm for online linear optimization over any Hilbert space. It is theoretically optimal, with regret guarantees as good as with the best possible learning rate. The algorithm is simple and easy to implement. The analysis is given via the adversarial coin-betting game, Kelly betting and the Krichevsky-Trofimov estimator. Applications to obtain parameter-free convex optimization and machine learning algorithms are shown.} }
Endnote
%0 Conference Paper %T Parameter-Free Convex Learning through Coin Betting %A Francesco Orabona %A Dávid Pál %B Proceedings of the Workshop on Automatic Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Frank Hutter %E Lars Kotthoff %E Joaquin Vanschoren %F pmlr-v64-orabona_parameter_2016 %I PMLR %P 75--82 %U https://proceedings.mlr.press/v64/orabona_parameter_2016.html %V 64 %X We present a new parameter-free algorithm for online linear optimization over any Hilbert space. It is theoretically optimal, with regret guarantees as good as with the best possible learning rate. The algorithm is simple and easy to implement. The analysis is given via the adversarial coin-betting game, Kelly betting and the Krichevsky-Trofimov estimator. Applications to obtain parameter-free convex optimization and machine learning algorithms are shown.
RIS
TY - CPAPER TI - Parameter-Free Convex Learning through Coin Betting AU - Francesco Orabona AU - Dávid Pál BT - Proceedings of the Workshop on Automatic Machine Learning DA - 2016/12/04 ED - Frank Hutter ED - Lars Kotthoff ED - Joaquin Vanschoren ID - pmlr-v64-orabona_parameter_2016 PB - PMLR DP - Proceedings of Machine Learning Research VL - 64 SP - 75 EP - 82 L1 - http://proceedings.mlr.press/v64/orabona_parameter_2016.pdf UR - https://proceedings.mlr.press/v64/orabona_parameter_2016.html AB - We present a new parameter-free algorithm for online linear optimization over any Hilbert space. It is theoretically optimal, with regret guarantees as good as with the best possible learning rate. The algorithm is simple and easy to implement. The analysis is given via the adversarial coin-betting game, Kelly betting and the Krichevsky-Trofimov estimator. Applications to obtain parameter-free convex optimization and machine learning algorithms are shown. ER -
APA
Orabona, F. & Pál, D.. (2016). Parameter-Free Convex Learning through Coin Betting. Proceedings of the Workshop on Automatic Machine Learning, in Proceedings of Machine Learning Research 64:75-82 Available from https://proceedings.mlr.press/v64/orabona_parameter_2016.html.

Related Material