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