Bandit Convex Optimization: sqrt{T} Regret in One Dimension.
Sébastien BubeckOfer DekelTomer KorenYuval PeresPublished in: CoRR (2015)
Keyphrases
- convex optimization
- regret bounds
- lower bound
- weighted majority
- bandit problems
- online convex optimization
- upper confidence bound
- worst case
- online learning
- multi armed bandit
- interior point methods
- linear regression
- multi armed bandit problems
- online algorithms
- primal dual
- convex optimization problems
- upper bound
- low rank
- total variation
- semidefinite program
- convex relaxation
- norm minimization
- bregman divergences
- convex sets
- alternating direction method of multipliers
- least squares