Weaknesses: (W1) - The contributions of the paper are very close from the one of [12]. Indeed, it takes ideas from [12] to restrict the analysis on a simplex that we can control. Moreover, it doesn't clearly put forward the novelty of the bound on dynamic regret compared to the one of [18]. For instance, the following sentence serves to define a key quantity in the authors development: ''For each i [N ], denote by hti the last observed gradient of fi at time t, with h1i initialized arbitrarily'' Unfortunately, it is quite unclear as two readers might understand something different. In the same line of comments, the proof of Lemma 3 is very confusing.

Reducing the variance of the gradient estimator is known to improve the convergence rate of stochastic gradient-based optimization and sampling algorithms. One way of achieving variance reduction is to design importance sampling strategies. Recently, the problem of designing such schemes was formulated as an online learning problem with bandit feedback, and algorithms with sub-linear static regret were designed. In this work, we build on this framework and propose a simple and efficient algorithm for adaptive importance sampling for finite-sum optimization and sampling with decreasing step-sizes. Under standard technical conditions, we show that our proposed algorithm achieves O(T {2/3}) and O(T {5/6}) dynamic regret for SGD and SGLD respectively when run with O(1/t) step sizes.