First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
Authors: Aleksandr Beznosikov
Sergey Samsonov
Marina Sheshukova
Alexander Gasnikov
Alexey Naumov
Eric Moulines
Venue: NeurIPS 2023 poster (2023)
Keywords: convex optimization
stochastic optimization
Markovian noise
acceleration
variational inequalities
lower bounds

Abstract: This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.

First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
Aleksandr Beznosikov
Sergey Samsonov HSE University
Marina Sheshukova HSE University
Innopolis University, Skoltech, MIPT, Yandex
Alexander Gasnikov MIPT, Skoltech, IITP RAS
Alexey Naumov HSE University
Eric Moulines Ecole polytechnique
Abstract
This paper delves into stochastic optimization problems that involve Markovian noise. We present unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time the underlying noise sequence, based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research Markov noise, such the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.
the randomized batching scheme, which is
1 Introduction
Stochastic gradient methods are an essential ingredient for solving various optimization problems, with wide range of applications in various fields such machine learning [36] (37). empirical risk minimization problems [96), and reinforcement learning 933
Various stochastic gradient descent methods (SGD) and their accelerated versions 75 have been extensively studied under different statistical frameworks [17 97]. The standard assumption for stochastic optimization algo- rithms to consider independent and identically distributed noise variables. However, the growing usage of stochastic optimization methods in reinforcement learning [1O]
85
69
87 25 and distributed
optimization 63 65 has led increased interest problems with Markovian noise, Despite this,
existing theoretical works that consider Markov noise have significant limitations, and their analysis often results in suboptimal finite-time error bounds.
Our research aims to fill the gap in the existing literature on the first-order Markovian setting. By focusing on uniformly geometrically ergodic Markov chains, we obtain finite-time complexity bounds for achieving e-accurate solutions that scale linearly with the mixing time of the underlying Markov chain. Our approach is based on careful applications of randomized batch size schemes and provides a unified view on both non-convex and strongly convex minimization problems, as well as variational inequalities.
Our contributions. Our main contributions are the following:
Accelerated SGD. We provide the first analysis of SGD, including the Nesterov accelerated SGD method, with Markov noise without the assumption of bounded domain and uniformly bounded stochastic gradient estimates. Our results are summarised in Table and Section 2.J and cover both strongly convex and non-convex scenarios. Our findings for non-convex minimization problems complement the results obtained in 21
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Lower bounds. In Section 2.2 in the upper complexity bounds is not an artefact of the proof. This is consistent with the results reported in [71.
we give the lower bounds showing that the presence of mixing time
Extensions. In Section 2.4 we provide, far as we know, the first analysis for variational inequalities with general stochastic Markov oracle, arbitrary optimization set, and arbitrary composite term. Our finite-time performance analysis provides complexity bounds in terms of oracle calls that scale linearly with the mixing time of the underlying chain, which is an improvement over the bounds obtained in [99] for the Markov setting.
Related works. Next, we briefly summarize the related works.
Stochastic gradient methods. Numerous research papers have reported significant improvements achieved by accelerated methods for stochastic optimization with stochastic gradient oracles involving independent and identically distributed (i.id.)) noise. These methods have been extensively studied
39 [022] and have shown practical success [55] 21]. The time analysis of first-order methods in i.i.d. noise settings has been extensively studied by many authors, as discussed in (59] and references therein. In Table D we include only some important
in theory [4 L [6] (5% 61 226 30 97 944
G
results because i.i.d. setting is not in the interest of this paper.
While the literature on i.i.d. noise is extensive, existing research on the first-order Markovian setting is relatively sparse. In this study, we focus on Markov chains that are uniformly geometrically ergodic, and we refer the reader to Section 2 for detailed definitions. We note that the complexity bounds which scale linearly with the mixing time of the underlying general Markov chain are currently available only for general convex and non-convex minimization problems. Namely, [3] has investigated a version of the ergodic mirror descent algorithm that yiclds optimal convergence rates for Lipschitz, general convex and non-convex problems. Recently, [2T] proposed a random batch size algorithm that adapts the mixing time of the underlying chain for non-convex optimization with a compact domain. In particular, [21] Theorem 4.3] yields optimal complexity rates in terms of the number of oracle calls required for non-convex problems, which is consistent with the results obtained in [23] Unlike previous studies, this method is insensitive to the mixing time of the noise sequence.
For the general case of Markovian noise the finite-time analysis of non-accelerated SGD-type algorithms was carried out in [20] and [19.. However, [0] heavily relies on the bounded domain assumption and uniformly bounded stochastic gradient oracles, while its bound in 190 Theorem 5] has a suboptimal dependence on the mixing time of the underlying chain, see Table ! Additionally, [00 does not cover the strongly convex setting. On the other hand, [19 covers both non-convex and strongly convex settings, but the bounds of [19 Theorem I] has terms that are exponential in the mixing time, and careful examination reveals suboptimal dependence on the initial condition for strongly convex problems when SGD is applied.
SGD with Markovian noise, the authors of 20 considered the use of a batch size of and achieved a rate of forgetting the initial condition that matches that of the i.i.d. noise setting. However, their result is suboptimal in terms of the variance terms in both non-convex and strongly convex settings, as detailed in Table I We emphasize that the case of unbounded gradient oracles with Markov noise is not treated in contrast to the i.i.d. setup 197 62)
In the study of Nesterov
The above papers deal with general Markovian noise optimization. But there are also results that deal with Markovian stochasticity with finite state space. Here we can highlight the work (28). where the author gives quite extensive results and achieves linear scaling by mixing time in the non-convex as well as strongly convex cases. Recently, numerous papers have appeared dealing with the special scenario of distributed optimization [ p investigates the generalization and stability of Markov SGI) with special attention to the excess variance guarantees. We note that first, these algorithms only need to deal with a very special case of Markov gradients, and second, the corresponding dependence time, there exist particular results, e.g. 7T], which provide a lower bound for the particular finite sum problems in the Markovian setting.
the mixing time of the Markov chain is again quadratic. At the same
Variational inequalities. Variational inequalities [29 have been an active area of research in applied mathematics for more than half a century 78
86). VI cover important special cases, e.g., minimization over convex domain, saddle point or min-max and fixed point problems. optimization, supervised [51] ! 11 In the last 5 years, variational
41
computational game theory 20 robust 7 and nonsmooth 77
72
and unsupervised [103] 5 learning, image denoising 27
inequalities and their special cases have attracted much interest in the machine learning community

---

due to new connections to reinforcement learning
79 50
adversarial training
64 and GANs
15
33
60
Variational inequalities (VI) and saddle point problems have their own well-established theory and methods. Unlike minimization problems, solving variational inequalities doesn't rely on (accelerated) gradient descent. Instead, the extragradient method [57]] various modified versions [72 42], or similar techniques [5 are recommended as the basic and theoretically optimal methods. While deterministic methods have long been used for solving variational inequalities, stochastic methods have gained We summarise the results on methods for stochastic variational inequalities with the Lipschitz operator and smooth stochastic saddle point problems in Table 2 The number of papers dealing with stochastic VIs and saddle point problems is small compared to those dealing with stochastic optimization, we include in Table 2 papers with the i..dd. noise (which we do not do for stochastic optimization). The only competing work dealing with Markovian noise in saddle point problems consider the finite sum problem and thus the finite Markov chain [99], therefore we do not include it in Table Moreover, the results from [0] has much worse oracle complexity guarantees ((7²/=²) in terms of T. There are more papers dealing with stochastic finite-sum variational inequalities or saddle point problems, but in the i..dd setting 12 80 104 g We also do not consider in Table 2 because of the difference in the stochastic oracle structure. It is important to note that, unlike most previous works, we consider the most general formulation of VI itself for arbitrary optimization set and composite term.
importance only in the last 15 years, following pioneering works by 49 52
Notations and definitions. Let dz) be a complete separable metric space endowed with its Borel o-field 2. Let (ZM, 2 be the corresponding canonical process. Consider the Markov kernel Q defined
Z x 2, and denote by Pg and Eg the corresponding probability distribution and the expected value with initial distribution &. Without loss of generality, we assume that (Zx KeN is the corresponding canonical process. By construction, for any A Z, it holds that (Z E AlZx-1) = Q Q( A), P.g-..s. g = òz. = E Z, we write P. and EE, instead of I'x, and Es. respectively. For x x being the iterates of any stochastic first-order method, we denote Fx = 0 . S k) and write E2 as an alias for B[| We also write N = N \ {0). For the sequences (an NEN and (bw)nen we write On S b, if there exists a constant such that that O, S cb, for all n E N.
Table 1: This table summarizes results first-order method with Markovian noise. The columns of the table indicate whether the authors consider optimization over bounded domain, potentially unbounded gradients, and whether or not they assume additional restrictions on the Markovian noise (finite state space or reversibility). For ease of comparison we provide the respective results on SGD and ASGD (accelerated SGD) in the i.i.d. setting.
Mcthoa
Graden
Arrkniike
meptaly
500 DEAC
NA
NA
0 (20144) RonD
MG
12
x
8
( [o+ 12122
6 mos
14500 bam
o (p4iris' - 1e
nutution: and L are opciissatio domain:
ad
_. [VF Note that G 2 L Gnd of under All We also set B sup, [ell] x stantng poin g solution, D. : tine the chain
Rechanticity parmetess All sochasticity
accuracy Se the stouply convex ones. Punctions Lije and H(G, sunds for impborr
solution, measared as fi is non convex problems Elli-
respestive panmnssers.
clas way Markov noise aubyis EM]l jequres revesibiltty Paraeeeer c (1/2. tefes to stp 1/et.
Moekision Sh general stane spocr fuucuation tems Thereen 1.3 comain bidden dapendence fiscouation terms, makag result computison complicated. They contain hidden factors whtch are exponential in 7/ log the with finiee state space spocilicallly decresing step sire. Morcover the procr of Thoeee 1) joquetions (61) (66) the auther lod the feter C* with C= log 4. The mealt the sahte accomnts for this lost factor coneikere the ine miing of buch wns, which is ublisinnss ior.. consiton Markos miie with fime state space and addiionnlll aoomes that all stnchasric realivation FV, 23 are L. smooth. consders Marrksston noise with tane stare space, bounds noise only x", bet adittinallly asumes that all stochastic redizztioon Ft; 2) are L. L-smooth and jr scougly conves.
grves
oxpsira a panmater
Coraliar
mom general setting,
the inttal enorr
IIl
astuions our papes. Morsweer, the atalyis. of repires F"r.:) Lipudiie wir. for any e "cmmilles Marksian
2 Main results
Assumptions. In this paper we study the minimization problem
minzer [xx = Ez~a (xx 2)),
where the access to the function / and its gradient is available only through the (unbiased) noisy oracle F(x, Z) and Vf Z), respectively. In the following presentation we impose at least one of the following regularity constraint on the underlying function ff itself:
3

---

Table 2: This table summarizes the findings methods for solving stochastic (strongly) monotone variational inequalities with a Lipschitz operator and (un)bounded stochasticity. The columms of table indicate whether the authors consider variational inequalities or only certain saddle point problems, the arbitrariness of the sets, and the use of additional composite terms, The columns on stochasticity provide information on the assumptions made with respect the stochastic operator, such as bounded variance and the Markovian noise setting. Note that with the exception of our work, all other studies assume the independent noise.
Statement
Stochasticity
Method
VI?
Any set?
Composite?
Unbounded!
Markovian?
Orack complexity
SPOr
13 FM
X
A log 12
SEA
/
x
x
I=
p
98-
/
1
log
1=0
+
SBG
8
8
# log
10!--a1
Simogy
DBEG
8
8
22
86
8
log
90DA 1
1
x
log
IEG (ours)
v
log
37
x
x
LD
VR: 9E0 85
x
x
Monntose
x
1
0
1igt
58-960
1
8
2n
12
SEG 2
8
x
0
RBG (ours)
E.22
notation: = constant of strong monotonicity of operator F, -= Lipschitz constant of F. B uniform bound of F. D- uniform
bound of itcrations a², x² starting point, solution, A and stochasticity parameters (sce A 62 (N 98 take A 0), stochasticity parameter x" (see (68). mixing time of the chain (sce A B accuracy of the solution.
(D) give results with stepsize parameter, choose according tn Section 3 from [Т consider A 7 hut do not provide explicit rates if A # (see also Table Table IJ). consider the cocoercive case. for which in general L2/p
A 1. The function f is L-smooth on IR'' with L > 0, i.., it is differentiable and there is constant > 0 such that the following inequality holds for all x, y Rdd
[V f((ii - -
A 2. The function f is pusttrongly convex on R2, i.e., is continuously differentiable and there is constant μ > O such that the following inequality holds for all x, E Rd:
(n/2)][z y112 s f(x) - f()) (Vf(v)xr-))
(2)
Next we specify our assumptions on the sequence of noise variables { We consider here the general setting of { being homoohoogess Markov chain. Such problems naturally arise stochastic optimization.
the empirical risk minimization problems it naturally appears in the context of non-random minibatch choice. Indeed, a random choice of a batch number may lose to non-random one, see 67 (56) wide range of problems dealing with Markovian noise spawned by the reinforcement learning methods. The usual MDP setting falls naturally inside this paradigm, moreover, the analysis of non-tabular RI. problems requires to deal with the general state-space Markov noise. Here the potential range of applications include the policy evaluation methods, such as the temporal difference methods [22, and policy optimization algorithms, such as policy gradient family, e.g. the celebrated REINFORCE algorithm [100].
We denote by Q the Markov kernel corresponding to the sequence {2 and impose the following assumption on the mixing properties of Q;
3. { is a stationary Markov chain on (Z, Z) with Markov kernel Q and unique invariant distribution æ. Moreover, Q is uniformly geometrically ergodic with mixing time 7 E N, i.e., for every k E N,
(Q²)) sup (upp..re(1/2))10
(=', S (1/4)Lb/T1.
The assumption A 3 is classical in the literature on optimization methods with Markovian noise and has been considered in particular in recent works (90 21 20 In particular, this assumption covers finite state-space Markov chains with irreducible and aperiodic transition matrix considered in

---

28 Yet our definition of the mixing time T is more classical in the probability literature [1], and slightly different from the one considered e.g. in 28 651. Next we specify our assumptions on stochastic gradient:
4. For all x E Rd it holds that E,, (x,,, - = Moreover, for all z and x E Rd
holds that
[VF 2) vf(=))² 1
The assumption A resembles the strong growth condition 197 which is classical for the over- parametrized learning setup 9 28 The main difference is that A concerns the almost sure bound
in 4 which is unavoidable when dealing with uniformly geometrically ergodic Markovian noise and scales with the 2 in the particular problems. With the assumptions A and A 4 we can prove the result on the mean squred error of the stochastic gradient estimate computed over batch size n.
3 Note that it is possible that the quantity 8 in H is not iustance-independee
ratio 1./P from A A
under arbitrary initial distribution. This result is summarized below in Lemma !
Lemma 1, Assume A
5 and A 4 Then, for any n 2 and x E RR, it holds that E Ex EE
F( 7:) - V ((())) v Sr (o² + 6 (V))))
(5)
Moreover, for any initial distribution & on (Z, 2), that
BeIlnn VF(x, Z:) - (z)] v ميت (o² (d"+o'1 (V
(6)
where C₁ = 16(1 + Im*4/
Proof.
We first prove Note that due to 81 Proposition 3.4] the Markov kernel Q under A
admits positive pseudospectral gap pps > 0 such that 1/7ps I 2r. Thus, applying the statement of
88 Theorem 3.2], get under A 4 that
Ex 1= VF 2,) {)()))?? S F..
17pp
To prove the second part we use the maximal exact coupling construction and follow, e.g.. Theorem 1]. The complete proof is given in Appendix B.I
The proof of Lemma
D simplifies the arguments in 21 Lemma 4] and allows us to obtain tighter values for the constants when dealing with the randomized batch size. Note that it is especially important to have the result for MSE under arbitrary initial distribution ç, since in the proofs of our main results we will inevitably deal with the conditional expectations w.r.t. the previous iterate. We provide more details on the bias and variance of the Markov SGD gradients in the next section.
2.1 Accelerated method
We begin with version of Nesterov accelerated SGD with randomized batch size, described in Algorithm I Due to the unboundedness of the stochastic gradient variance (see A D. using of the classical Nesterov accelerated method 776 Section 2.2.] does not give the desired result, is necessary to introduce an additional momentum 74 9 We use our own version, but partially similar to 74 197. The main feature of Algorithm D is that the number of samples used during the k-th gradient computation scales as 2dx,, where JR comes from truncated geometric distribution. The truncation parameter needs to be adopted (see Theorem D in order to control the computational complexity of the algorithm.
Randomized batch size allows for efficient bias reduction in the stochastic gradient estimates and can be seen as a particular case of the so called multilevel MCMC [5 34] In the optimization context this approach was successfully used by (1 for the non-convex problems. Indeed, this bias naturally appears under the Markovian stochastic gradients oracles. It is easy to see that, with the counter T defined in Line
we have
Es [V ZT+ + ff(**).
Below we show how the bias of the gradient estimate scales with the truncation parameter M. The statement of Lemma yields that the gradient estimates 9₁ introduced above have the bias, which decreases quadratically with M.
Lemma 2. Assume A and d
Then for the gradient estimates g² from Algorithm 1 iit holds that
Eg [g = Li Mil. Moreover,
E& (x+
g/1 S
M 3) +8
[V*( Enlg/112 -2 +
5

---

Algorithm Randomized Accelerated GD
1: Parameters: stepsize >> 0, momentums 0, 1), 3, p. number of iterations N, batchsize limit M
2: Initialization: choose x² =
3: for 0. ................................ N 1 do
4: x6 / (1 0)
5: Sample Jn ~ Geom (1/2)
2 (ot, -93 -1), if2 S M otherwise
6:
ge 96 +
22 = 21 with
Vf(zz Zr+44
0.
7:
f k+ Ig prg
8:
xt1 qty + (p - n + 11-pp(11 - -B)x +(1 1e--pp (11-p)) p)
9:
Th++1 = T + 22 B
10:
end for
The proof and the statement with explicit constants are given in Appendix 3.2 Note that the Lemma is a natural counterpart of the deterministic bound Lemma Moreover, it gives the idea of the trade-off between the parameters B and M. Namely, the expected number of oracle calls compute Ik is ( log2 (M)) with the bias scaling as M-2. Thus the increase of M drastically reduced the bias with only a logarithmic payment in variance. At the same time, gradient variance scales as (T but the increase of B is much more expensive for the computational cost of the whole procedure. Taking into account the considerations above, we can prove the following result:
Theorem 1. Assume A A 4 y E (0; 31. and 3,0, 0, 7) P. M. B
Let problem O
be solved by Algorithm
7
Then for any b E N",
satisfying
(1 (1 + 16 + +
3 VPuuy, 7
V A4
pn -
M = vp (1+p/3))
B = [blog M,
3pn
holds that
E $11IN - x-
11+
+1 (f((x))) - f(x*)) S Sexp p2u
1 -x (f(x²) - f(x)))
x
(a² 02 (7)
The proof is provided in Appendix B.3
The result of Theorem be rewritten upper complexity bound under an appropriate choice the remaining free parameter b: Corollary 1. Under the conditions of Theorem 7 choosing
and 7
7 min { FAN' In (max {2, NaNIll x 11 +6p (((aa)) fl" }}}
in order to achieve E-approximate solution (in terms of B[[2 [[[||x x² 1=1 S E) it takes
δ ( log + Aie
oracle calls.
(8)
The results of Corollary [ are obtained with fixed parameters of the method. In Corollary these parameters are selected bit artificially, e.g., the stepsize 7 depends on the iteration horizon N. In Appendix B.4 we show how one can similar results, but with a decreasing stepsize.
Comparison. Running the procedure above requires to know the mixing time 5. Estimating the mixing time from a single trajectory of the running Markov chain is known to be computationally hard problem, see e.g. [OI and references therein. At the same time, methods, which share the same (optimal) linear scaling of the sample complexity w.r.t. the mixing time also share the same drawback as our method. particular, it holds true for the EMD algorithm (23) SGD-DD algorithm [7I] and usual SGD with Markovian data [28] At the same time, in the non-convex scanario the paper 21 is truly oblivious to mixing time, allowing to obtain sample complexity rates non-convex problems, which are homogeneous w.r.t. with AdaGrad-type learning rate. An interesting direction for the future work to suggest a procedure that would allow to generalize the results of (2 accelerated SGD setting.

---

It is possible that the sample complexity bound 8 is worse than the respective bounds for non- accelerated SGD with Markov data, provided that d² grows quickly with L/μ. At the same time, this drawback is shared by the classical results on learning under the strong growth condition, see e.g. [97]. As it shown in [2], the respective rates can be worse than the ones obtained by usual SGD even under the i.i.d. noise setting, see Appendix F.3 in 62] Making the analysis of accelerated SGD 'backward compatible" w.r.t. the rates of usual SGD requires to perform analysis in terms of additional problem-specific quantities, see 47 62
The closest equivalent of the result Corollary is given by 20
Theorem 3]. However, the correspond- ing bound of (20, Theorem 3] is incomplete, since the factor 7² is lost in the proof (see equations (64- 66)) With this completion, the bound of (20 Theorem 3] yields a variance term of order
1 which is suboptimal with respect Moreover, the corresponding analysis relies heavily on the assumption of a bounded domain. In 2X the author considers Markovian noise with a finite number of states and manages to obtain a rather interesting result of the form O ( log _ + Lrg. a Here the first term does not depend т, and the second consists only a² (stochasticity in x²),, but the price for this is an additional factor T./1 in the second term and more strict assumption that all smooth and strongly convex. In the context of overparameterized learning, results are almost consistent with the bound of (97 Theorem 1] under i.i.d. sampling. The difference that the term 8² in A can be more pessimistic than the expectation bound in 197)
realizations F(::2)
2.2 Lower bounds
We start with a lower bound for the complexity of Markovian stochastic optimization under the assumptions A
Below we provide a result that highlights that the bound of Theorem i tight provided that ó does not scale with the instance-depended quantities, e.g., condition number L/ μ.
Theorem 2. There exists an instance of the optimization problem satisfying assumptions A 7 A
with 8 = 1 and arbitrary 2 0, L, 1, > 0, E Nº, such that for any first-order gradient method takes at least
N = Ω (T I log 1
Ia? FTe
oracle calls in order to achieve E|||a:N - x 11 S
The proof is provided in Appendix B.5
The idea of the constructed lower for deterministic part
Theorem 2.1.13]. The stochastic part lower bound goes back to the classical statistical reasoning, and is well explained for i..d. noise in 59 Chapter 4.1]. Our adaptation for Markovian setting is based on Le Cam's theory,
bound (T log !) goes back to 76
[1] Theorem 8), and also [105]. For the case of Markov noise this lower bound is, to the best of our knowledge, original. The closest result to ours is the stochastic term lower bound in 28 Proposition 1]. but it is valid only for the vanilla stochastic gradient methods. Below we provide another lower bound showing that the dependence of the sample complexity Corollary on 8 is not an artefact of the proof.
Proposition 1. There exists an instance of the optimization problem satisfying assumptions A A 4 and a = O, such that for any first-order gradient method
with arbitrary L, > 0, T E N', 8 p² takes at least
N S2 ( log
gradient calls in order to achieve B|[|=* - x 11 S E.
This lower bound is adapted from the information-therr
lower bound 771. The detailed proof can
be found in Appendix B.5 Recent studies [54] 7 [ have revealed the impossibility of accelerating stochastic gradient descent (SGD) for online linear regression problems with specific noise structures.
To address this issue, researchers have proposed various solutions, such as the MaSS algorithm [6] and the approach presented in 4 However, these methods rely heavily the particular structure of the online regression setup. Another question that naturally arises is whether one can get rid of the
dependence on in the deterministic part of g if 8 = 0. The following counterexample shows that
this is not the case in general.
Proposition 2. There exists an instance of the optimisation problem satisfying assumptions A with with arbitrary L, > 0, E No, a = 1, = O, such that for any first-order gradient method it takes at least
N = ((T log
7

---

oracle calls in order to achieve -x"1
The proof is provided in Appendix B.5
2.3 Non-convex problems
Now we proceed with a randomized batch size version of the simple SGD algorithm. it summarized in Algorithm 2 and can be shown to achieve optimal rates of convergence for smooth non-convex problems. For the case of non-convex problems with Markov noise similar analysis appeared P1 Theorem 4].
Algorithm 2 Randomized GD
Parameters: stepsize y >> 0, number of iterations K, bound on batchsize B, mixing time T;
2: Initialization: choose æº E X'
3: for k == 0, ..,
do
4: Sample JR ~ Geom (2)
2 (gf, - -1),
if S
5: g" = 9o
with =2 22' Vf(a" Zy441)
otherwise
6:
xt+1 = x² 79
7: Th+1 = t + 2
8:
end for
By balancing the values of B and M with Lemma establish the following result:
Theorem 3. Assume A A A A 4
Let problem be solved by Algorithm
2 Let f be a global
(maybe not unique) minimum of Then for any b N and 7, M satisfying
Y S (L(1 + 0 + - --)
M max --11,
B = [blogg M),
it holds that
E
Vf(=>)| x
1(a)- 7N + L 0
The proof is provided in Appendix Corollary 2. Under the conditions of Theorem
B.6
The next corollary immediately follows from the theorem.
if we choose T and Y given by
min I(
LNo
then to achieve e-solution (in terms of ( $²)
need (1=)))1(()))))) + -
oracle calls.
Comparison. The respective bound for the non-convex setting provided in [20 Theorem 1] yields the sample complexity of order ò ( Also we can note the results of Theorem
ex
2] with the following estimate O (
To achieve linear convergence rates in the non-convex setting we can use the Polyak-Lojasiewicz (PL) condition
S The respective result is provided in Appendix B.7
2.4 Variational inequalities
In this section, we interested in the following problem:
Find x" E X' such that (F(z*), x z²) + r(x) - r(=*) 2 for all e X. convex set, and r: Rd -
(9)
Here F: Rd + Rdd an operator, lower semicontinuous convex function) which is assumed to have simple structure. As mentioned carlier, this problem is quite general and covers a wide range of possible problem formulations. For example, if the operator F is the gradient of convex function f. then the problem Q is equivalent to the composite minimization problem [ i.e., minimization of f(x) > + r(x). In the meantime, also reformulation of the min-max problem
regularization term (a suitable
min max ri (x1) + g( 22) - r2(x2), #i EX 2yER2
(10)
with convex-concave continuously differentiable g. convex sets Xi, Nr and convex functions r1. r2- Using the first-order optimality conditions, easy to verify that (10) equivalent to ( with 2 F(x)= (V., (2)1 V og (21, (2), TT) and r(z) ri (1(11) Fr((22).

---

A 5. The operator F is L-Lipschitz continuous on X' with L > 0, i.e., the following inequality holds for all z, E X:
[F(x) F(v)ll S 1 - vll. Vx, y E X. 6. The operator F is pp-strongly monotone on X. i.e, the following inequality holds for all
y X:
(F(x) F(y), x - v) 2 pr || -
(11)
The function r is Ptr-ononglly convex X, i.e. for all x, y X and any r'(x) E ar(x)) have
rly) 2 r(x) + (z), z) + (1z/2) -11
(12)
These two assumptions are more than standard for the study of variational inequalities and are found in all the papers from Table 2 We consider two cases: strongly monotone/convex with PF + Hr > 0 and monotone/convex with Pe + Mr, O.
A 7. For all x E IRd it holds that [x 2)] F(x). Morcover, for all E Z and E X it holds that
- s o² A²| -
(13)
where x² is some point from the solution set.
is found in the literature on variational inequalities
and is considered to be analog to 95
on overparametrized learning.
Just the Nesterov accelerated method is optimal for smooth convex minimization problems, the ExtraGradient method [57
72 52 is optimal for monotone variational inequalities. Therefore, we take base. On the extrapolation step (Line of Algorithm we simply collect batch of size B. but on the main step (Line the convergence of our method.
8 we use the randomization as in Algorithm |
The next theorem gives
Theorem 4. Assume A A with uF + prr 0, A Then for any E N,, and 7/ M satisfying
Let problem
be solved by Algorithm
? S min (UF + (r) : -- (#F (A) -22 VA 27
M max /T- (1r + (4)) -+]
B = [blogg M
it holds that
E [1 x² [1]] S exp (- N(ugtaa))
1100 11
02
The proof is postponed to Appendix B.8 One can get an estimate on oracle complexity.
Algorithm 3 Randomized ExtraCradient
1: Parameters: stepsize ? 0, number of iterations N
2: Initialization: choose x E X'
3: for k = 0, 2......... N
do
4: *+1122 prox,. yr (- BB-BB111
B F(* ZTn4:))
5: T = T B
6: Sample Jj Geom
7:
-e o0 +
2x (gti.
-),-1),
i < M otherwise
with = 22' n F(a 271+1/22))
0,
8:
k+1 prox ( 718*)
9:
Th+ = 1/2 1/2 2J BBB B
10:
end for
Corollary 3. Under the conditions of Theorem
4 if we choose b - and r as follows
min
{ pprpp's
1. oF tpr
N(uFtut) In max {2; uN||=
0² })}
L: A
then to achieve e-solution (in terms of E[[l/ x² 12] E) we need
ò ÔT. f1.[11+ artp. + artRo + (p log + x oracle calls.
A

---

Note that one provide an (almost) matching lower complexity bounds for variational inequalities via lower bounds for saddle point problems, which are special case of variational inequalities. The method for obtaining lower bounds for saddle point problems is reduced to obtaining estimates for the strongly convex minimization problem (see [T06 40 for respective deterministic lower bounds), which we provide in Section 2.2 Similarly, the question of constructing a lower bound which is tight w.r.t. A remains open.
For the monotone case, we use the gap function as a convergence criterion:
Gap(z) = supyex (F) x - y) + r(z) - r(y)]
(14)
Such a criterion is standard and classical for monotone variational inequalities 7/2 important
assumption for the gap function is the boundedness of the set X'
A 8. The set X' is bounded and has diameter D, i.e., all x, y E X:
|| yl < D²
g can be slightly relaxed. We need to use a simple trick from [77]. In particular, we need to consider
C- compact subset of X' and change X' to C in (4.. But such technique is rather technical and does not change the essence. Finally, the following result holds.
Theorem 5.
Assume
S A o with pe + μr = 0. A
Let problem 9 be solved by M /N, it holds that
Algorithm Then for any B N", and 7. M satisfying Y
E Gapp(>
D2 N
( loga N 2 + D2) where x. 1/2 E 1
The proof is postponed to Appendix
B.9
The following corollary holds.
Corollary 4. Under the conditions of Theorem
S if we choose B and y as follows
min
Li (o=+A-D=)N
Da
then to achieve E-solution (in terms of E[Gap(æ)] $ E) we need
δ (- (T[Ee² LD²
oracle calls.
Comparison. These results is the first for variational inequalities with Markovian stochasticity, either in the strongly monotone or monotone cases. The only close work is 999]. The authors work with convex-concave saddle point problems and provide the following estimate on the oracle complexity O ( - in terms of Moreover, the authors consider the case of finite Markov chain, which is special case of our setup.
(with G the uniform bound of the operator), which is worse than ours at least
3 Conclusion
In this paper, present unified random batch size framework that achieves optimal finite-time performance for non-convex and strongly convex optimization problems with Markov noise, as well as for variational inequalities. Unlike existing methods, our framework relaxes the assumptions typically imposed on the domain and stochastic gradient oracle. We also provide variety of lower bounds, which are to the best of our knowledge original in the Markov setting.
Acknowledgments
This research of A. Beznosikov has been supported by The Analytical Center for the Gov- ernment of the Russian Federation (Agreement No. 70-2021-00143 dd. 01.11.2021, IGK 000000D730321 P0000002))0000) E. Moulines received support from the grant ANR-19-CHIA SCAI and parts of his work has been done under the auspices of Lagrange Center for maths and computing.
References
[1] Eddie Aamari and Clément Levrard. Nonasymptotic rates for manifold, tangent space and curvature estimation. The Annals of Statistics, 47(1):177 204, 2019.
[2] Ahmet Alacaoglu and Yura Malitsky. Stochastie variance reduction for variational inequality methods. In Conference Learning Theory, pages 778-816. PMLR, 2022.
10

---

[3] Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A uni- versally optimal multistage accelerated stochastic gradient method. Advances neural information processing systems, 32, 2019.
[4] Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity-inducing penalties. arXiv preprini arXiv: 108.0775 2011.
[5] Francis Bach, Julien Mairal, and Jean Ponce. Convex sparse matrix factorizations. arXiv preprint arXiv:0812.1869 2008.
[6] Amir Beck. First-order methods in optimization. Society for Industrial and Applied Mathe- matics (SIAM), 2017.
[7] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization. Princeton University Press, 2009.
[8] Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 172-235. PMLR, 2023.
[9] Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, optimal and robust algorithms. arXiv preprint TrXiv:2010.13112 2020.
[10] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691- 1692. PMLR, 2018
[1]] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 40(1):120-1455 2011.
[12] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. Advances in Neural Information Processing Systems, 32, 2019.
[13] You-Lin Chen, Sen Na, and Mladen Kolar. Convergence analysis of accelerated stochastic gradient descent under the growth condition. arXiv preprint arXiv:2006.0678) 2020.
[14] Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in neural information processing systems, 24, 2011.
[15] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv: 2017.
[16] Olivier Devolder et al. Stochastic first order methods in smooth convex optimization. Technical report, CORE, 201
[17] Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1):352033500 2017.
[18] Alexandros G. Dimakis, Soummya Kar, José M. F. Moura, Michael G. Rabbat, and Anna Scaglione. Gossip algorithms for distributed signal processing. Proceedings of the IEEE. 98(11):1847-1864 2010.
[19] Thinh T. Doan. Finite-time analysis of markov gradient descent. IEEE Transactions Automatic Control, 68 68(4):2140-215 2023.
[20] Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Convergence rates of accelerated markov gradient descent with applications reinforcement learning. arXiv preprint arXiv:2002.00 02873, 2020.

---

[21] Ron Dorfman and Kfrr Ychuda Levy. Adapting to mixing time in stochastic optimization with markovian data. In International Conference on Machine Learning pages 3429-5446. PMLR, 2022.
[22] R. Douc, E. Moulines, P. Priouret, and P. Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering. Springer, 2018.
[23] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1578, 2012.
[24] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Marina Sheshukova. Rosenthal-type inequalities for linear statisties of markov chains. arXiv preprini arXiv:2303. 058388, 2023.
[25] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Hoi-To Wai. On the stability of random matrix product with markovian noise: Application to linear stochastic approximation and td learning. In Conference on Learning Theory, pages 1711-1752. PMLR, 2021.
[26] Pavel Dvurechensky and Alexander Gasnikov. Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. Journal of Optimization Theory and Applications, 171:121-145, 2016.
[27] Ernie Esser, Xiaoqun Zhang, and Tony F Chan. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences,
2010.
[28] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. arXiv preprint 1444: 2023.
[29] F. Facchinei and J.S. Pang. Finite-Dimensionul Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2007.
[30] Alexander Vladimirovich Gasnikov and Yu E Nesterov. Universal method for stochastic composite optimization problems. Computational Mathematics and Mathematical Physics, 58:48-64, 2018
prabbee
[31] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
[32] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming. 155(1-2):267-355, 2016.
[33] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien
A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802. 10551, 2018.
[34] Michael B. Giles. Multilevel monte carlo path simulation. Operations Research, 55(3):607- 617, 2008
[35] Peter W Glynn and Chang-han Rhee. Exact estimation for markov chain equilibrium expecta- tions. Journal of Applied Probability, 51 (A):377733 2014.
[36] Ian Goodfellow, Jean Pouget- Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NIPS), 2014.
[37] Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cam- bridge, MA, USA, 2016. http://www.deeleeannnoooo..o org
[38] Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 7865-7901. PMLR, 2022.
12

---

[39] Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexan- der Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2106.0599 2021.
[40] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint urXiv:2103.08220 2021.
[41] P. T. Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complemen- tarity problems: a survey of theory, algorithms and applications. Mathematical programmingg. 1990.
[42] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
[43] Yu-Guan Hsich, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances Neural Information Processing Systems, 33:16223-16234, 2020.
[44] Chonghai Hu, Weike Pan, and James Kwok. Accelerated gradient methods for stochastic optimization and online learning. Advances in Neural Information Processing Systems, 22, 2009.
[45] A. N. lusem, A. Jofré, R. I. Oliveira, and P. Thompson. Extragradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2):686 724, 2017.
[46] Alfredo N lusem, Alejandro Jofré, and Philip Thompson. Incremental constraint projection methods for monotone stochastic variational inequalities. Mathematics of Operations Research, 44()):236-263, 2019.
[47] Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pages 545-604. PMLR, 2018.
[48] Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18(223): 4-4, 2018.
[49] Houyuan Jiang and Huifu Xu. Stochastic approximation approaches to the stochastic variational inequality problem. JEEE Transactions on Automatic Control, 53(6):1462-14777 2008
[50] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119, pages 4890-4900 PMLR, 2020.
[51] Thorsten Joachims. support vector method for multivariate performance measures. pages 377-384, 01 2005.
[52] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror prox algorithm. Stochastie Systems, 1(1):17-58, 2011.
[53] Aswin Kannan and Uday V Shanbhag. Optimal stochastic extragradient schemes for pseu- domonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779-88) 820, 2019.
[54] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. In 2018 Information Theory and Applications Workshop (ITA), pages 1-9. IEEF, 2018.
[55] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.66000 2014.
13

---

[56] Anastasia Koloskova, Nikita Doikov. Sebastian U Stich, and Martin Jaggi. Shuffle SGD is always better than SGD: Improved analysis of SGD with arbitrary data orders. arXiv preprint arXiv:2305. 19259, 2023.
[57] M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:35 49, 1977.
[58] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1-2):365-397 2012.
[59] Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. 01 2020.
[60] Tengyuan Liang and James Stokes. Interaction matters: A note on non- non-asymptotic local con- vergence of generative adversarial networks. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 907-915. PMLR, 16-18 Apr 2019.
[61] Qihang Lin, Xi Chen, and Javier Pena. A smoothing stochastic gradient method for composite optimization. Optimization Methods and Software, 29(6):1281-1301 2014.
[62] Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over per-parraeterized learning. arXiv preprint arXiv: 13395,, 2018.
[63] Cassio G. Lopes and Ali H. Sayed. Incremental adaptive strategies over distributed networks. IEEE Transactions on Signal Processing, 55()):4064 4077, 2007.
[64] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
[65] Xianghui Mao, Kun Yuan, Yubin Hu, Yuantao Gu, Ali H. Sayed, and Wotao Yin. Walkman: random-walk algorithm for decentralized optimization. IEEE
A communication-effiee Transactions on Signal Processing, 68:2513-2522 25288, 2020.
[66] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint / 2018.
[67] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Sim- ple analysis with vast improvements. Advances in Neural Information Processing Systems, 33:17309- 2020.
[68] Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pages 4573 4582. PMLR, 2020.
[69] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep rein- forcement learning. Nature, 518(7540):529-53) 2015.
[70] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. J. Shawe-Taylor, R. Zemel, P. Bartleut F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[71] Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. Advances neural information processing systems, 33:16666-16676, 2020.
14

---

[72] Arkadi Nemirovski. Prox-method with rate of convergence O(I/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal Optimization, 15(1):229-22) 2004.
[73] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103(1):127-152, 2005.
[74] Yu. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012.
[75] Yu. E. Nesterov. method for solving the convex programming problem with convergence rate O(1/k²). Dokl. Akad. Nauk SSSR, 269(3)5533-577, 1983.
[76] Yurii Nesterov. Introductory lectures on convex optimization: basic course, volume 87. Springer Science & Business Media, 2003.
[77] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319-344, 2007.
[78] J. Von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1944.
[79] Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P. How, and John Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70,
pages 2681 2691- PMLR. 2017.
[80] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. Advances in Neural Information Processing Systems, 29, 2016.
[81] Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20(none):1 32, 2015.
[82] Wei Peng, Yu-Hong Dai, Hui Zhang, and Lizhi Cheng. Training gans with centripetal acceleration. Optimization Methods and Software, 35(5):955-973, 2020.
[83] B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864-878, 1963.
[84] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):400-444 407, 1951.
[85] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897.
PMLR, 2015.
[86] Gesualdo Scutari, Daniel Palomar, Francisco Facchinei, and Jong-shi Pang. Convex optimiza- tion, game theory, and variational inequality theory. Signal Processing Magazine, IEEE, 27:35 44, 06 2010.
[87] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory, pages 2803-2830. PMLR, 2019.
[88] Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv:1907.042333 2019.
[89] Tao Sun, Dongsheng Li, and Bao Wang. Adaptive Random Walk Gradient Descent for Decentralized Optimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 20790-20809, PMLR, 17-23 Jul 2022.
[90] Tao Sun, Yuejiao Sun, and Wotao Yin. Markov chain gradient descent. Advances in neural information processing systems, 31, 2018.
15

---

[91] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum deep learning. In Sanjoy Dasgupta and David McAllester. editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1139-1147, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[92] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3:9-44, 1988.
[93] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[94] Adrien Taylor and Francis Bach. Stochastic first-order methods: non-asymptotic and computer- aided analyses via potential functions. In Conference on Learning Theory, pages 1934-2992 PMLR, 2019.
[95] Paul Tseng. A modified SIAM Journal Control and Optimization, 38(2):331-446, 2000.
splitting method for maximal monotone mappings.
[96] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[97] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over-parameterrzee models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and stafistics, pages 1195-1204. PMLR, 2019.
[98] Sharan Vaswani, Aaron Mishkin, Issam H. Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. CoRR, abs/1905 abs/1905.09997, 2019.
[99] Puyu Wang, Yunwen Lei, Yiming Ying, and Ding-Xuan Zhou Stability and generalization for markov chain stochastic gradient methods. arXiv preprint arXiv:2209.0800. 2022.
[100] Ronald J Williams. Simple statistical gradient- algorithms for connectionist rein- forcement learning. Machine learning, 8:229-2566 256, 1992.
[101] Geoffrey Wolfer and Aryeh Kontorovich. Estimating the mixing time of ergodic markov chains. In Conference Learning Theory, pages 3120-3159. PMLR, 2019.
[102] Blake Woodworth and Nathan Srebro. An even more optimal stochastic optimization algo- rithm: minibatching and interpolation learning. Advances in Neural Information Processing Systems, 34:7333-7345 2021.
[103] Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2005.
[104] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of conconvex-noncomee R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1153-1165. Curran Associates, Inc., 2020.
minimax problems. In H. Larochelle, M. Ranzato,
[105] Bin Yu. Assouad, Fano, and Le Cam, pages 423-435, Springer New York, New York, NY, 1997.
[106] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems, arXiv preprint 191.0.191, 2019.
16


Reviews:
[{"review_id": "8yeHNwxxCk", "reviewer": "Reviewer_11kd", "summary": "This paper studies the convergence of first-order methods with Markovian noise for solving stochastic optimization problems and variational inequalities. The authors establish finite-time complexity bounds which scale linearly with the mixing time of the underlying Markov chain. ", "questions": "It is suggested that the authors should provide some simple numerical experiments to demonstrate the effectiveness of the proposed algorithms.\n", "limitations": "Yes. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper analyzes SGD (with and without Nesterov acceleration) with Markovian noise without the bounded domain and unifomly bounded stochastic gradient estimate assumptions, for both strongly convex and nonconvex scenarios. Matching lower bounds are also provided for the strongly convex case. Finally, an analysis for variational inequalities with general stochastic Markov oracle, arbitrary optimization set and arbitrary composite term is also provided. The results are interesting and appear to be novel.", "weaknesses": "Purely theoretical paper. No numerical experiments are provided. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer __11kd__ for the work and for the positive feedback! Next, we answer the issues raised.\n\n__W1__ and __Q1__(experiments):\n\nUnfortunately in a week to respond, we couldn't make the final version of the experiments, but we promise to add a set of experiments to vary the theory in the new version of the paper (the final one, if the paper is accepted). In particular, now we aim at practical verification of some theoretical dependencies. For example, Reviewer __9UP4__ asked to observe the linear dependence on the mixing time and also include numerical results for the Variational Inequalities (VI) setting. We aim to illustrate the benefits of the proposed approaches on the policy evaluation problems on the discrete type environments solved within the TD ($\\lambda$)-type algorithms."}, {"review_id": "rhLCNHOU5t", "reviewer": "Reviewer_9UP4", "summary": "This paper presents an optimization study focusing on stochastic optimization with Markovian noise as opposed to i.i.d. noise. The authors explore three distinct scenarios: strongly convex, non-convex, and Variational Inequalities (VI). In comparison to previous research, they relax the boundedness assumptions related to the domain or gradient magnitude for cases 1 and 2. The newly proposed convergence bounds exhibit linear dependence on the mixing time, whereas previous works relied on quadratic or exponential dependence. The authors establish a lower bound to demonstrate the optimality of this linear dependence. Notably, this work is the first to demonstrate the convergence of the stochastic EG algorithm for VI inequalities under Markovian noise.", "questions": "1- There are some typos in your proofs in supplementary materials e.g. in the proof of Lemma 2, in the equation after line 601, it should be Log M instead of log N and x^k_g instead of x^k. \n\n2- There is no discussion in the paper about a range of \\delta^2 appearing in the accelerated rate. It could be large as the condition number and in that case, the rate given in the paper is worse than SGD in terms of dependence on the condition number. Why the accelerated rate doesn’t have backward compatibility in this case? \n\n3- Your convergence proofs are based on fixed momentum and step size parameters. And due to that, you get a convergence to the neighborhood. Could you analyze in the decaying step size regime?   ", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper introduces a relaxation of the restrictive assumptions found in previous analyses by adopting common and mild assumptions. It explores three distinct settings and presents a comprehensive framework for their convenient analysis. The exposition of the paper is accessible and the proofs are clearly articulated.", "weaknesses": "One major limitation of the method is its lack of obliviousness to the mixing time. This paper addresses this weakness by achieving linear dependence on the mixing time; however, this is accomplished through a dependence on multilevel mini-batching, where the mini-batch sizes are contingent on the mixing time. This particular dependence was absent in some previous works, which may explain their quadratic dependence on the mixing time.\n\nAnother limitation is the comparison of convergence with existing results. While the paper relaxes certain restrictive assumptions, its convergence is limited to the neighborhood. In contrast, for example, [21] achieves asymptotic convergence to the minima. Moreover, when analyzing convergence with fixed step size or momentum parameters, the feasible parameter values in this work rely on σ and other unknown values to achieve an ε error.\n\nFinally, it would be beneficial to augment the paper with experimental results that validate the upper bound. Specifically, it would be valuable to observe the linear dependence on the mixing time and also include numerical results for the Variational Inequalities (VI) setting", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer __9UP4__ for the work and for the positive feedback! Next, we answer the issues raised.\n\n__W1__(mixing time):\n\nWe agree that the demand of knowing mixing time in advance is a significant limitation of the method. Estimating mixing time $\\tau$ from a single trajectory of the running Markov chain is known to be computationally hard problem, see e.g. [R1] and references therein. At the same time, methods, which share the same (optimal) linear scaling of the sample complexity w.r.t. the mixing time also share the same drawback as our method. In particular, it holds true for the EMD algorithm [R2], SGD-DD algorithm [R3], and usual SGD with Markovian data [R4]. The reviewer is right that the sample complexity of vanilla SGD is indeed quadratic in mixing time, provided that the learning rate is agnostic to $\\tau$. At the same time, the sample complexity rates  which are linear w.r.t. $\\tau$ for accelerated SGD do not automatically follow from the known techniques [R5] with rescaling step size by $\\tau$. Moreover, as stated in the main paper, the corresponding results of [R5] are incomplete.\n\nThe only work which is known to us, which is truly oblivious to the mixing time, is the paper [R6]. It also relies on the randomized batch size techniques, yet it allows to obtain the optimal sample complexity rates in a non-convex setting with AdaGrad learning rate. Thus it is an interesting direction for the future work to suggest a procedure that would allow to generalize the results of [R6] to accelerated SGD setting.    \n\n[R1] Wolfer et al. Estimating the mixing time of ergodic markov chains. \n\n[R2] Duchi et al. Ergodic mirror descent. \n\n[R3] Nagaraj et al. Least squares regression with markovian data: Fundamental limits and algorithms. \n\n[R4] Even. Stochastic gradient descent under Markovian sampling schemes.\n\n[R5] Doan et al. Convergence rates of accelerated markov gradient descent with applications in reinforcement learning. \n\n[R6] Dorfman et al. Adapting to mixing time in stochastic optimization with markovian data.\n\n__W2__ and __Q3__(stepsize): \n\nWe provide a sketch of the proof for the diminishing step size in our general reply. We allow for a decreasing step size, and the expression for the step depends only on $L$, $\\mu$, which seems more practical (as requested by the reviewer).  We added this reasoning to the text of the paper as a separate corollary of Theorem 1, and also made similar ones for VIs and the non-convex case. We agree with the reviewer that the results of some other papers are sometimes less demanding on the step selection, and we also added this to the text of the paper in the \"Comparison\" paragraphs at the end of Sections 2.1 and 2.3.\n\n__W3__(experiments): \n\nUnfortunately in a week to respond, we couldn't make the final version of the experiments, but we promise to add a small set of experiments to vary the theory in the new version of the paper (the final one, if the paper is accepted). We aim to illustrate the benefits of the proposed approaches on the policy evaluation problems on the discrete type environments solved within the TD ($\\lambda$)-type algorithms.\n\n__Q1__(typos):\n\nThank you very much for careful reading of the paper. We also made an additional proofreading of the supplemental materials to catch typos.\n\n__Q2__($\\delta$ discussion): \n\nThank you for your important comment. Indeed, it is possible that the quantity $\\delta^2$ scales as $L/\\mu$, and the resulting sample complexity bound scales as $(L/\\mu)^{3/2}$. At the same time, this drawback is shared by the classical results on learning under the so-called strong growth condition, see e.g. [R1]. As it is shown in [R2], the respective rates can be worse than the ones obtained by usual SGD even under the i.i.d. noise setting, see Appendix F.3 in [R2]. Under particular noise settings the acceleration over SGD might be not possible, see e.g. [R3]. \n\nMaking the analysis of accelerated SGD ‘backward compatible’ w.r.t. the rates of usual SGD requires to perform analysis in terms of additional problem-specific quantities, which are different from the ones coming from the assumptions A1-A4. For specific problem instances, such as online regression, there exist solutions e.g. in terms of stochastic condition number, see [R4,R2]. To the best of our knowledge, there is no recipe for such “backward compatible” bounds for the general minimization setup. We will add the underlying discussion and references to the revised version of the paper.\n\n[R1] Vaswani et al. Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron. \n\n[R2] Liu et al. Accelerating SGD with momentum for over-parameterized learning. \n\n[R3] Nagaraj et al. Least squares regression with Markovian data: Fundamental limits and algorithms. \n\n[R4] Prateek et al. Accelerating stochastic gradient descent.\n"}, {"review_id": "vgCICFS2bx", "reviewer": "Reviewer_RVr5", "summary": "The authors design and analyze first-order methods for stochastic minimization and stochastic variational inequalities (VIs), with Markovian noise. Typically in stochastic minimization, the target function is only accessible at point x, defined as $f(x)$, and its gradient $\\nabla f(x)$, through the sampling of a seed $z \\in Z$ using an oracle $F(x,z)$ and its gradient $\\nabla F(x,z)$. Under Markovian noise, the seed $z_t$ sampled at time $t$, is a state in a time-homogeneous Markov chain with a unique invariant distribution $\\pi$. Under this assumption, the goal is to minimize the expected value over the invariant distribution, that is $\\min_x f(x)=E_{z\\sim \\pi}[F(x,z)]$.\n\nThe authors make an assumption about the mixing time of the Markov chain. Beyond this, they make no other fundamental assumptions about the Markov chain. Moreover, for every point $x$ and seed $z$, and for some positive $\\sigma,\\delta$, the noisy gradient $\\nabla F(\\cdot,\\cdot)$ satisfies the following inequality:\n$$\n\\|\\nabla f(x) - \\nabla F(x,z) \\|^2 \\leq \\sigma^2 + \\delta^2 \\|\\nabla f(x)\\|^2,\n$$\n\nThe authors prove the following results:\n1. For strongly-convex minimization, they design and analyze an accelerated algorithm. This algorithm builds upon the accelerated stochastic gradient descent by Nesterov, and they further use randomized batch sizes and momentum. Additionally, they show that their convergence rate is tight in all parameters, except for $\\delta$. They also show that the dependence on $\\delta$ and the parameter that controls the Markov chain's mixing is necessary.\n2. The authors extend their results to non-convex minimization as well as to stochastic variational inequalities (VIs) with Markovian noise. They design and analyze algorithms for both settings by modifying existing algorithms, specifically, the Stochastic Gradient Descent and Stochastic Extra Gradient. They use the randomized batching technique, previously used in their algorithm for strongly-convex minimization.\n\n\n\nAfter the rebuttal, the authors effectively addressed my concerns about the real-world applications of their noise model. Furthermore, in my view, they have successfully addressed the main concerns raised by the other reviewers. Consequently, I maintained my original score.", "questions": "Could the authors provide more examples of stochastic minimization or stochastic VIs with Markovian noise?", "limitations": "I think that the authors have addressed the limitations of their work, by listing the necessary assumptions for their theorems. Moreover, I do not believe that this work will have negative societal impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The assumptions about the Markovian noise make sense especially in setting where the value of the noise sample is only influenced by factors exogenous of the picked action. Moreover, I think the paper is well-written, and the comparison with related work seems extensive. The authors seem to improve either in terms of assumptions, or in terms of convergence in all their settings. The results look reasonable, I checked the statements in the main body.", "weaknesses": "Given that this is a theory paper, the only minor weaknesses is that for the stochastic strongly-convex minimization, the bound is not tight for parameter $\\delta$, and the fact that they are missing lower bounds for the non-convex setting, as well as the stochastic variational inequality setting. I do not consider this a big weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer __RVr5__ for the work and for the positive feedback! Next, we answer the issues raised. \n\n__Q1__(examples of Markovian noise):\n\nThis is a very interesting and important question. Next, we give a number of examples which we will try to fit into the revised paper:\n\n_Coordinate._ Assumptions similar to A4 often arise in stochastic optimization. For example, in coordinate methods, when we use only part of coordinates instead of the full gradient. The existing literature assumes that we choose coordinates randomly and independently at each iteration, see e.g. [R1, R2]. Choosing the updated indices according to the Markovian dependency extends the possibilities of the existing methods. The idea of taking into account the history of the index updates seems natural. For example, if we used a coordinate in a previous iteration, it may be worth reducing the probability of its selection in the current iteration. Such family of methods is a very interesting area for future research.\n\n_Compression._ Compression is in some sense a generalization of the coordinate approach when we compress the transmitted information for the fastest communication between computing units in a distributed environment. Often compression operators utilize randomness [R3, R4]. As in the case of coordinate methods - the use of prehistory can be useful.\n\n_Mini-batching._ Assumption A4 often performs as well when we consider the gradient not over the whole sample, but over a batch. Here too, Markovian stochasticity can help, because a random choice of a batch number may lose to a non-random choice [R5, R6].\n \n_RL._ Reinforcement learning setting naturally falls into the Markovian stochasticity framework, since the gathered state-action sequence typically forms a Markov chain. The usual MDP setting falls naturally inside this paradigm. The Markovian noise here naturally comes into play from observing the triplets $(s_t,a_t,s_t'), t \\in \\mathbb{N}$, where $s_t$ is the current state of the environment, $a_t \\sim \\pi(\\cdot | s_t)$ is an action sampled on the $t$-th iteration and $s_t'$ is the next state of the environment, which is typically assumed to depend only on history only through $s_t, a_t$, that is, $s_t' \\sim P(\\cdot | s_t, a_t)$ for an appropriate Markov kernel $P$. Moreover, the analysis of non-tabular RL problems requires to deal with the general state-space Markov noise. Potential applications include the policy evaluation methods, such as the celebrated temporal difference (TD(0), TD($\\lambda$)) with or without functional approximation, see [R7]. We can apply the same methodology to the methods of policy gradient family, e.g. REINFORCE [R8], both in on-policy or off-policy settings. \n\n[R1] Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems\n\n[R2] Richtárik et al. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function\n\n[R3] Alistarh et al. QSGD: Communication-efficient SGD via gradient quantization and encoding\n\n[R4] Mishchenko et al. Distributed learning with compressed gradient differences\n\n[R5] Mishchenko et al. Random reshuffling: Simple analysis with vast improvements\n\n[R6] Koloskova et al. Shuffle SGD is Always Better than SGD: Improved Analysis of SGD with Arbitrary Data Orders\n\n[R7] Sutton. Learning to predict by the methods of temporal differences\n\n[R8] Sutton et al. Reinforcement learning: An introduction\n\n__W1__(bound is not tight for parameter $\\delta$):\n\nUnfortunately yes, that’s what we're thinking about right now. In this paper we are clearly reflecting that we have this problem at the moment. You might also find interesting the related discussion with Reviewer __9UP4__.\n\n__W1__(lower bounds for VIs and non-convex): \n\nLower bounds for variational inequalities can be obtained via lower bounds for saddle point problems, which are a special case of variational inequalities. The method for obtaining lower bounds for saddle point problems is reduced to obtaining estimates for the strongly convex minimization problem (see [R1, R2] for deterministic lower bounds), which we provide in our paper. Therefore, it is possible to obtain lower bounds for saddle point problems and hence for variational inequalities. For non-convex problems, lower bounds can also be obtained (see [R3, R4] for deterministic lower bounds).  But these bounds will have the same issue (dependence of $\\delta$ – “the bound is not tight for parameter $\\delta$”). Thus we think it is more important to focus on the lower bounds for the minimization problem and understand the dependence on $\\delta$ to the end, and then move on to other cases. To clarify the reviewer's question, we added a remark to the paper about how lower bounds for variational inequalities and nonconvex minimization can be obtained, in this remark we also noted that the bounds will have the same open question as lower bounds for strongly convex minimization.\n\n[R1] Zhang et al. On lower iteration complexity bounds for the saddle point problems\n\n[R2] Han et al. Lower complexity bounds of finite-sum optimization problems: The results and construction\n\n[R3] Carmon et al. Lower bounds for finding stationary points i\n\n[R4] Zhou et al. Lower bounds for smooth nonconvex finite-sum optimization."}, {"review_id": "x71kWm94V8", "reviewer": "Reviewer_8XQi", "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.\nAn 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.\nThe SGD algorithm is then studied in the smooth non-convex setting, to obtain typical rates for this algorithm under this type of noise assumption.\nFinally, the authors study variational inequalities under Markovian noise, by introducing Randomized Extra Gradient (with also their batchsize strategy).", "questions": "Questions related to the two major weaknesses/concerns above:\n\n1. 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.\n\n2. 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.\n\n3. 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 ?\n\n\nOverall, 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.", "limitations": "No such limitation noted.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "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.\n\nIn 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.\n\nAlthough 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.\n\n1) **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.\nTable 1 should also discuss this noise assumption.\n\n2) **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\n55 bounds which scale linearly with the mixing time of the underlying Markov chain are currently\n56 available only for non-convex minimization problems*: this assertion is false, since rates exists for convex problems, PL problems [23,28].\nThese 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer __8XQi__ for the work and for the positive feedback! Next, we answer the issues raised. \n\n__W1__ and __Q1__(noise):\n\nThank you! The noise assumptions are indeed an important part that needs to be covered. We analyze in detail the assumptions on noise from [28]. In Section 5.1, the author uses $\\bar \\sigma$, as the reviewer noted, but in addition to $\\bar \\sigma$, the estimates include $\\sigma_{\\max} = \\max_v \\sigma_v$, which is the analog of the supremum in the infinite case we consider. In particular, in Theorem 2, $\\Delta = \\sigma_{\\max}^2/L + f(x^0) - f(x^*)$. In general, the boundedness assumption w.r.t. $z$ comes alongside with the mixing assumption in terms of the total variation distance. Using the unbounded (w.r.t. $z$) noisy oracles $\\nabla_{x} F(x,z)$ requires another types of mixing, in particular, in terms of weighted Wassertein metrics, which makes the respective analysis more complicated. Moreover, in case of unbounded gradient oracles it might be complicated to obtain a direct counterpart of Lemma 1 and Lemma 2. For example, a counterparts of Lemma~1 would contain dependence upon initial condition $\\xi$ in the r.h.s., which makes the standard recursion argument for the $k$-th iteration error much more involved.\n\nThe authors in [28] also assume that $f_{\\xi}$ are $L$-smooth for all $\\xi$. In the finite sum setup considered in [28], such assumptions are reasonable. But $L$ for all $f_{\\xi}$ can be larger than $L$ for $f$. Moreover, if we pass to the more general case (infinite) that we consider, the assumptions raise questions. In particular, if $f (x, \\xi) = f(x) + \\xi \\cdot x^2 / 2$ and  $\\nabla_x f (x, \\xi) = \\nabla f(x) + \\xi x$. Let us check the $L$-smoothness of $f(\\cdot, \\xi)$ for all $\\xi$:\n$$\n||\\nabla f (x, \\xi) - \\nabla f (y, \\xi)||^2 = ||\\nabla f(x) - \\nabla f(y) + \\xi (x-y)||^2 \\leq 2 ||\\nabla f(x) - \\nabla f(y) ||^2 + 2\\xi^2|| x-y||^2 \\leq 2 (L_f^2 + \\xi^2) || x-y||^2.\n$$\nIn this case, $2L^2 = 2 \\sup_\\xi [L_f^2 + \\xi^2]$. Sections 5.2, 5.3 use noise in the optimal point, but additionally assume that all $f_{\\xi}$ are $\\mu$-strongly convex. This discussion shows that all assumptions must be clearly compared. In particular for [28], we added two rows to Table 1 as well as comments in footnote:\n\nMC SGD [28] (Sec. 5.1) (7) |  + | - | - | - | $O\\left( \\frac{\\tau (L(f(x^0) - f(x^*)) + \\sigma^2)}{\\varepsilon^2} + \\frac{\\tau (L(f(x^0) - f(x^*)) + \\sigma^2) \\bar \\sigma^2}{\\varepsilon^4}\\right)$ | $O \\left( \\frac{\\tau L}{\\mu} \\log \\frac{(f(x^0) - f(x^*))/\\mu + \\sigma^2/(\\mu L)}{\\varepsilon} + \\frac{\\tau \\bar \\sigma^2}{\\varepsilon \\mu^2}\\right)$\n\nMC SGD [28] (Sec. 5.2) (8) |  + | + | - | - | - | $O \\left( \\frac{L}{\\mu} \\log \\frac{||x^0 - x^* ||^2}{\\varepsilon} + \\frac{L \\tau \\sigma^2_*}{\\mu^3 \\varepsilon}\\right)$\n\n(7)  considers Markov noise with finite state space, uniformly bounds noise with $\\sigma$, but use $\\bar \\sigma^2$ as a variance of noise. Also the author additionally assumes that all stochastic realization $f_\\xi$ are $L$-smooth\n\n(8)  considers Markov noise with finite state space, $\\sigma_*$ bounds noise only in $x^*$, but additionally assumes that all stochastic realization $f_\\xi$ are $L$-smooth and $\\mu$-strongly convex\n\nIn \"Comparison\" paragraphs (Sections 2.1 and 2.3) we added a comparison of noise assumptions not only for our paper and [28], but also for others from Table 1. In particular, we note that in [86], [19], [20], [21] the authors use a uniform bound (supremum-like). But [23] deals with mean/expectation bound for the stochastic gradient.\n\n__W2__ and __Q2__(rate):\n\nWe revised the comparison part, Table 1 and the paragraphs at the end of the subsections. As mentioned in the response to the __Q1__, we added a comparison of assumptions, and at the request of Reviewer __9UP4__ we added a comparison of steps that are considered in different algorithms. Regarding points (a)-(c):\n \na) Our estimate for oracle complexity in the non-convex setting: $\\mathcal{\\tilde O} \\left( \\tau \\cdot \\left[\\frac{(1 + \\delta^2) L (f(x^0) - f^*)}{\\varepsilon^2}+ \\frac{L(f(x^0) - f^*)\\sigma^2}{ \\varepsilon^4} \\right] \\right)$. The estimate from [28]: $\\mathcal{O} \\left( \\frac{\\tau (L(f(x^0) - f(x^*)) + \\sigma^2)}{\\varepsilon^2} + \\frac{\\tau (L(f(x^0) - f(x^*)) + \\sigma^2) \\bar \\sigma^2}{\\varepsilon^4}\\right)$. \nIn particular, if $\\delta = 0$, we are mainly interested in the second term of both estimates. And here the answer to which estimate is better depends on whether it is smaller  $L(f(x^0) - f^*)\\sigma^2$ or $\\bar \\sigma^2 \\sigma^2$. In the other words, if  $L(f(x^0) - f^*) \\leq \\bar \\sigma^2$, then our estimate is better and vice versa. \n\nb) See the answer to the reviewer's previous question. We added two results from [28] to Table 1. We added to the comparison that an effect with independence of $\\tau$ was found in the paper [28], but the price of this effect is an additional assumption, as well as an additional factor of $L/\\mu$ in the estimate.\n\nc) We rewrote this sentence as follows: \"We note that the complexity bounds which scale linearly with the mixing time of the underlying Markov chain are currently available only for general convex and non-convex minimization problems. Namely, [23] has investigated a version of the ergodic mirror descent algorithm that yields optimal convergence rates for Lipschitz, general convex and nonconvex problems.\" We also added to lines 78-79: \"Meanwhile, (28) also achieved linear scaling by mixing time in the non-convex (general and PL) as well as the strongly convex cases.\"\n\n__Q3__:\n\nThe noise assumption in Theorem~$2$ is contained in Assumption A3 and is expressed in terms of the mixing time $\\tau$, which is naturally related to the hitting time from [28] in case of finite state-space Markov chains. While in such setup hitting time is a natural quantity, for general Markov noise the lower bounds in terms of the mixing time $\\tau$ are more suitable. We hope we have understood the question correctly."}]

Author rebuttal:
Reviewer __9UP4__ requested to make the analysis with stepsize, which is decreasing  and independent of a large set of unknown parameters. In part because of the size limitations of a personal reply to Reviewer, we put this in a general reply.

Here we give a sketch of how to make a decreasing step for the strongly convex case. The first detail is to make the parameters of Algorithm 1 depend on the iteration number $k$: $\gamma, p, \beta, \eta, M, B \to \gamma_k, p_k, \beta_k, \eta_k, M_k, B_k$, but the expressions for $\gamma_k, p_k, \beta_k, \eta_k, M_k, B_k$ from Theorem 1 are kept. We start the proof after line 643:
\begin{align}
    \mathbb{E_k} [||x^{k+1} - x^*||^2 &+ 2\gamma_k \eta^2_k (f(x_f^{k+1}) - f(x^*)) ]
\\\\
\leq&
    \left( 1 - \beta_k / 2\right) \left[|| x^k - x^*||^2 + 2\gamma_k \eta^2_k (f(x_f^k) - f(x^*)) \right]
    + 36 \beta^2_k \mu^{-2} \left(C_{1} \tau b^{-1} + (C_{1} + 1) \tau^2 b^{-2}\right) \sigma^2
\end{align}
With $\beta_k = \sqrt{\frac{4 p^2_k \mu \gamma_k}{3}}, ~~\eta_k = \sqrt{\frac{3}{\mu \gamma_k}}$, we get
\begin{align}
    \mathbb{E_k} [||x^{k+1} - x^*||^2 &+ \frac{6}{\mu} (f(x_f^{k+1}) - f(x^*))]
    \\\\
    \leq&
    \left( 1 - \sqrt{\frac{p_k^2 \mu \gamma_k}{3}} \right) \left[|| x^k - x^*||^2 + \frac{6}{\mu} (f(x_f^k) - f(x^*)) \right]
    + \frac{48 p_k^2 \gamma_k}{\mu} \left(C_{1} \tau b^{-1} + (C_{1} + 1) \tau^2 b^{-2}\right) \sigma^2.
\end{align}
Since $p_k = \left[1 + 2\left(  1 +  \gamma_k L \right) \left(1 + 4 \left[C_{1} \tau b^{-1} + (C_{1} + 1) \tau^2 b^{-2}\right] \delta^2 \right)\right]^{-1}$ and $\gamma_k \in (0; \frac{3}{4L})$, then $p_k \in [p_l; p_u]$, where $p_l, p_u \sim (1 + (1 + \tau b^{-1} + \tau b^{-2})\delta^2)$. Taking the full expectation, we have
\begin{align}
    \mathbb{E}[||x^{k+1} - x^*||^2 &+ \frac{6}{\mu} (f(x_f^{k+1}) - f(x^*))]
    \\\\
    \leq&
    \left( 1 - \sqrt{\frac{p_l^2 \mu \gamma_k}{3}} \right) \mathbb{E}\left[|| x^k - x^*||^2 + \frac{6}{\mu} (f(x_f^k) - f(x^*)) \right]
    + \frac{48 p_k^2 \gamma_k}{\mu} \left(C_{1} \tau b^{-1} + (C_{1} + 1) \tau^2 b^{-2}\right) \sigma^2.
\end{align}
With notation $r_{k} = \mathbb{E}\left[|| x^k - x^*||^2 + \frac{6}{\mu} (f(x^k_f) - f(x^*)) \right]$, $a = \sqrt{p^2_l \mu / 3}$, $\omega_k = \sqrt{\gamma_k}$ and $C = \frac{48 p_u^2}{\mu} \left(C_{1} \tau b^{-1} + (C_{1} + 1) \tau^2 b^{-2}\right) \sigma^2$, we obtain
\begin{align}
    r_{k+1}
    \leq
    \left( 1 - a \omega_k \right) r_{k} + \omega_k^2 C,
\end{align}
where $0 < \omega_k \leq d = \sqrt{3/(4L)}$. For this kind of recursion, we can use the results of Lemma 3 of [Stich. Unified optimal analysis of the (stochastic) gradient method]. In particular, we can choose $\gamma_k$ as follows
\begin{align*}
    \text{if } N \leq \frac{d}{a}, && \gamma_k = \frac{1}{d}
    \\\\
    \text{if } N > \frac{d}{a}, \text{ and } k < \lceil \frac{N}{2 }\rceil && \gamma_k = \frac{1}{d}
    \\\\
    \text{if } N > \frac{d}{a}, \text{ and } k \geq \lceil \frac{N}{2 }\rceil && \gamma_k = \frac{2}{a(k + \frac{2d}{a} + \lceil \frac{N}{2 }\rceil)}
\end{align*}
and get
$$
r_N = \mathcal{O}\left( \frac{d r_0}{a} \exp\left( - \frac{aN}{2d} \right) + \frac{C}{a^2 N}  \right).
$$
The step choice still depends on the horizon of iterations $N$. To fix it, we can the following restart procedure. We construct a sequence of the iteration budgets $N_t=2^t$ for $t\geq 0$. For each restart $t$ we set the stepsize $\gamma(N_t)$, run the algorithm for $N_t$ basic iterations and use the obtained point as a warm-start for the next restart. For simplicity, we can also use the same starting $x^0$ point for all the restarts. Let us now assume that the algorithm made $N$ iterations. This means that it made at least $T = \lfloor \log_2(N)\rfloor-1$ restarts. Since at the end of the last restart it made $N_T$ basic iterations with the stepsize $\gamma(N_T)$, we can guarantee that
$$
r_{N} = r_{N_T} = \mathcal{O}\left( \frac{d r_0}{a} \exp\left( - \frac{aN_T}{2d} \right) + \frac{C}{a^2 N_T}  \right).
$$
One can note that $N_T \sim N$, then
$$
r_{N} = r_{N_T} = \mathcal{O}\left( \frac{d r_0}{a} \exp\left( - \frac{aN}{2d} \right) + \frac{C}{a^2 N}  \right).
$$ 
This algorithm does not require to fix the number of basic steps $N$ in advance. If we want to have $\varepsilon$-solution in terms of $r_N$, then we have the following estimate on the number of iterations:
$$
N = \mathcal{O}\left( \frac{d}{a} \log \varepsilon^{-1} + \frac{C}{a^2 \varepsilon}\right) = \mathcal{O}\left( \left[1 + (1 + \tau b^{-1} + \tau^2 b^{-2} ) \delta^2\right] \sqrt{\frac{L}{\mu}} \log \varepsilon^{-1} + \frac{\sigma^2}{\mu^2 \varepsilon}\right).
$$
It remains to note that now $B_k = b \log_2 M_k = b \log_2 M_k \sim b \log_2 N \sim b \log_2 \varepsilon^{-1}$ - it gives additional log factor in the estimate for oracle complexity. This factor doesn't really affect the final bound.


Meta-review: This is a solid paper on learning with Markovian noise, focusing on convergence bounds that are linear in the Markov chain's mixing time, across a number of assumption settings (strong convexity, non-convexity, and VIs). Four expert reviewers all recommend acceptance, underscoring the result, the clarity of exposition and analysis, and the coverage of related work. Basic work on learning from non-iid noise is inherently interesting today and to the NeurIPS audience, and this paper extends knowledge on that front well.

The authors' interaction with the reviewers was productive and brought about some revisions that will improve the final paper further. Among these, I'll underscore the discussions clarifying the dependencies on parameters in the convergence bounds (e.g. the range of the delta parameter and the dependence on mini-batch sizes, from the threads with reviewers 9UP4 and RVr5, and the noise parameter from the exchange with reviewer 8XQi). The list of examples from discussion with reviewer RVr5 will also be a nice addition.

Two reviewers also brought up numerical experiments -- more as a suggestion than a necessary addition. The author indicated progress on this feedback that should help strengthen the final draft further as well.
Decision: Accept (poster)