[J21] - A continuous-time approach to online optimization

J. Kwon and P. Mertikopoulos. Journal of Dynamics and Games, vol. 4, no. 2, pp. 125-148, April 2017.


We consider a family of learning strategies for online optimization problems that evolve in continuous time and we show that they lead to no regret. From a more traditional, discrete-time viewpoint, this continuous-time approach allows us to derive the no-regret properties of a large class of discrete-time algorithms including as special cases the exponential weights algorithm, online mirror descent, smooth fictitious play and vanishingly smooth fictitious play. In so doing, we obtain a unified view of many classical regret bounds, and we show that they can be decomposed into a term stemming from continuous-time considerations and a term which measures the disparity between discrete and continuous time. As a result, we obtain a general class of infinite horizon learning strategies that guarantee an $O(T^{−1/2})$ regret bound without having to resort to a doubling trick.

arXiv link: https://arxiv.org/abs/1401.6956

Nifty tech tag lists from Wouter Beeftink