The Pareto Regret Frontier
Wouter M. Koolen (QUT)
NICTA SML SEMINARDATE: 2013-11-12
TIME: 12:00:00 - 13:00:00
LOCATION: NICTA - 7 London Circuit
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
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.
BIO:
Wouter M. Koolen is a machine learning researcher fascinated by the theoretical foundations of sequential prediction and decision making. Wouter obtained his PhD at CWI with Paul Vitanyi and Peter GrAnwald, worked at Royal Holloway with Voldoya Vovk, at CWI with Peter GrAnwald and is now at the Queensland University of Technology with Peter Bartlett.
