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 Followthe- 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.
Original language | English (US) |
---|---|
Journal | Journal of Machine Learning Research |
Volume | 40 |
Issue number | 2015 |
State | Published - 2015 |
Event | 28th Conference on Learning Theory, COLT 2015 - Paris, France Duration: Jul 2 2015 → Jul 6 2015 |
Keywords
- Experts
- Non-additive losses
- On-line learning
- Structured prediction
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Statistics and Probability
- Artificial Intelligence