Published in AISTATS, 2019
This paper gives a trade-off between the number of updates and the regret in an online algorithm in a general setting.
Mohammad Reza Karimi Jaghargh, Andreas Krause, Silvio Lattanzi, Sergei Vassilvtiskii (2019). "Consistent Online Optimization: Convex and Submodular" AISTATS. (pp. 2241--2250). [pdf]