Online Learning with Global Cost Functions
Venue
22nd Annual Conference on Learning Theory, COLT, Omnipress (2009)
Publication Year
2009
Authors
Eyal Even-Dar, Robert Kleinberg, Shie Mannor, Yishay Mansour
BibTeX
Abstract
We consider an online learning setting where at each time step the decision maker
has to choose how to distribute the future loss between k alternatives, and then
observes the loss of each alternative. Motivated by load balancing and job
scheduling, we consider a global cost function (over the losses incurred by each
alternative), rather than a summation of the instantaneous losses as done
traditionally in online learning. Such global cost functions include the makespan
(the maximum over the alternatives) and the Ld norm (over the
alternatives). Based on approachability theory, we design an algorithm that
guarantees vanishing regret for this setting, where the regret is measured with
respect to the best static decision that selects the same distribution over
alternatives at every time step. For the special case of makespan cost we devise a
simple and efficient algorithm. In contrast, we show that for concave global cost
functions, such as Ld norms for d<1, the worst-case average regret
does not vanish.
