Multitask Learning with Expert Advice

Jacob Duncan Abernethy, Peter Bartlett and Alexander Rakhlin

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-20
January 28, 2007

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-20.pdf

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the "ideal" algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.


BibTeX citation:

@techreport{Abernethy:EECS-2007-20,
    Author = {Abernethy, Jacob Duncan and Bartlett, Peter and Rakhlin, Alexander},
    Title = {Multitask Learning with Expert Advice},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Jan},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-20.html},
    Number = {UCB/EECS-2007-20},
    Abstract = {We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the "ideal" algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.}
}

EndNote citation:

%0 Report
%A Abernethy, Jacob Duncan
%A Bartlett, Peter
%A Rakhlin, Alexander
%T Multitask Learning with Expert Advice
%I EECS Department, University of California, Berkeley
%D 2007
%8 January 28
%@ UCB/EECS-2007-20
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-20.html
%F Abernethy:EECS-2007-20