Recently, I got chance to go through the following excellent paper appeared in COLT 2012 entitled Unified Algorithms for Online Learning and Competitive Analysis. When you read literature on online learning and try to make a connection to online algorithm, you may end up with some vague thought without any serious relation (at least this happened to me when I was reading chapter 5 of the book Prediction, Learning, and Games). Although Avrim Blum et. al did an excellent work on relating learning from expert advice to metrical task problem (MST), but the current paper is really can be considered as a breakthrough in relating two inherently different problems with similar structure. Another nice thing about this paper is that it is done by a combination of researchers from two fields, i.e., online learning and competitive analysis. I really liked the paper and it was one of the papers I was looking forward in the last two years to see:-)
No comments:
Post a Comment