The Pareto regret frontier
Contribuinte(s) |
Burges, Christopher J.C. Bottou, Leon Welling, Max Ghahramani, Zoubin Weinberger, Kilian Q. |
---|---|
Data(s) |
2013
|
Resumo |
Performance guarantees for online learning algorithms typically take the form of regret bounds, which express that the cumulative loss overhead compared to the best expert in hindsight is small. In the common case of large but structured expert sets we typically wish to keep the regret especially small compared to simple experts, at the cost of modest additional overhead compared to more complex others. We study which such regret trade-offs can be achieved, and how. We analyse regret w.r.t. each individual expert as a multi-objective criterion in the simple but fundamental case of absolute loss. We characterise the achievable and Pareto optimal trade-offs, and the corresponding optimal strategies for each sample size both exactly for each finite horizon and asymptotically. |
Formato |
application/pdf |
Identificador | |
Relação |
http://eprints.qut.edu.au/73148/1/5150-the-pareto-regret-frontier.pdf http://papers.nips.cc/paper/5150-the-pareto-regret-frontier Koolen, Wouter M. (2013) The Pareto regret frontier. In Burges, Christopher J.C., Bottou, Leon, Welling, Max, Ghahramani, Zoubin, & Weinberger, Kilian Q. (Eds.) Advances in Neural Information Processing Systems (NIPS) 26, 5 - 10 December 2013, Lake Tahoe, Nevada, USA. |
Direitos |
Copyright 2013 Please consult the author |
Fonte |
Science & Engineering Faculty; Mathematical Sciences |
Tipo |
Conference Paper |