Random Walk Approach to Regret Minimization
Abstract
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.
Cite
Text
Narayanan and Rakhlin. "Random Walk Approach to Regret Minimization." Neural Information Processing Systems, 2010.Markdown
[Narayanan and Rakhlin. "Random Walk Approach to Regret Minimization." Neural Information Processing Systems, 2010.](https://mlanthology.org/neurips/2010/narayanan2010neurips-random/)BibTeX
@inproceedings{narayanan2010neurips-random,
title = {{Random Walk Approach to Regret Minimization}},
author = {Narayanan, Hariharan and Rakhlin, Alexander},
booktitle = {Neural Information Processing Systems},
year = {2010},
pages = {1777-1785},
url = {https://mlanthology.org/neurips/2010/narayanan2010neurips-random/}
}