Online Optimization Specialization (3/4): Review of 'Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization'
Specialization Introduction This specialization covers five selected grounding papers in online optimization. In each blog, I will discuss one paper, where I aim to include Brief introduction and summary to the paper Key takeaways of the paper Notice that all the discussion and summary in this specialization are based on the reviewed papers. None of the algorithms or theorems is proposed by myself. Summary Paper Detail Title: Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization Author(s): Jacob Abernethy, Elad Hazan, Alexander Raklin URL: http://web.eecs.umich.edu/~jabernet/123-Abernethy.pdf Abstract We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal $O*(\sqrt{T})$ regret. The setting is a natural generalization of the stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of rece...