Random Walk Approach to Regret Minimization

Part of Advances in Neural Information Processing Systems 23 (NIPS 2010)

Bibtex Metadata Paper


Hariharan Narayanan, Alexander Rakhlin


We propose a computationally efficient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efficient method for implementing mixture forecasting strategies.