Summary
The authors study first order stochastic algorithms under a Markovian noise: the noise is no longer i.i.d. as for vanilla SGD, but follows a Markov chain, of finite mixing time $\tau$. The proposed algorithms are SGD-like algorithms, with batchsizes that can vary. In particular, they use a randomized batchsize strategy, whose aim is to trade-off between the noise variance of the stochastic gradients, and their bias (due to non-iid sampling). Batches are typically taken equal to the mixing time of the Markov chain.
An accelerated SGD algorithm is first introduced, and is proved to converge in the smooth strongly convex regime, with a rate that depends on the mixing time, a maximal gradient noise (max in terms of Markov chain state space and variables), condition number and strong convexity parameter. Various provided lower bounds show that this rate, although not optimal, has an optimal noise dependency.
The SGD algorithm is then studied in the smooth non-convex setting, to obtain typical rates for this algorithm under this type of noise assumption.
Finally, the authors study variational inequalities under Markovian noise, by introducing Randomized Extra Gradient (with also their batchsize strategy).
Strengths
Overall, the paper is well written, and very easy to follow, on a very interesting topic (stochastic approximation/optimization, under Markovian noise), that has re-gained attention lately.
In this line of work, the proposed algorithm and analysis of accelerated SGD is novel, this is the first accelerated rate for SGD under Markov chain noise. The batch size technique is also nice, and well explained. Together, these two techniques give a nice algorithm with a near-optimal rate, as shown by the lower bounds, that are more general than previous ones in this setting.
Although I am not very familiar of variational inequalities, the topic of VA with MC noise seems to be not very well studied in the literature, and provide the first bound with complexity proportional to the mixing time.
Weaknesses
There are two major concerns. Questions related to these are below in the dedicated section.
1) **The noise assumption**. The noise parameter $\sigma^2$ is defined as (forgetting about the $\delta^2$): $\sigma^2\geq \sup_{z,x} \|\nabla_x F(x,z)-f(x)\|^2$. Here, taking the sup over $x\in\mathbb R^d$ is not problematic (and $\delta^2$ is usually there to compensate for this), but I worry about this sup over $z\in Z$. Indeed, for the very simple setting of gaussian additive noise, the noise term here is equal to infinity. Previous works (e.g. [28] in the paper) instead consider $\bar \sigma^2$ for noise assumption (in the smooth non-convex or smooth-PL settings), where a mean is taken over $z$ instead of a sup. $\sigma^2$ here is thus not a noise variance, but an almost sure bound, which can be confusing.
Table 1 should also discuss this noise assumption.
2) **Non-convex rate, Table, and missing comparison**. *(a)* The same non-convex rate is present in [28], under milder noise assumptions. *(b)* The strongly convex rate in this same reference has no mixing time in the transient regime (i.e. in the linearly converging term), and its noise is taken at the *optimum* (and is thus often null). *(c)* *We note that the complexity
55 bounds which scale linearly with the mixing time of the underlying Markov chain are currently
56 available only for non-convex minimization problems*: this assertion is false, since rates exists for convex problems, PL problems [23,28].
These three points *(a,b,c)* lead the reviewer to have some concerns with comparison related works that are cited in this paper (and that I would not have read if not cited, so that this leads me to believe, are there some other existing works like this in the literature ?). Indeed, the non-convex rates should clearly be compared with those of [28], that seem stronger, if I understand well. Also, their strongly convex rates should be discussed: the rate of Theorem 1 can be faster in some cases but not all I think. These rates should thus be in table 1 also.
Questions
Questions related to the two major weaknesses/concerns above:
1. Is the accelerated rate in Theorem 1 obtained by adding stronger assumptions than previous works (i.e. a sup over the state space instead of a mean) ? I would like the authors to discuss this assumption, and its relation with other works.
2. Could the author provide a clearer comparison of their work to the related ones ? I think this requires adding some discussions in several parts of the paper.
3. The lower bound in [28] is in term of hitting time, and the authors of this paper provide an algorithm and analysis without noise assumption; could this be related to the current submission ?
Overall, I vote for acceptance, despite the concerns noted above, due to the contributions in variational inequalities, for the clarity of the paper, and the accelerated rate with batch randomization, while waiting for the authors' answer in order to provide a final decision.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
No such limitation noted.