On-Line Learning Algorithms for Path Experts with Non-Additive Losses
Abstract
We consider two broad families of non-additive loss functions covering a large number of applications: rational losses and tropical losses. We give new algorithms extending the Follow-the-Perturbed-Leader (FPL) algorithm to both of these families of loss functions and similarly give new algorithms extending the Randomized Weighted Majority (RWM) algorithm to both of these families. We prove that the time complexity of our extensions to rational losses of both FPL and RWM is polynomial and present regret bounds for both. We further show that these algorithms can play a critical role in improving performance in applications such as structured prediction.
Cite
Text
Cortes et al. "On-Line Learning Algorithms for Path Experts with Non-Additive Losses." Annual Conference on Computational Learning Theory, 2015.Markdown
[Cortes et al. "On-Line Learning Algorithms for Path Experts with Non-Additive Losses." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/cortes2015colt-line/)BibTeX
@inproceedings{cortes2015colt-line,
title = {{On-Line Learning Algorithms for Path Experts with Non-Additive Losses}},
author = {Cortes, Corinna and Kuznetsov, Vitaly and Mohri, Mehryar and Warmuth, Manfred K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {424-447},
url = {https://mlanthology.org/colt/2015/cortes2015colt-line/}
}