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