Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling
Authors: Zhenyu Sun
Ermin Wei
Venue: ICML 2025 poster (2025)
Keywords: non-convex optimization
markov sampling
Primary area: optimization->stochastic

Abstract: Unlike its vanilla counterpart with i.i.d. samples, stochastic optimization with Markovian sampling allows the sampling scheme following a Markov chain. This problem encompasses various applications that range from asynchronous distributed optimization to reinforcement learning. In this work, we lower bound the sample complexity of finding $\epsilon$-approximate critical solutions for any first-order methods when sampling is Markovian. We show that for samples drawn from stationary Markov processes with countable state space, any algorithm that accesses smooth, non-convex functions through queries to a stochastic gradient oracle, requires at least $\Omega(\epsilon^{-4})$ samples. Moreover, for finite Markov chains, we show a $\Omega(\epsilon^{-2})$ lower bound and propose a new algorithm, called MaC-SAGE, that is proven to (nearly) match our lower bound.

Improved Lower Bounds for First-order
Stochastic Non-convex Optimization under Markov Sampling
Zhenyu Sun | Ermin Wei 12
Abstract
sequential dependencies, naturally modeled by Markov chains. For instance, in reinforcement learning, an agent typically collects data by interacting with an environment governed by a Markov decision process (MDP) (Sutton, 2018). leading to correlated samples. In online recommen- dation systems, user feedback often arrives sequentially in Markovian fashion, where each user's response depends their previous engagements (Afsar et al., 2022). In time- series analysis, measurements such sensor data or stock prices reflect underlying Markovian transitions (Hamilton, 2020; Esling & Agon, 2012). In the context of Bayesian inference, Markov chain Monte Carlo (MCMC) methods generate correlated samples approximate posterior distri- butions (Brooks, 1998; Nemeth & Fearnhead, 2021), which in turn are used for high-dimensional parameter estimation. Moreover, in the language models, transformers generate next-token predictions via a Markov chain (Makkuva et al., 2024). The meeteomee practical applications high- light the importance of generalizing analysis from the i.i.d. sampling to Markov sampling. Over the last few years, a growing body of literature has begun addressing questions involving Markov sampling given specific contexts, such as reinforcement learning (Bhandari et al., 2018 8; Zhang et al., 2021), distributed optimization (Sun et al., 2023; Even et al., 2024), and federated learning (Sun et al., 2024). This trig- gers the need for a unified theory advance that captures the intrinsic difficulty of dealing with Markovian dynamics.
Unlike its vanilla counterpart with i.i.d. samples, stochastic optimization with Markovian sampling allows the sampling scheme following a Markov chain. This problem encompasses various appli- cations that range from asynchronous distributed optimization to reinforcement learning. In this work, we lower bound the sample complexity of finding e-approximate critical solutions for any first-order methods when sampling Markovian. We show that for samples drawn from station- ary Markov processes with countable state space, any algorithm that accesses smooth, non-convex functions through queries to stochastic gradient oracle, requires at least 2)(=") samples. More- over, for finite Markov chains, we show a S2(E lower bound and propose new algorithm, called MaC-SAGE, that is proved to (nearly) match our lower bound.
1. Introduction
Stochastic optimization methods have become integral to a wide array of machine learning and statistical modeling tasks, with applications ranging from large-scale data analy- sis to reinforcement learning and control. Due to the pros- perity in deep learning and large models, first-order opti- mization methods, meaning only gradient information is leveraged for algorithm design, stand out due to their ad- vantages of implementability and computational efficiency (Achiam et al., 2023; Zhao et al., 2023). In many real- world scenarios, however, data do not arrive independently and identically distributed di....). Instead, they are gener- ated by underlying dynamical processes exhibiting temporal
Compared to the well-studied i.i.d. setting, analyses of first- order optimization methods under Markov sampling faced with novel and substantial challenges posed by corre- lated data. In the i.i.d. scenario, each data point is drawn independently from the same distribution and hence ren- ders unbiased estimate of stochastic gradient, which allows straightforward variance bounds and concentration inequal- ities be applied (Nemirovski al., 2009; Lan, 2012: Li & Liu, 2022). In contrast, when samples follow Markov chain, neighboring data observations are correlated, which complicates both the bias and variance characterizations of stochastic gradient estimates. In fact, due to the Markovian property, the gradient estimate is biased, prohibit direct gen- eralization of analyses from the i.i.d. case (Bhandari et al., 2018: Even, 2023; Roy et al., 2022: Sun al., 2023; Kim et al., 2022).
DDepartment of Electrical and Computer Engineering, North- western University, Evanston, IL. USA DDeparmeent of Indus- trial Engineering and Management Science, Northwestem Uni- versity, Evanston, IL, USA. Correspondence to: Zhenyu Sun wtw.://022222uuuuoeetteetoo
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Moreover, existing literature investigating stochastic opti- mization under Markov sampling mainly focuses de- riving various convergence and sample complexity up- per bounds for different algorithms. For example, re- cently (Even, 2023) provides the sample complexity upper bound for vanilla SGD under the Markov sampling scheme. (Dorfman & Levy, 2022) proposes sophisticated variant of SGD to guarantee robustness in hyperparameter selection. (Beznosikov et al., 2024) further establishes the convergence analysis for accelerating first-order methods and general- izes them to variational inequalities. However, the lower bound results are still lacking, especially when the objective function is non-convex, even they are fruitful for (strongly) convex case and for the i.i.d. case. Therefore, in this paper we aim bridge such research gap by establishing the lower bounds on sample complexities of first-order methods that solve stochastic non-convex optimization problems when data samples are Markovian. Our main contributions are summarized as follows:
non-convex objectives (Arjevani et al., 2023), respectively, and SGD is shown to have matched upper bounds for both cases (Foster et al., 2019; Ghadimi & Lan, 2013). For the Markovian sampling scheme, denoting as the mixing or hitting time of the Markov chain, (Beznosikov et al., 2024) shows a bound with (?(T log(E for strongly convex func- tions and (Duchi et al., 2012) provides a bound of ST(TE ²) for the convex case which proven to match the upper bound of SGD (Duchi et al., 2012). Recently, (Even, 2023) establishes a loose lower bound ((TE= for non-convex functions, while the best-known upper bound for this case is (TTE-)). Table I compares various lower bounds given different function and sampling assumptions.
2. Problem Formulation
Consider the general stochastic optimization problem,
min F(x) := [=-m(f(;;s))
(I)
where E S for S being the support, and II denotes some unknown underlying distribution. In this paper focus on the Markovian case, i.e., we assume that the samples { { form a sequence generated by some underlying Markov chain with its stationary distribution being IT. More- over we focus on countable-state Markov chains, meaning the state spaces are countable but may not be finite. Note that the Markovian setting reduces to the i.i.d. setting by decoupling the dependence across time.
We provide the algorithm-independeer sample com- plexity lower bound for any first-order methods of stochastic non-convex optimization problems, given data samples are generated by a sountable-state sta- tionary Markov chain. Our lower bound shows com- plexity with the order of cm4, which matches the upper bound of algorithm MAG provided in (Dorfman & Levy, 2022; Beznosikov et al., 2024).
We further restrict the case of finite-state Markov chains and show an 2-2 lower bound on the sample complexity. The bound is not contradictory to the bound for the countable-state case, as we are search under different function and oracle classes.
Since exactly solving (1) is NP-hard (Hillar & Lim, 2013), by restricting to first-order methods, we search for an e- approximate critical solution, which is widely adopted by literature (Carmon et al., 2020; Arjevani et al., 2023; Beznosikov et al., 2024) of F(z) defined in (I), In particu- lar, given differentiable function F Rdd - IR, our goal is to find some such that
We then propose a new algorithm, which is called MaC- SAGE, when the Markov chain is finite-state. The con- vergence analysis is provided for MaC-SAGE, which indicates nearly the same order of e -2, hence demon- strating the (near) min-max optimality of the proposed algorithm.
[VF(') SE
for any >> O.
2.1. An Example: Temporal-diiffrencc Learning
Sample complexity of stochastic optimization. The sam- ple complexity analysis of first-order stochastic optimization has thrived since last two decades. Lower bound results are undoubtedly crucial, as these bounds provide a fundamental limit on how efficiently any first-order algorithm can learn. Typically when full batch of samples are used for algorithm design, the lower bound of ((e 2) is established for smooth non-convex functions (Carmon et al., 2020) and algorithm Gradient Descent matches this lower bound (Ghadimi & Lan, 2013). When samples are assumed to be i.i.d., ((<==)
To illustrate the importance of our problem, we show that the temporal-diiference (TD) learning algorithm can be viewed special case that iteratively searching for an e-approximate critical solution of problem (I). Particularly, for the TD learning, we aim to (approximately) learn the value function defined by
Σ (r((t,,)41)) =
and ((c-5) 4) (which improves to 2(c=3) if the objective is assumed mean-square smooth (Arjevani et al., 2023)) lower bounds are provided for convex (Agarwal et al., 2009) and
where r(s,, 8(4 is the reward function and 8 ~ P(. $t) is drawn from some unknown stationary Markov chain P.
2

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Table Sample complexity lower bounds for stochastic optimization with smooth objectives. "full" means the objective function
directly used, corresponding deterministic case: for convex case, the sample complexity measure metric is F(x) F S c: for non-convex case, the complexity measure metric |/+()]] I e: represents the hitting/mixing time.
Reference
Convexity
Sampling
Lower bound
(Nesterov, 2013)
Strongly convex
full'
((log(e=1))
(Nesterov, 2013)
convex
full
((6-0.5)
(Carmon et al., 2020)
non-convex
full
(2(--2
(Agarwal al., 2009)
i.idd.
(2(c22
(Arjevani et al., 2023)
non-convex
i.idd.
((c=4)
(Beznosikov et al., 2024)
strongly convex
Markovian
Q( (oglog""
(Duchi et al., 2012)
convex
Markovian
M(TE=
(Even, 2023)
non-convex
Markovian
1(TE-1)
This work
non-convex
Markovian
M(T
Assuming that the value function can be parameterized by linear function, i.c.. there exists some l such that V*(ss o(s)T0", r Vs E S for the known feature mapping (--). then the TD-learning algorithm maintains an estimate 0 of 0 by the following update:
2.2. Function class
Partieularly, we consider all smooth functions in the follow- ing set:
F(A. FF: Rd R F(O) inf F(x) S A, [VF(x) V F < L| 5|| Vx, E Rd)
0.+1 = - (d(ss)) r((.: -
= 0g m:i(00iss
(2)
where sf is the sample drawn from s ~ P(. st).
where A 2 0 and L >> 0 are fixed parameters. The con- dition F(O) - inf, F(x) < on F(0) can be generalized to any initial value F(Fa). However, for zero-respecting algorithms (to be defined in Section 2.3), have To 0. In particular, we consider the case where the objective F is smooth and has bounded initial gap to the optimum.
g(0r; 81, 8() (d(s,)T - r(st, s() > 0, (st)) and th is the stepsize. Defining the augmented state (8,8') ESX S for which s' P(- s) and letting
f(0:3) //' g(0u u 8,); s') s') Ou)du
2.3. Algorithm class
with g(0; 8, defined in (2), we have V)(0;))
Our algorithm class is based the flow of (Arjevani et al., 2023). We consider the following first-order algorithms such that:
g(f: s, s'), implying that (2) is equivalent
0+t1 0g V (f,;
3
where { forms another Markov chain with augmented state space = S S. Shown by (Tsitsiklis & Van Roy, 1996; Bhandari al., 2018) (2) asymptotically converges to
the algorithm access an unknown E F(A, LT) by stochastic first-order oracle O;
the oracle O returns sequence of samples
the solution the following equation in expectation:
{si) (B can be time-dependent) generated by Markov chain and mapping
|B.-I...-~-(100000 8, = 0
Op(z, {st) [g(z; s
where II is the stationary distribution corresponding to the
Markov chain P. It then cquivalently yields by (3) that the TD-learning algorithm outputs c-approximation critical solution of some F for which
where g(z; s) ff(z;) is the stochastic gradient.
iteration the algorithm queries batch of M points
B =: VF()).
Ft = (5r,1 24. M,
3

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
for each batch query wi, O responses with
2.4. Countable-state Markov Chain
Or(n, =)) (Or( I (L,M)) MtM)
In this section, we are interested in any sampling schemes characterized by countable-state Markov chains, meaning that the state space S is discrete while |S| oo is allowed. Particularly, when the state space is finite, i.e., |S] < co, the case reduces to that of finite-state Markov chains, which is separately analyzed in Section 4.
where Zt,i is the sequence of sample drawn for Te, and 24 i= 21,
Then algorithm A consists of sequence of measurable map- pings {Ar to generate a sequence of iterates {2x Jio satisfying the following conditions:
The class of countable-state Markov chains is parameterized by the hitting time defined as follows.
Definition 2.1 (Hitting time). For any state w E S, define
the t + 1-th iterate is the output of A, when taking all previous oracle responses as input, i.c.,
Tw == inf (t 2 1 w}
A[[Oll Ae (Or(z)) A10Fl, 20). .a)......00. (r( 10 z)):
as the Markov chain firstly reaches state w. The hitting time That is defined by
2(+1
Algorithm A is zero-respecting, i.e., for any O and samples 20: 21.... with any M, it satisfies for any 2 - and any m E [M]
Thit
B(Tw 80 = v). E.SSSX
max
Intuitively, the hitting time measures the maximal number of steps for which any pair of states take to transit between each other.
(2)port(2:1,,m)) S
U kgL.m'E[AA]
support support(gk..e)) (5)
Then we consider the class of countable-state Markov chains for which the stationary distribution II exists and the hitting time Tha is upper bounded by parameter 2 1. We denote the chain by P. Specifically,
A(OFl where ga.m the stochastic gradient for Th.mm and support(z) = {i e [d] [z], & 0} for [z]] being the i-th coordinate of ar.
Ma(T) = {P That ST, lim pPPt=IT
IT, Vuu
(6)
We denote A (M) the class of all zero-respecting algo- rithms. It is worth noting that for any A E (M), A(OF 00. = 0 by definition.
where That is defined in Definition 2.1 and μPt represents the distribution of the chain after t-step transitions starting from the initial distribution μ.
We note that the mentinmento algorithm class is general, which captures many existing first-order algorithms. For example, the vanilla MC-SGD (Even, 2023)
2.5. Oracle Class
Recalling that the oracle O returns sequence of stochastic gradient evaluated each query, we place the following assumption.
Z1+1 = - St)
corresponds to M = B = 1, 2 O. For Randomized ExtraGradient (Beznosikov al., 2024), which maintains the update by
Assumption 2.2. For any x E R denoting II as the sta- tionary distribution of the Markov chain, (=-nllg(r;;)) FF(x)|2 < o² for some 0 o < 20, and E E, (2; s)] VF(x).
1412 prox,,, (xt (119(1188++111
Tt+1 prox,, (Ie+1/22 q/ur))
Basically, Assumption 2.2 requires 1) asymptotically unbi- ased gradient estimate when the Markov chain reaches its stationary distribution IT, i.e., Ee,-n[g(<;; 8t)] = V F()); and 2) bounded variance after convergence of the chain to its stationary distribution, i.e., E.-nnly(1;; 8) F> < o². This assumption becomes aligned with the bounded vari- ance assumption of stochastic first-order methods under i.i.d. sampling by further forcing independence across samples (Ghadimi & Lan, 2013; Allen-Zhu & Hazan, 2016).
where by generating Jr Geom(1/22
= u8 2 (m
if 2 K 0 otherwise
u 1-1
with
2
uf == 2-1
Σ g(ansTTH11)) T:41 = T, 1 1
Then, the oracle class, denoted by 0.(0? r), is that the stochastic gradient is sampled from a chain contained in M,(T) by (6) and such that Assumption 2.2 is satisfied.
one can clearly see that it fits in the case of M = and B 2

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
2.6. Sample Complexity Measure
to Ω
if of x LA, it matches the best- known upper bound for stationary Markov chains, which o LLA + z0 (A (Beznosikov et al., 2024).
IL Io
Our result of lower bound is established in terms of the sample complexity for finding an e-approximate critical solution of F. Let (((A) = Usst 2t be the collection of all samples utilized til time t by algorithm A.
4. Min-max Optimality for Finite Stationary Markov Chains
Concretely, the sample complexity measure is defined by
(M, A. L, o2,
In this section, we restrict on the case of finite-state station- ary Markov chains, where we further assume that the state space of stationary Markov chains is finite, i.e., |S] < co. Then, we can further show ((T sample complex- ity lower bound, which is followed by new proposed al- gorithm (MaC-SAGE) with (max Tmia (miix )²=²) sample complexity (Tmáz is the mixing time defined in Defintion B. indicating the nearly min-max optimality of our pro- posed algorithm.
sup sup 0E0,(02,7) L)) ArA
inf
} (7) inf (1T 21 B F Tr
When (M, A, L, .) is lower bounded by Nr, i.e.,
(M, A, L, 02, r) 2 Nr with Nr denoting all collected samples up to time T, it indicates that there exists some stationary Markov sampling process P with bounded hit- ting time and an oracle O E (o. such that for any A Agr (M) there exists F E L) for which E| F (000l >]| > E, where the expectation is taken over randomness in A and O. In other words, at least Nr num- ber of samples must be required to (possibly) achieve an e-approximate critical solution for any first-order algorithm.
We firstly define the class of finite-state Markov chains:
Ma,fi(t) (P) (PI |S| < oo).
(8)
Our subsequent analysis is established on the oracle class de- noted by (s, r), which requires the sampled stochas- tic gradients are drawn from a stationary Markov chain P E (M) and also satisfy bounded noise assumption given as follows:
3. Improved Lower Bound
Assumption 4.1. For any E Rd and any > 0, [g(2;;;) - VF(z)]2 I o² for > 0 and if s₁ ~ II, vt,
In this section, we show our main result on the lower bound of sample complexity for stochastic non-convex opti- mization under Markov sampling. The result is algorithm- independent, implying that all first-order methods that are zero-respecting take at least such samples to reach an e- approximate critical point of the non-convex objective func- tion.
B = FF))).
Moreover, given the finiteness of the state space, we con- sider objective functions are in the following class
F L) = FF: Rd - R F(O) inf F(z) < A
When the sampling process is characterized by countable- state stationary Markov chains, we show the following sam- ple complexity lower bound.
[V] V fy; e) s D| vll Vz, y R Ys S)
and note that F C F by further place smoothness point- wisely on every f); which is commonly used in liter- ature (Even, 2023). Accordingly, the sample complexity
Theorem 3.1. Considering the samples are generated by stationary Markov chains in Mo(T), there exist numerical constants C1, C2 > such that for any M, L,,, O,
measure is given by
(TO²
TO²
TO2 + d min (1102.2211))
No. A, L,
N L
sup (60,.,
inf (EF (EA
sup
Remark 3.2. Note that the extreme case - 1 corresponds to the i.i.d. sampling case. To see this, recalling the defini- tion of hitting time r = 1 indicates exactly one step is taken transiting from one state to any other, which then implies the samples are drawn exactly from the stationary distribution II and there is no time dependence across samples drawn at different time steps, hence reducing i.i.d. case. Thus, when o² > LA our lower bound result is aligned with the bound Ω (2(4)) ( AAA provided in (Arjevani et al., 2023). Moreover, noting that both lower bounds reduce
inf [(S((A)
E V A {
(10)
based on which we provide the following lower bound of sample complexity for finite-state stationary Markov chains: Theorem 4.2. Considering the samples are generated by finite-state Markov chains in Ms, there exist numeri- cal constants C3, C4 > O such that for any M, L, O, 0,
N N A, L, 0² = = min { (C30? ,c30))cLLA))
5

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Note that the results shown in Theorems 3.1 and 4.2 not contradictory, in the sense that S C Og by (T) C (T) F C F and Assumption 4.1 implying Assumption 2.2. Therefore, lower bounding N allows us to search for "hard" example in a broader space, compared to doing so for N In other words, the "hard" example in Og that realizes ((TT=*) 4) of Theorem 3. is more special than the one to re- alize 3) of Theorem 4.2 and is probably unrealizable when restricting on the class De Technically speaking, finding such an example for O₂ needs more sophisticated construction than for Oz.ft-
Algorithm I Markov-Chain Stochastic A Average Gradient
with Estimation (MaC-SAGE)
I: Input: Initialize To, 1/1 = On. 1-1 = Oa, Vi E [n], G-1 = Og, stepsizes {tt]
for = 0, ,,,.... , do
3: Sample state St from the underlying Markov
chain, i.e., f((3))) Si(-).
4: Update y/- (vi ................................ y2¹) as
t
vi = t+ Vl +
t 1==0
Vj [n]. (11)
A natural question following is then to ask that
5: Calculate
Is the lower bound in Theorem 4.2 tight enough?
Gt = G - Vi 1i + vi (i(z))
If we expect a positive answer to this question, an algo- rithm should be designed such that it has an orderly-same sample complexity upper bound, i.e., we need to show that 5 A, o², r) ()r In fact, propose new algorithm, called MaC-SAGE (summarized in Algo- rithm 1), which achieves a nearly-same order of re
6:
Update h4 = (hi, .., ,2,)) as
1 = M/_1 + 1=1= V (((+)) - hi-1), Vj E [m].
As now the state space S of the Markov chain is finite, to state our algorithm we simply set |S| = n and denote 8, E S as the state visited at time Further, we use 8t = i indi- cate the i-th state is visited at time f, hence correspondingly V f 8t) :- V fzxz). In Algorithm only one sample is drawn from the underlying Markov chain at each time iteration, which returns the corresponding stochastic gra- dient evaluated at the current query 2t. Simultaneously a vector ye is maintained to track the number of occurrences of each state, serving as role to reweigh the contribu- tion of the gradient given by each state. Then h is de- signed to dynamically track the latest gradient information provided by every state, which is then combined together with yr to incorporate corrected gradient into G.. Defining (t) == sup(l 1 S f, $1 = i). it is straightforward to observe that Algorithm 1 can be rewritten as follows:
7: Update I++1 = It - G/G
end for
F is (weighted) finite sum. Therefore, one may expect that if the estimator y/2 of II is asymptotically unbiased, meaning lim;-+00 Vt- = II and if the rate of y/ converging to II is no slower than the rate of SAG (which is O(T-0.5)) the sam- ple complexity would be O (up to some logrithmic factors). This intuitive result summarized in the following lemma (which is restated by Corollary B.4 in Appendix B).
Lemma 4.3. Suppose ye = .y...... vz) with y-1 = On is updated as (11) in Algorithm Then, we have for any t 1>1
E B 11|
T
where Tiin is the mixing time of the chain defined in Defini- tion B.I.
T141 = 34 - Ge
where
Formally, the convergence result of MaC-SAGE is presented in the following. The proof is shown in Appendix B.
1
Lazn Vie [n],
t [+1
Theorem 4.4. Let F F'(A, L) defined in (9) with L > O. Suppose Assumption 4.1 is satisfied. Then, for any finite-state stationary Markov chain contained in Ma,fi(T) defined in (8) with t > O, the trajectory {ae { generated by MaC-SAGE (Algorithm 1) satisfies
G. Σ of (Faatt))
which is similar to the classical variance-reduced algorithm SAG except for the weight vý- As matter of fact, Algorithm 1 is inspired by SAG (Schmidt et al., 2017) by further intro- ducing ye as an estimator of the stationary distribution II. Intuitively, when is known, SAG would effectively reduce the variance and thus speedup the convergence rate as now
TLA T
702 T
E
min VF(2))1 =
where 7 max(T, Tmix } where Tmizz denotes the mixing time of the chain defined by Definition B.I.
6

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
It is straightforward observe from Theorem 4.4 that the sample complexity of MaC-SAGE to achieve an approximate critical solution is Ó(FE implying its (near) optimality as it (nearly) matches the lower bound provided by Theorem 4.2.
that all its coordinates are nonzero, which then combines with Lemma 5.1 to guarantee the sample complexity lower bound ((T as shown by Theorem 4.2 by further setting d = d= 2) (since we have to guarantee O(Acad) = A).
To get the lower bound for countable-state Markov chains, we modify conditions (12) and (13) such that they hold prob- abilisticalll. This can be done by splitting u* and w* into two substates, respectively, where each substate is sampled with some probability q > O. Specifically. for instance if state v" is sampled there is with probability that condition (12) becomes true, similarly for the case w- is sampled. Figure 2 depicts a concrete construction of the chain. Thus, similar to the construction for the finite-state Markov chains we show the following result.
5. Proof Idea of the Lower Bounds
In this section we present the proof idea of how we obtain the sample complexity lower bounds for both finite-state and countable-state stationary Markov chains. We first clarify the proof sketch by focusing on the case where B = 1, ie., only one sample is drawn from the underlying Markov chain by the algorithm. Then, we generalize it to the case of B 121 which can also be time-dependent. Full proofs are presented in Appendix A.
Lemma 5.2. For any q E (0,1) and any zero- respecting algorithm A E A2r. there exist a countable- state stationary Markov chain contained in M.(T) and some F E F((OAdde)) L) with (x; sat- isfying (F) = "Esnlgg (1; and Ellg" (1; 8e) - V F=)I2 S O(o²2/q), Vt 2 0 such that for any 0 < 8 < 1, with probability at least - 6
The core technique inspired by (Arjevani et al., 2023) is to construct "hard" function F with [(;:) supported on each state of a Markov chain lying in the required class such that the gradient norm, [>) is small only if each coordinate of x has a large enough absolute value. We use the progress function to mathematically evaluate the largest coordinate whose absolute value is larger than some nonnegative scalar i.c.,
max maxprogo (2-10rl) < d. V 7(d - log 8 1)) ( 4,m
mE[M] $5t
4q
prog, (z) == ma 2 1 [[]]a]] > a}
In fact the constructive function F* in Lemma 5.2 coin- cides with the one in Lemma 5. which then implics that at least ((dd/q) iterations are needed to guarantee an c- approximate critical solution output by any algorithm and hence ((rd/q) samples (due to B 1). Finally setting d = 2(E=2) and q O(e²) concludes the lower bound Q((E=*) shown by Theorem 3.1.
where [z] represents the k-th coordinate of x. We set prog, (x) = if [[r]]] S a, Vk E [d]. Then the task of find- ing an e-approximate critical solution is equivalently trans- formed to finding solution whose coordinate progress is high. Formally it is stated by the following lemma.
Lemma 5.1. There exists some F' E ((
F(O(Ae2d) 2d), L) such that [V) > Ve > 0f
Note that the above proof derivations are established on the precondition when B = by which we are able to directly obtain the sample complexity bounds through the iteration complexity analysis, since the iteration complexity is the same the sample complexity. To generalize our results to B 2 1, we present the following result.
progo (z) < d.
Indicated by Lemma 5.1 ensuring (x)] S E requires all coordinates of r to be nonzero. Then for the case of finite- state Markov chains, we construct a chain with its hitting time upper bounded by 7 and lower bounded by !(7) and design g² (x; 8) such that Assumption 4.1 is satisfied and
Lemma 5.3. There exist a Markov chain in (6) (or (8) and some functions F",g" satisfying correspond- ing conditions in Lemma 5.2 (or Lemma 5.1) such that for any zero-respecting algorithm Azr with B Z 1, there is a zero-respecting algorithm Atr with B
i. progolo" (1; (1) S progo (x) +1 1 only if prog, (x) is even and s = v² ii. progo(g" (z; s)) I progo (x) +1 only if (1)) is odd and s = n²
(12)
1 for which the following holds: for any
2
0 if maxme[M]] max progo (r (# A'Oo)))) S k, then
(13)
maxme[M] paxgge (1.. A10rl) S k, 4O < k < d.
and otherwise progu (9" (x; s)) S (x)) Vs & (u" w²") ). where at least (((T) number of state transitions are taken for transiting from state v² to state w" and vice versa. See Fig- ure 1 for a visualization. With conditions (13) holding we obtain that at least ((Td) iterations (if only one sample is used every iteration, i.c., B = 1) are required for any al- gorithm (which is reso-respecting) to output a solution such
The above lemma indicates that can always find an al- gorithm that only draws one sample per iteration to achieve no worse progress in its update than other algorithms that access multiple samples per iteration. In other words, com- bining with Lemmas 5.1 and 5.2 yields that accessing multi- ple samples every iteration has no benefit on improving the
7

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
sample complexity for the algorithm, which hence implies the lower bounds that holds for B 1 also holds for B 2 1.
stochastic optimization. Mathematical Programming, 199 (1):165-214, 2023.
Beznosikov, A., Samsonov, S., Sheshukova, M., Gasnikov, A., Naumov, A., and Moulines, E. First order methods with markovian noise: from acceleration variational inequalities. Advances in Neural Information Processing Systems, 36, 2024.
6. Conclusion
In this paper, we study the sample complexity of general first-order stochastic non-convex optimization problems. Unlike the conventional i.i.d. sampling, we focus on the case where data samples and stochastic gradient estimates are generated by unknown Markov chain, which introduces additional data correlation and hence non-trivial analysis difficulties. Due to the lack of sample complexity lower bound results and the gap to the best-known upper bound, we provide an improved complexity lower bound with the order of e for Markov chains with countable states, which then matches the best-known upper bound. Moreover, we establish an e lower bound for finite-state Markov chains. Finally, we propose algorithm MaC-SAGE such that its sample complexity upper bound nearly matches our lower bound, implying its near min-max optimality and the tight- ness of the lower bound.
Bhandari, J., Russo, D., and Singal. R. A finite time anal- ysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Brooks, S. Markov chain monte carlo method and its appli- cation. Journal the royal statistical society: series D (the Statistician), 47(1):69-100 1998.
Carmon, Y., Duchi, J. C.,, Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Dorfman, R. and Levy, Y. Adapting to mixing time in stochastic optimization with markovian data. In Interna- tional Conference Machine Learning, pp. 5429-5446. PMLR, 2022.
Acknowledgements
This work is supported by NSF awards CNS-2030251, ECCS-2216970, and CMM1-2024774.
Duchi, J. C., Agarwal, A., Johansson, M., and Jordan, M. I. Ergodic mirror descent. SIAM Journal Optimization, 22(4):1549-1578 2012.
Impact Statement
Esling, P. and Agon, C. Time-series data mining. ACM
This paper presents work whose goal advance theoreti- cally understanding stochastic optimization. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Computing Surveys (CSUR), 45(1):1-34, 2012.
Even, M. Stochastic gradient descent under markovian sam-
pling schemes. In International Conference on Machine Learning, pp. 9412-9439, PMLR, 2023.
References
Even, M., Koloskova, A., and Massoulié, L. Asynchronous sgd on graphs: a unified framework for asynchronous decentralized and federated optimization. In International Conference on Artificial Intelligence and Statistics, pp. 64-72. PMLR, 2024.
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08877. 2023.
Afsar, M. M., Crump, T., and Far, B. Reinforcement learn- ing based recommender systems: A survey, ACM Com- puting Surveys, 55(7):1-38, 2022.
Foster, D. J., Sekhari, A., Shamir, O., Srebro, N., Sridha- ran, K., and Woodworth, B. The complexity making the gradient small in stochastic convex optimization. In Conference on Learning Theory, pp. 1319-1345. PMLR, 2019.
Agarwal, A., Wainwright, M. J., Bartlett, P., and Raviku- mar, P. Information-theoreei lower bounds on the oracle complexity convex optimization. Advances in Neural Information Processing Systems, 22, 2009.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-2366) 2013.
Allen-Zhu, Z. and Hazan, E. Variance reduction for faster non-convex optimization. International conference on machine learning, pp. 699-707. PMLR, 2016.
Hamilton, D. Time series analysis. Princeton university press, 2020.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro,
Hillar, C. J. and Lim, L.-H. Most tensor problems are np- hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
N., and Woodworth, B. Lower bounds for non-convex
8

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Kim, K., Oh, J., Gardner, J., Dieng, A. B., and Kim, H. Markov chain score ascent: A unifying framework of variational inference with markovian gradients. Advances in Neural Information Processing Systems, 35:34802- 34816, 2022.
Zhang, S., Zhang, Z., and Maguluri, S. T. Finite sample analysis of average-reward td learning and q-learning. Advances in Neural Information Processing Systems, 34: 1230-1242, 2021.
Zhao, W. X., Zhou, K., Li, J., Tang, T., Wang, X., Hou, Y.,
Lan, G. An optimal method for stochastic composite opti- mization. Mathematical Programming, 133(1):365-22) 2012.
Min, Y., Zhang, B., Zhang, J., Dong, Z.,, et al. A survey of large language models. arXiv preprint arXiv:2303. 18223, 2023.
Levin, D. A. and Peres, Y. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
Li, S. and Liu, High probability guarantees for noncon- vex stochastic gradient descent with heavy tails. In In- ternational Conference Machine Learning, pp. 12931- 12963. PMLR, 2022.
Makkuva, A. V., Bondaschi, M., Girish, A., Nagle, A., Jaggi, M., Kim, H., and Gastpar, M. Attention with markov: A framework for principled analysis of transformers via markov chains. arXiv preprint arXiv:2402.04466/ 2024.
Nemeth, C. and Fearnhead, P. Stochastic gradient markov chain monte carlo. Journal of the American Statistical Association, 116653))4333-500 2021.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach to stochastic pro- gramming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Nesterov, Y. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Roy, A., Balasubramanian, K., and Ghadimi, Constrained stochastic nonconvex optimization with state-dependent markov data. Advances in neural information processing systems, 33:27266-23270, 2022.
Schmidt, M.,
Le Roux, N., and Bach, F. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112 12,, 2017.
Sun, T., Li, D., and Wang. B. On the decentralized stochastic gradient descent with markov chain sampling. IEEE Transactions Signal Processing, 2023.
Sun, Z., Zhang, 7., Xu, 7.,, Joshi, G., Sharma, P., and Wei, E. Debiasing federated learning with correlated client participation. arXiv preprint arXiv:2410.01209 2024.
Sutton, R. S. Reinforcement learning: An introduction. A Bradford Book, 2018
Tsitsiklis, J. and Van Roy, B. Analysis of temporal- diffference learning with function approximation. Ad- vances in neural information processing systems, 1996.

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
A. Proofs of Lower bounds
A.I. Construction of Markoy chains
We construct Markov chains which are sinite-state contained in (T) and countable-statc contained in M2(T). We take the countable-state Markov chain case as an example. The construction for finite-state Markov chains are similar. Without loss of generality assume that even.
First, we pick countable-state Markov chain P' with state space S' (different from S) such that its hitting time is Är for some À (0, 1/2), which can be always done since ()( + 0. Then we choose two states s", w" that realizes the hitting time, i.c..
1 80 r) 2
BlTT 80 v), s.t. ,s,,"" E arg (v,w)
B(Tw
(s,w))S'xS
x
Next append number of additional states S \ S' into the chain P' to form new chain P such that the state space of P is S. Moreover the way we append additional states satisfies that 1) there is state v" E \ S' for which at least 1 steps are needed to transit between v² and 8"; 2) any state in S S' must transit to state s before transiting to other states in S'. One specific construction of the appended chain directed cyclic chain with self-loops, where a straightforward calculation gives its hitting time is 7/2. Thus we guarantee that the new constructed chain P has hitting time to be т. The following figure (Figure 1) illustrates a concrete example of the construction satisfying the bbove-mentiones requirements.
5'55
S
r steps
T steps
Figure 1. Construction of Markov chain P with bounded hitting time
A.2. Construction of the function F
Now construct "hard" function that is difficult for any first-order algorithm to search for the critical point. Specifically consider the following two functions
dd/2
h (x) (1)))((z))))+
+ (0(-(o))))(((1)laa)) ((x))))
(14)
[d/2] Σ
h2(x))
(w(-(x)22 100-(z)2-1)0((11pppp ( ((02))))))(
(15)
where
((u)=
exp (1 12u-113
and
0(u) = ve 1" e dt
-00
10

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
with R.
We denote the corresponding probability of state of the stationary distribution 11. Then, given the Markov chain constructed above, we know that at least 5 steps are required to take transiting from s* to w" and vice versa. Then, we construct function F' and f(=:s) such that
h1(2),
if e*
h2(z), 0,
if = w otherwise
(16)
and F(x) = TT-hi + Tw (2()). For any a and i 2 define zgi == ([z)1.... 0, .0.....,,) 0) as the truncated version by only keeping the first coordinates. We also set æço = z. Then we have the following properties of F.
Lemma A.1. Ler F (x) = n.- h1 (1)) + Tw 222 (x) for 1 h2 defined by (15),(15). Then we have the following:
(1). F(0) inf, F(x) I And for some constant 4
(2). [V)x())) & 23 and (2)]l) < 2 1,2.
(3). F(x) is 4-mmooth for some constant 4 > O.
(4). prog (x) < d. [VF()))]
(5). (ha( (pros (a) = Vh, (T ( (x)) i 1,2.
(6). If (r) (x) is odd, progo (v)( I progy (x)), progo(Vhzle) I prog (x) + 1. If progo(z) is even, progo Vhn (h)( S progy (2) + 1, progo (vh)(x)) S prog (2))
(7). If prog (z) is odd, Vh (x) Vh (F (a)). Vh2(2) Vha(#g11pma (2)) progy (2) is even, Vhi(z) Vhi (Fg14pmey(s) (z)). (1) W (z))
Proof. For Part (1), observing that (0)) and noting that 0 S vi))) 0, Φ(u) S V2Te,
F(x) 2 -b(1)(((z))) - Σ (())=)1))(1)))) 2 deV2re -doo
with Ao ev2ire, which completes its proof.
For Part (2), noting that 0 S (u) S v54e-T and 0 S d'(u)= I Ve, combining with the fact that for each = 1,2
Th (x) ((--=l)-1)0 -(t))))))))-((() 3 - ((((()))))) dr,
yields
Th, (x) S eve+ v54c V & 23 0zj
implying [V,,(>)] < 23 and |/Vh(=)]| s d3 vi = 1,2.
Parts (3) and (4) follow directly from (Carmon al., 2020). Parts (5)-(7) follow from the observation that
1
[h1(2) (hr((>]
[x] p O, ... 0), if [zzz] S
Vj 2 i+1
Vha(2) Vha [2/2, 0. 0). if 12 S 2' Vj2i+1.

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
A.3. Lower bound for finite-state Markov chains
According to Part (6) of Lemma A.I, the above constructive I' and f as (16) satisty the conditions (12) and (13), Consider the following F
LX 1
2/1 where À L
(x)))
F
(17)
Accordingly, we have
9 (x:=))==== Vf
LA f V 7,
(::)) 2cV (5:s)
We note that
VFF = 4 V
-
1
which implies that F" is L-smooth by Part (3) of Lemma A. and similarly we conclude f (c58) is L-smooth for any E S. Moreover, by Part (1) of Lemma A.1 we obtain that
2 F (0) inf (x) L (F(0) - inf F(x)) S
4 Ant
L d
and further we note for any 8 E S and any
[V;;;) - (+ & 2(1lh [Vhg(z)113) - 22-((2))))
where we use Part (2) of Lemma A.1, implying that
lig (z; - (F"(())) < 2d.
Therefore by setting
LA
o²
d= min
(18)
4/ Age
8 2
we guarantee that
F*(0) - inf inf F))) A 2 (F) (F S L|I - vll. Vr,y
(f - (y: s)]l S L yll, Vx,y
VF= 0²
which hence indicates that F* E FA, I.) and Assumption 4. 1 is satisfied.
Further combining with (16) and Part (6) of Lemma A.1 yields that conditions (12) and (13) hold for 1 and f*, where we use that progy (z) (x), Va. Therefore, for B 1,
max max progo ( (z,m MEM Is!
110 < d, VI < rd 2
1
(19)
For any algorithm A with B 2 1, we observe that by the construction of F* and f and the Markov chain P*, for any I. 2 0 and m E [M]. there exists an algorithm À with B = for which progo (x [[0m==))) < progo (= (1000)))) since multiple samples do not contribute to additional progress of æ (This also proves the finite-state case Lemma 5.3). Therefore, (19)
also holds for B 1, which implies that for any m E [M]
IV (10
L 7
VF
1 Sgd LA 2 2e, Vt S
where we use Part (4) of Lemma A.1 and note that prog (x) v progo (z:). Thus we conclude
1
min {
LA 27,
N (M,, I, 2 rd
Z z
An
23
completing the proof of Theorem 4.2.
12

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
A.4. Lower bound for countable-state Markov chains
Note that Assumption 2.2 for the countable-state case more general than Assumption 4.1 for the finite-case, which provides with more flexibility the construction of the "hard" example. In particular, of the Markov chain P in Section A.1 by further splitting states o" and w" into two substates, i..., v {ef, v2) and wn [ w such that conditioning on u" (or w²) is visited, the probability that of or (w?)) is sampled is (0, 1). We denote the modified construction as P Figure 2 visualizes our construction.
slightly modify the construction
5'55
S
steps
N
steps
Figure Construction of Markov chain p with splitting states
We define Ty- Toj + ang and Tw- = Aw; + Tw; as the marginal probabilities of virtual states o* and w². Then, we construct our and f for countable-states Markov chains as following: for each i-th coordinate of f
if E (0 s)) = (V)(
1++(i > prog (z))
s=at
q
1==w; 1
if E fwi, wi), [0(=; [v>2(>)] otherwise, [(x; 8) 0,
1 (1+ lft progy (x))
(20)
where P(s = of s E {ur, v11)) = P(s = wi E [wi, w(}) = q E (0,1) and let F(x) = -Tg (x) + n., (2()). Then we have the following lemma.
Lemma A.2. Considering stochastic gradient g(z; s) constructed as (20), the following statements hold:
(I), For s E {ui, v5, wf, wi}. with probability at least 1 q, progu (o(;; s)) S prog y (x) and g(æ;s) = (z))
for all x.
(2). For s & {Mi, ug, wi, wj}, with probability 1, progo st)) & prog (a) and g( 8t) g(x (e); 88 for all x.
(3). For any s, with probability 1, prog) < 1 p (x) and g(r; g( (1)3 for all
(4). Cawalg(x: (z).
Proof. We firstly show Part (3). Note that by (20) and Part (7) of Lemma A. for any x, s, st)]; = 0, > 1+ (z) in the sense that [Vh (x)]] [Vh2(z)], = 0, Vi > prog (z), which implies (2)))(((z;s)) / 11+progy (z). Moreover, by Part (7) of Lemma 1. defining x' 151+p=g (x) gives (h1 (hi(2') and (h2 V/2(z'). Thus, we
obtain g(;; s) g(,'; s) for any x, 8, implying Part (3).
13

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
For Part (I), we note that when i 2 1 1+prog 1 (Ir and E {og, w.). g(1; 8) (1)) (x) for 1, 2. which implies
(g s)) S progy (x). Vs {vg. w:) ). Further, according (5) of Lemma A.I, we have g( s) = (x) s) for {ug, w and all z. Since ((= 0)
9. hence Part (1) proved.
Part (2) holds trivially in the sense that g( st) 0 when & (vf, v2, wi, wš). Finally, Part (4) holds since 1[1,// {wi, w =
{vi 3 E[L./q
Also, we show in the following lemma that has bounded variance.
Lemma A.3. For F()) n. h1 (x) + Tw (1) and g defined as (20), then for any Markov chain with stationary distribution II, given any E R t 0 and any initial distribution of the chain,
1-9
Bllg(a; s.) VF(x)] S aid +
q
for some constant d1, 02 > O.
Proof. By Part (4) of Lemma A.2, know Eg-r(o(;; = (x)).
Denote i" 1 - prog (Ir). For any E {ui, v2, wi, w5). we have
g(x; s) (x)) = (0, (O....,, 0.
+ .- Vh (x) - n.- Vh2(a), if E (vf g( s) Fxx) = (O...., O, (z)); 11s + " Vh2(x) - n.. Vhi(s), if E u5]
/
When 1 1 is odd, from Part (6) of Lemma A.I we know that [x)] (2) 4- 232d, SE (5
Therefore.
l1g(x; s) v (x))] < 2//V/r
(1a(x;)) - <
( 1)2 + (x)(())) (\) < 3 (1< / 23 SE fwi, wř}
< 3|[
and
[1] s:) - V2 || < 4. 232d, when & (ui, 02 wf, w5}
where we use (2) of Lemma A.1. Combining the above three inequalities, it yields that when i" - 1 is odd, for any Markov chain, any x, 2 0 and any initial distribution of the chain,
[l st) VF(x)]] s and + 1-4
q
where a = 6 232 a2 3 23 and we use that BI(LL/q - 1)² s E (wi, wiHl = -1-00 -1-g)/4. The case when 1 is even can be derived similarly.
Then, we are ready to show Lemma 5.2. Again we first focus on the case of B 1 and then generalize B 2
Proof of Lemma 5.2. We construct F the same (17) with À 2/ and
LA
g" (z; 8) = 4
(.))
with s(x;s) defined as (20). Then by Lemma A.3, we have
El|g" (x; VF (x) < 4ajde² + 4az(1 -911-9)22 9)
Vt 2 0.
Then, define
B, = 1 (3x f:: progo (1330((((1;8))) = + prog (z))
14

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Note that under the construction of the Markov chain pa and 1a and g", for any zero-respecting algorithm A
B+ = O, Vk 1........ 2 conditioning on B, = 1.
That is to say within every 7 iterations B, can be I at most once. And Part (1) Lemma A.2 indicates that the probability of B, being is no greater than q. Let k(t) = maxme[[]] max progy (17, (r
A[O]r*
Then, the above implies that
k(t) - Σ B1
15
which then gives
P(K(1) 2 d) SP
Σ
Bi
2d
1st
P
exp
Σ
Bi
Rd
1st
S
EEe Eige
Bi]
"Ele D1sl
E(2/11 21]
e
(1 q + eq) [20/=]
S /2//r/o-d
where 2/8 are i.i.d. Bernoulli random variable with succeeding probability at most q and in the fourth inequality the fact that the number of B₁ that can possibly be 1 is most [2t/T] and they are independent if not forcing be zero. Therefore, we conclude that for any 5 E (0, 1) and y E (0, 1) with probability at least 8,
T(d log(1/8))
k(t) < d, Vt I
4g
which completes the proof of Lemma 5.2. Similarly we can use the same technique in the last section to show the countable-state case Lemma 5.3.
Now to show Theorem 3.1, setting
LA
d min
(21)
41, Age
8aje2
and
+
(22)
80262
yields that F* F(A, L) and Assumption 2.2 is satisfied. By Part (4) of Lemma A.1 and Lemma 5.2, choosing 8 1/2 renders that for any E [M] with probability at least 1/2,
) 2 2c, Vt < 7(d 1)
VF
A (xt
4q
which implies that
EI (1,100=11111 2|1 2,, AI 5 T(d - 1)
E
4q
Therefore, we conclude that
r(d-1)
T
T
N,
min (2 c2L
4q
by the selections of g as (21),(22) for some constants C1, 02 > 0.
15

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
B. Convergence Analysis of MaC-SAGE
In the following, we denote Ti the stationary probability according to state i. Definition B.1. Define lmiz(( (c) inf 1 drv(uP), IT) S e). Then Tiir Lmir (1/4) is the mixing time of the
chain.
Lemma B.2. We have the the following claims:
drv drv(uptt MT) I ddr((pP', IT).
For k 2 2, (2 S (k- 1) Finx.
Moreover,
Σ drv ,II) S co Timiss
VT 20
for some co > 0.
Proof. The first two claims are directly from (Levin & Peres, 2017).
To see the third claim, we note that
dup 1I) s
drv II)
buii (1+1))
Tuiiz
drv' II)
Σ
drv(uPl m²
1=0
k 01 10001mmma 1 (2-
I drv (H,, Tmii
(tmix (2 (k++l)
tmi 122
kom2
I dr MTmmi
1:2 Tmir
k==
S drv (H,, mlmmm + 2Tmix
which completes the proof with co drv T),
x) 2.
Theorem B.3. Let S be the state space of the Markov chain with |S| N. Consider any real-valued mapping S - R. and p is any initial distribution. Without particularly claiming, v(-) is vector. Define V [b(1)* "(.)...".!!..? N Then
1 T-1 111'-1111)
E
u(s))
V1
Σ
T
T
Σ v(s))
TEn
11Tv
max [1ti 111 11:0 + 2co max [|](ii] Tmie
Σ v(s)) / 2
TE v(s))
Σ
VV
TE
+ 3cp max [1 Tinr
T 1=
where (.) means the initial state so follows p: g(() u(1) T.VV
16

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Proof. We firstly show the first equality. Note that
Byg
1
v(8)) 0(5))
12'S -1²
pbV
-
VI'
T
0
T T-1
Σ
T
(pt
-
T
k=0
where we observe that μ² = 1.
Then we turn to show the second inequality. By definition, we have
2
TEn 1 Σ v(s))
11
Enllu(so)- - V12
2 T
+
Σ
(T - k)Enl(u(s0) - -
(23)
T
Moreover,
En((v(so) x (v)(((s))
~ー -
Σ mi(
Imm(i) Σipk 111 "")""""""""
$ Σ m Σ l|pt III" boll
max |1)) 111
Applying Lemma B.2 (23) yields
2 Σ ((s)) - 11 r=0
T-1 n'v) v) < max [1(1))| - 1|x + 2co max [[0(6)] Tmir
TEn
-
which completes the proof of the second inequality.
To obtain the third inequality, defining g()) u(i) II V we aim to bound
T-1
T-1 Σ g(sk)
T
p
T
Σ ((*c)
En
T
k=0
k=0
2
2
Σ k== 1=n+1
Σ
(,(o(s)))(s)))) - (=(((s))(ss)))
T
Note
(=)))))())))"""- -Ba((ss))((s)))) =
Σ (Ps TT)) )(( - 7))
Σ (ag(i)((Pk -11))) Σ (pl-k- -1IT- 11TT)) )).-)()))
< max | || 1
17

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
Thus,
T-1
T T-1 9 (sk)
21
T B
En
T
T
k=
0
2
11 (T"(PP 111" llo max [ + co max (1
Tmin
(pk 111 oo max (1)( + 2cd max (I)( Tmir
- co max (1)()))l Tmiz (2 + 1.
Combining all the above completes the proof.
Corollary B.4.
2
0 ToTmii
E
Σ (ot
(V)((((
-VV((())-VV(())))
VF(x)))
0
t
2
0 T
E
(u
TT)
0
t
Proof. For any t, setting v(t) [O.....
- -FF2z V2(22) 0) and noting [|o( S - < o²
completes the first result. Similarly setting v(t) [o...., 0, 1,0 0, 0) completes the second.
Theorem B.5, Considering MaC-SAGE (Algorithm 1) and supposing all conditions in Theorem 4.4 hold, then
E min [VF(E)))
=0 -
TLA
+6
0² max((T Tmmie
T
T
Proof. Using the smoothness of F,
L
F(1+11) F(x)) S (VF(1), x2)
| s2el?
2
~VV((a (VV((()).G)) G1) + Ly
|G111
2
= 2t (VF(I)) -G,
"t
[VF
2/11 -
2t
2
2
2
S 7t |VF(x)) G.
7t
7t
4
11.111
2
2
n S 1/(2L).
Note that by (t()) = supp 2
S f.
[VF - = <
Σ wi) n. V/
+2
Σ
v (V -(To)))) v/((z.))
2
Σ (0) क. ) (V. VF(()))
+2
Σ vi V fa ( vf((z))
mm
2
<
(v) क. (V. VF(2:))
+
y V. - f2(x111
i=1
Σ
(vt (V)(())))))))))))))))))))))))))) vF(x:))
+ Σ
w 2 | =z,l1
18

---

Lower Bounds of Stochastic Non-convex Optimization under Markov Sampling
where the third inequality follows the convexity of 12-norm by Ei=1 1t =1 T-smoothness of each fi- Further we have
of and
by definition; the last one follows
[-1
| - 2a,(1)1 2
Σ (t - (t))
(aa(())
Denoting : |E (vl (V) - vF(2))]| we obtain
Vl)))()))) - 2 + 21
Σ
v - (t)
[ml (t)
2 + L
3
n!!l?
(t)
when 7/ S 2L Further note that
T-1 ΣΣ
G
Σ
n
t= (0)
t=
where bt(t) in 1> t, St = i}. Thus, by letting AT F(xo) - -((TT we have
[FF(x)] < +
Σ
Σ
2t 1|1.11 +
ΣΣΣ
T.
(1 1).
t=
1=
:=1 1=
Moreover, since
T-1
T-1
E
wh? -- Fi]
G
That
Ttt 4L
||&11
for 7+ = ILima (1),;
S Torast
it yields
E
min [F
E
2 Jー1
+
> T-1
1=
ne
7t
==
Noting that according to Lemma A.5 of (Even, 2023)
T 1
TT- 7tt
T
nt
<
8L log(n)))
1=0
and by Corollary B.4
T- 1
T 1
02 Tmii log T LThil
7).
E
ntc
Σ E
= O
4LThat
A=
1=
Finally combining with the fact This I T we obtain
TLA T
0² 12maax T, Tmirn]
E
min
V
=0
+
T
19


Reviews:
[{"review_id": "PJfi1TaC7z", "reviewer": "Reviewer_UhUm", "summary": "This paper presents sample complexity lower bounds for stochastic gradient descent under a Markovian sampling assumption. In particular, there are two theorems in the paper showing lower bounds $\\Omega(\\epsilon^{-4})$ for Markov chains with countably infinite state space and $\\Omega(\\epsilon^{-2})$ for finite state space chains. The results also depend on a constat $\\tau$, which is an upper bound on the Markov chain's hitting time. \n\nIn addition, the paper presents a new algorithm called MaC-SAGE for finite state space chains whose sample complexity upper bound matches the lower bound in the paper.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**TC1**: After double-checking, we modified the theorem. Now the rate scales with $\\max ( \\tau_{mix},\\tau_{hit})$, but note MaC-SAGE remains optimal (up to constants).\n\n**TC2**: We clarify that we are **not** claiming $B_l$s are i.i.d. Bernoulli r.v., but we claim $z_i$s (see its definition in the following) are i.i.d. Bernoulli r.v. We explain it as follows: First, we construct a Markov chain in which there are two states $v^*, w^*$ such that $\\tau/2$ steps must be taken to commute each other. Then, we further introduce randomness in states $v^*, w^*$ to make sure that in the ideal case, when $\\tau/2$ steps are taken, the event “$prog_0(x)$ increases by one” happens with probability at most $q$. To do this, we split $v^*$ (and $w^*$) into two substates $v_1^*, v_2^*$ (and $w_1^*, w_2^*$) and construct the gradient by (20). By Lemma A.2, every $\\Omega(\\tau)$ steps there is at most one $B_l$ being one, with its succeeding probability (if it could) at most $q$. To see line 790, in the ideal case, at least $\\tau / 2$ steps are needed to increase $prog_0(x)$ by one and this becomes possibly true with probability at most $q$. That is to say, when $v^*$ or $w^*$ is visited, a coin is flipped where the flip’s result determines whether or not the event “$prog_0(x)$ increases by one” succeeds. And also the results of coin flips are independent across every time when $v^*$ or $w^*$ is visited. Therefore, $z_i$s record the results of coin flips, which are i.i.d.\n\n**TC3**: To highlight novelty: [Even’23] assumes uniform stationary distribution $\\pi$ ($\\pi_i = 1/n$), while [Powell & Lyu’24] require prior knowledge of $\\pi$. In contrast, MaC-SAGE requires no information about $\\pi$ and allows it to be non-uniform. We design $y_t$ to estimate $\\pi$ and address this challenge.\n\n**W1**: We explain our construction of Markov chains by referring to Figures 1,2. Actually, transition probabilities are not critical for proving lower bounds; only the chain's structure matters.\nIn the countable-state case (Figure 2), for the $S\\setminus S’$ part (orange circle), starting from $v^*$ (union of $v_1^*, v_2^*$, red dashed circle), the chain can move only in one direction until hitting $s^*$; similarly for $s^*$ to $v^*$. The number of states along each path between $v^*$ and $s^*$ is $\\tau/2$. The structure of the subchain in $S’$ (blue circle) is flexible—for example, it may be a complete graph. This construction ensures commuting between $v^*$ and $w^*$ requires at least $\\tau/2$ steps, while maintaining ergodicity of the chain.\n\nThe substates $v_1^*, v_2^*$ lie within $v^*$, and similarly for $w^*$. Figure 2 shows: 1) exactly one common parent state of $v_1^*, v_2^*$; 2) conditioned on the parent, transition to $v_1^*$ happens with probability $q$, and to $v_2^*$ with $1 - q$. It is equivalent that, upon reaching $v^*$, a coin is flipped to determine $v_1^*$ (w.p. $q$) or $v_2^*$ (w.p. $1-q$). The conditional probability below (20) defines this flip.\n\n**W2**: The constructed Markov chain and $f$ in (16) force any algorithm to iterate at least $\\Omega(\\tau)$ steps to make an increase in $prog_0(x)$. Then by Lemma 5.1, $\\Omega(\\tau d)$ samples are needed to make $\\nabla F$ small (see lines 360-380). To see boundedness of hitting time, we note by our construction, as long as the hitting time of the subchain supported on $S’$ (blue circle) is $O(\\tau)$, due to hitting time of the subchain in orange circle is $O(\\tau)$, the hitting time of the whole chain is $O(\\tau)$.\n\n**Q1**: We note our lower bounds rely on hitting time, which is a function of cardinality of (finite) state space. Due to space limit, please refer to responses to Q1&2 of Reviewer eLLJ about differences and reasons of separating Theorems 3.1&4.2.\n\n**Q2**: We acknowledge the limitation in finite hitting time assumption. We explain the idea how to construct a chain with bounded mixing time and hope to show it in future. First we design a cyclic-like subchain in orange circle with the number of states between $v^*$ and $s^*$ being $O(\\sqrt{\\tau})$. Second, we consider any subchain in blue circle whose mixing time is $O(\\tau)$. If we restrict on the orange or blue subchain, we have the mixing times of them are $O(\\tau)$. Then the mixing time of the composed chain is upper bounded by the larger mixing time of the orange or blue component. This is shown by [Madras&Randall’02] for reversible chains, while we conjecture it is also true for non-reversible chains.\n\n[1].Madras, Neal, and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability,2002.\n\n**Q3**: We acknowledge our proof techniques only suit stationary chains. But we note that many applications (e.g. TD learning, RL) belong to stationary case. And we highlight it is the first time improved lower bounds are provided for Markov sampling, with a new algorithm showing optimality of our bounds. Extending to non-stationary case is interesting and we hope to address it in future.", "claims_and_evidence": "See Theoritical Claims section.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I have read through the proofs of Theorems 3.1, 4.1, and 4.4. I have some concerns on the correctness of their argument for the main results. \n\n1. I think the convergence rate in Theorem 4.4 may depend on the mixing time as well. The last line of the convergence proof of MaC-SAGE on  page 19 asserts that $\\tau_{\\text{mix}} \\preceq \\tau_{\\text{hit}}$ citing [Levin & Peres, 2017]. My understanding is that its is not true in general that the mixing time can be bounded by the hitting time. For such a bound to hold, Theorem 10.22 in [Levin & Peres, 2017] requires reversibility of the Markov chain and some holding probability ($P(x, x) \\geq 1/2$) to ensure aperiodicity.\n\n2. The proof of Theorem 3.1 (lines 780-793), the authors seem to argue that the sum $\\sum_{l\\le t} B_{l}$ of the indicators $B_{l}$ that progress was made at time $l$ can be written as the sum of i.i.d. Bernoully random variable, only based on the fact that the there is at most one 1 between a time interval of length $\\tau/2$. I don't think this is true since $B_{l}$'s are defined according to the trajectory of a Markov chain. This part of the analysis must be fixed for me to recommend acceptance, since otherwise the validity of their key result, Thm. 3.1, the improved lower bound for Makovian first-order methods, is not justified. \n\n3. Also, I have a question on their new algorithm MaC-SAGE and the upper bound $O(\\tau/T)$ on the best-case expected gradient norm squared. The algorihtm seems to be a version of SAG (if not the same) in the Markovian setting, and [Even '23] already establishes a matching upper bound. Also the additional reference [Powell and Lyu '24] establishes a similar upper bound with random target time in place of the hitting time for regularized MISO ran on general recurrent data samples. This work also handles constrained nonconvex optimization. Compared to these existing results, I do not see a compelling reason to introduce a SAG-like algorithm if the only purpose is to obtain upper bound $O(\\tau/T)$. What additional advantage does the proposed algorithm and the accompanying result provide? Does the proposed algorithm show competitive performance against these algorithms?", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper's main contributions are lower bounds for SGD with Markovian sampling and non-convex objectives. The prior known lowerbound of [Even, 2023] was of the order $\\Omega(\\epsilon^{-1})$. This paper tightens this to $\\Omega(\\epsilon^{-4})$ for Markov chains on countably infinite state space and $\\Omega(\\epsilon^{-2})$ for finite state space. This is on par with similar results for i.i.d. sampling (e.g. [Arjevani et al. 2023]).", "essential_references_not_discussed": "The authors are encouraged to compare their results (on the upper bound) with the results in the following papers on stochastic optimization with dependent data: \n\n[1] William Powell, Hanbaek Lyu, \"Stochastic optimization with arbitrary recurrent data sampling\", ICML 2024\n\n[2] Ahmet Alacaoglu and Hanbaek Lyu, \"Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data\", ICML 2023\n\nEspecially, Thm. 3.8 in [1] seems to establish the matching upper bound $O(\\tau/T)$, where in fact \\tau is replaced by the random target time, a quantity that is generally smaller than the hitting time. Please also see my question on the upper bound in the theory section.", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. The paper presents two new lower-bounds for SGD with Markovian sampling which were not available in the literature. For the countable state space case, the dependence on $\\epsilon$ matches that of i.i.d. sampling. The dependence of the lower bound on $\\tau$ demonstrates the additional difficulty of the problem for poorly behaved Markov chains. The bounds for non-convex problems are much tighter than previous results. \n\n2. The version of SAG in Algorithm 1 has sample complexity matching the lower-bound for finite state chains. It also works by maintaining an approximation of the stationary measure which is interesting and new to my knowledge. \n\n**Weaknesses:**\n\n1. More detail in some of the proofs would also be helpful. The construction of the Markov chains for the lower bounds seems a somewhat vague. Especially the for the countably infinite case on page 13, a more explicit definition of the transition kernel would be helpful. Defining the transition to states $v_1^*$ and $w_1^*$ conditional on being in $\\{v_1^*, v_2^*\\}$ and $\\{w_1^*, w_2^*\\}$ as is done below (20) is a bit confusing to me.  \n\n2. I don't understand how the Markovian dependence of the data sampling is handled in the proofs. For instance, I am unsure how we reach the conclusion (19) on page 12 in the proof of Theorem 4.2. It i also not clear to me how the construction on page 10 guarantees the hitting time is bounded above by $\\tau$. See also the comments in the Theoretical claims section.", "other_comments_or_suggestions": "I am reserving my recommendation due to the (1) question/gap in the proof of lower bound and (2) novelty of the proposed algorithm and upper bound. I am willing to revisit my score if my concerns are successfully addressed.", "questions_for_authors": "1. There are two separate lower bounds for countably infinite and finite state space chains. However, the proofs dont seem to rely on the cardinality of the state space. It seems like both constructions can be done with a finite state space with size depending on $\\tau$. The key driver of the difference in the two theorems seems to be the strengthening of the bounded variance assumption. Why are the theorems separated based on infinite vs. finite state space?\n\n2. Also, for a countably infinite state space the assumption of bounded hitting time seems very strong. I think the stationary measure would have to be supported on a finite subset of $S$ for this to hold, which effectively reduces to the finite state space case. Can another assumption be used for countably infinite state space?\n\n3. The paper mentions a number of times that the Markov chains considered are assumed to be stationary. Why is this necessary?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "45zBvF2f2y", "reviewer": "Reviewer_eLLJ", "summary": "This paper studies the lower bound of sample complexity of general first-order algorithms for stochastic non-convex optimization problems under Markov sampling. They first show that for samples drawn from a stationary Markov chain with countable state space, the sample complexity is at least $\\Omega(\\epsilon^{-4})$. Moreover, for finite-state Markov chains, they show a $\\Omega(\\epsilon^{-2})$ lower bound of the sample complexity and propose a new algorithm that is proved to (nearly) match the lower bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1.  By using $:=$, we actually define $g(\\theta; s, s’) := (\\phi(s)^T \\theta - r(s, s’) - \\gamma \\phi(s’)^T \\theta)\\phi(s)$.\n\n2. We will fix it in the updated version.\n\n3. We thank the reviewer for the suggestion. By our notation, we mean $x_{t,i}$ being the $i$-th point at $t$-th iteration, whose dimension is $d$. We denote $x_t$ just for a collection of all updated points $x_{t,1},\\dots, x_{t,M}$. And when $M=1$, $x_t = x_{t,1}$. The reason we define such multiple points of query is to include a broader class of algorithms, e.g., momentum-based algorithms. We present the example of Randomized ExtraGradient in line 204, where $M=2$, meaning two points are maintained to update at every iteration. In the updated version, we will clarify further clarify it.\n\n4. In our setting, the support of a vector means the collection of all non-zero coordinates, i.e., $support(x)= \\\\{ i : x[i] \\ne 0, \\forall 1 \\le i \\le d \\\\}$.\n\n5. We apologize for the typo. $x_{t+1/2}$ should be used in the update of $x_{t+1}$ in line 206. We will fix it in the updated version.\n\n6. We apologize for the typo of missing $\\inf$. We will fix it in the updated version.\n\n7. We will fix it in the updated version.\n\n8. By the definition of $N_s^{\\epsilon}$, to ensure $N_s^{\\epsilon} \\ge N_T$ with $N_T$ being some constant, we only need to guarantee 1) the existence of an oracle (due to $\\sup$ over $O_s$); 2) the existence of a function (due to $\\sup$ over $\\mathcal{F}$); 3) for any algorithm $\\mathcal{A}$ (due to $\\inf$ over $\\mathbf{A}_{zr}$), 4) the smallest number of samples used by $\\mathcal{A}$ causes its output leading to the expectation of the gradient norm firstly lies below the level of $\\epsilon$. \n\n9. Denote $\\tilde{x}_T$ as the point which realizes the minimization, i.e., $\\tilde{x}_T \\in arg \\min E\\Vert \\nabla F(x_t) \\Vert^2$. Then, in order to force $\\mathbb{E}\\Vert \\tilde{x}_T \\Vert \\le \\epsilon$, it suffices to force $\\mathbb{E}\\Vert \\tilde{x}_T \\Vert^2 \\le \\epsilon^2$. Setting the bound on the right hand side of Theorem 4.4 gives that $T = \\tilde{O}(\\tau \\epsilon^{-2})$. Moreover, since only one sample is drawn at each iteration, it concludes the sample complexity of Algorithm 1 is $\\tilde{O}(\\tau \\epsilon^{-2})$.\n\n10. We appreciate the reviewer’s suggestion. We will provide more detailed explanations of the algorithm class in the updated version. Roughly speaking, the algorithm class we consider in the paper captures almost all popular first-order methods in literature. At every iteration, the algorithm is allowed to take all histories of previous samples and $ x_0,\\dots, x_t$ to generate $x_{t+1}$ following (5) which is satisfied by almost all first-order methods in literature. Note that (5) generalizes [Even’23] where $x_{t+1}$ is linearly spanned by previous points and sampled gradients.\n\n**Q1**. The core difference lies in how the stochastic gradient $g$ is constructed in the two settings. Assumption 2.2 for countable-state chains is weaker than Assumption 4.1 for the finite case (see lines 282–292). To address this, we design a countable-state Markov chain (Figure 2) by splitting $v^*, w^*$ into substates $v_1^*, v_2^*, w_1^*, w_2^*$ and define $g$ via (20). Unlike the finite case (Figure 1), where the transition from the parent of $v^*$ to $v^*$ happens with probability one, in the countable case, $v_1^*, v_2^*$ share the same parent, and the transition splits probabilistically: to $v_1^*$ with probability $q$, and to $v_2^*$ with $1-q$. Equivalently, the chain transitions to $v^*$, then flips a coin to select $v_1^*$ or $v_2^*$. This added randomness, combined with (20), makes the event “$prog_0(x)$ increases by one” succeed with probability $q$ (as shown in Lemma 5.2). As a result, more samples are needed—compared to the finite case—to ensure $prog_0(x) = d$ and hence $\\Vert \\nabla F(x) \\Vert$ is sufficiently small. See lines 333–359 for details.\n\n**Q2**. The main reason of considering different oracles is to bridge the gap between our lower bounds and upper bounds for different settings. Essentially we are searching for tight bounds under different settings. While we could get $\\epsilon^{-4}$ for the finite case under a more general Assumption 2.2, we aim to prove that an improved bound $\\epsilon^{-2}$ is tight under a more specific/easier setting for the finite state space case. This is both motivated by practical consideration and also the existing upper bounds. Then we propose a new algorithm such that the sample complexity can be improved to $\\epsilon^{-2}$ under such a stricter but practical Markov-chain class further with the matching lower bound.\n\n**Q3**. Please refer to Q1.\n\n**Q4**. We note the hitting time is a function of the number of states which is different for different Markov chains. Therefore, the convergence rate of MaC-SAGE is affected case by case.", "claims_and_evidence": "The claims are supported by clear and convincing evidence. The lower bounds are derived via carefully constructed functions and Markov chains, while the algorithm’s analysis rigorously addresses Markovian sampling.", "methods_and_evaluation_criteria": "The construction of the hard instance is standard in the literature. The design of the near-optimal algorithm seems new and interesting to me.", "theoretical_claims": "I did not check the proof line by line, but the technique is standard.", "experimental_designs_or_analyses": "There is no experiment.", "relation_to_broader_scientific_literature": "As stated in the paper, the previous lower bound under this setting is $\\mathcal{\\Omega}(\\tau \\epsilon^{-1})$. This paper improves it to  $\\mathcal{\\Omega}(\\tau \\epsilon^{-4})$. I think it is a huge improvement and helps us understand the boundary of the first-order algorithms.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "1. Page 3, Left, Equation (2): It is better to explicitly give the definition of $g(\\cdot)$\n2. Page 3, Left, line 151: Is it $\\bar{s}_{t}$?\n3. Page 3, Right, line 163: It is better to give the dimension of $x_{t, i}$ and $x_t$\n4. Page 4, Left, line 185: What is support?\n5. Page 4, Left, line 205: Is $x_{t+1/2}$ used in the iteration?\n6. Page 4, Definition 2: It seems to me $\\tau_w$ should be defined with $\\inf$\n7. Page 5, Equation (7): Should it be $|S_T(\\mathcal{A})|$?\n8. Page 5: Line 239: Can you explain more on When $N^{\\epsilon}_{s}(M, \\Delta, L, \\sigma^2, \\tau)$ is lower bounded by $N$, \n\ni.e., $N_{s}(M, \\Delta, L, \\sigma^2, \\tau) \\geq N_T$ \n\n9. Why the sample complexity of Algorithm 1 is $O(\\tau \\epsilon^{-2})$?\n10. The introduction of the algorithm class can have more explanation.", "questions_for_authors": "1. In terms of the sample complexity gap, what is the core difference in analysis between the infinite-state Markov chain and finite-state Markov chain?\n2. Why consider different oracles in the infinite-state Markov chain and finite-state Markov chain?\n3. What is the key difference when constructing the hard instance under this Markov sample scheme?\n4. How does the number of states affect the performance of MaC-SAGE？", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dOA3QpYKpa", "reviewer": "Reviewer_VvVo", "summary": "The paper proves a lower complexity bound of $ O(\\tau_{mix} \\varepsilon^{-4}) $ for smooth, non-convex stochastic optimization under Markovian noise with countable states. For finite state space, a lower complexity bound  $ O( \\varepsilon^{-2}) $ is also given, and a proposed method to match the lower bound to logarithmic factors is proposed.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for positive and encouraging comments on our paper. In our updated version, we will promote the writing to make it clearer and easier to follow for the readers.\n\n**For zero-respecting algorithms we consider in the paper**, we note that zero-respecting algorithms require the initial point $x_0$ to be zero, i.e., $x_0 = 0$ due to (5). That is to say random initialization is not allowed for zero-respecting algorithms. However, it is worth noting that such limitation on the initialization is also seen in lower bound analysis of literature [Even’23, Arjevani et al’23, Beznosikov et al’24, Duchi et al’12] and it does not affect the convergence result of the algorithm. We are willing to generalize our results to randomized algorithms in the future.\n\n**About extension to bounded gradient assumption**: We appreciate the reviewer’s suggestion. Extension to bounded gradient case is interesting and we hope to address it in the future. Also we would like to note that smoothness is a common assumption for convergence analysis in optimization literature [Ghadimi and Lan’13, Even’23, Roy et al’22, Dorfman and Levy’22]. Therefore, our results are applicable for optimization problems under standard assumptions.", "claims_and_evidence": "The analysis well supports the claims. The lower bound improves from the previous result of Even 2023 under the same setup. The lower bound is also tight, in the sense of matching the upper bound in prior works.", "methods_and_evaluation_criteria": "No numerical studies are presented.", "theoretical_claims": "The proof is not checked carefully. The proof seems to follow similar works in optimization and lower complexity bound analysis.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The works add an important piece for stochastic optimization under the non-convex setting.", "essential_references_not_discussed": "Related works are relatively complete.", "other_strengths_and_weaknesses": "Overall, I think the paper makes good contributions to the broad stochastic optimization field, where many ML methods operate under Markov chains. The results are presented clearly, and the proofs are intuitive to understand. \nThe consideration of finite state space is a good addition to the results, and the proposed algorithm, although similar to the classical variance reduced method for non-convex problems, yields strong convergence rate in the markovian noise setting.\n\nHowever, the writing might not be friendly enough. For example, I am a little confused about the definition of zero-respecting algorithms in section 2.3. It seems this algorithm class is general, but what are the exceptions? \n\nAdditionally, this work focus on smooth functions, I wonder what's the results with more generic assumption, i.e., bounded gradients?", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0veLrCSHdC", "reviewer": "Reviewer_dSkt", "summary": "This paper studies the sample complexity of stochastic optimization for smooth, non-convex functions when the noise variables form a Markov chain instead of being i.i.d. The authors obtain a lower bound of $\\Omega{\\tau\\epsilon^{-4}}$ for stationary Markov processes with a countable state space, where $\\tau$ is the hitting time of the Markov chain, and a lower bound of  $\\Omega{\\tau\\epsilon^{-2}}$ for finite-state Markov chains, where $\\tau$ is the hitting time of the Markov chain. A new algorithm, MaC-SAGE, which nearly matches the lower bound in case of finite-state Markov chains. The work provides theoretical complexity bounds and an efficient algorithm for optimization with Markovian sampling.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to \"Theoretical Claims\"\n\n1. The proof of Theorem B.3: We think the proof of Theorem B.3 is correct and we will add details in the updated version. We detailedly explain how line 912 is derived as follows:\n\nFirst, we derive line 907 from line 906:\nDenoting $v_{max} := \\max_i \\Vert v(i) \\Vert_{\\infty}$, we have\n$$\n\\begin{aligned}\n\\sum_i \\pi_i \\Vert v(i) \\Vert_{\\infty} \\sum_j \\vert P^k - \\mathbf{1}\\Pi^T\\vert_{i,j}  \\Vert v(j) \\Vert_{\\infty}  \n&\\le \\sum_i \\pi_i \\Vert v(i) \\Vert_{\\infty} \\sum_j \\vert P^k - \\mathbf{1}\\Pi^T\\vert_{i,j}  \\max_{j} \\Vert v(j) \\Vert_{\\infty} \\\\\n&\\le \\sum_i \\pi_i \\max_i \\Vert v(i) \\Vert_{\\infty} \\sum_j \\vert P^k - \\mathbf{1}\\Pi^T\\vert_{i,j}  \\max_j \\Vert v(j) \\Vert_{\\infty} \\\\\n&= v_{\\max}^2 \\sum_i \\pi_i \\sum_j \\vert P^k - \\mathbf{1}\\Pi^T\\vert_{i,j} .\n\\end{aligned}\n$$\nwhere due to display issue, we use $\\vert A \\vert_{i,j}$ to denote $|a_{ij}|$.\n\n\nSince by definition of the matrix infinity norm (i.e., for matrix $A$, $\\Vert A \\Vert_{\\infty} := \\max_i \\sum_j |a_{ij}|$), for any $i$, $\\sum_j  | P - \\mathbf{1}\\Pi^T \\mid_{i,j}  \\le \\Vert P - 1\\Pi^T \\Vert_{\\infty}$, then we conclude line 907 by further noting $v_{max}^2 = \\max_i \\Vert v(i) \\Vert_{\\infty}^2$ and $\\sum_i \\pi_i = 1$.\n\nThen, note that for finite-state case, since Lemma B.2 holds for any initial distribution $\\mu$, setting $\\mu = 1_{s_0 = i}$, meaning the chain starts from state $i$ with probability one, it yields that \n$$\n\t\\sum_{k=0}^T \\max_i d_{TV}(P^k(\\cdot \\mid s_0 = i), \\Pi) \\le c_0 \\tau_{mix}.\n$$\nMoreover, by definition of total variation distance, i.e., $d_{TV}(p,q) := (1/2) \\sum_{z}|p(z) - q(z)|$, we conclude $\\Vert P^k - \\mathbf{1}\\Pi^T \\Vert_{\\infty} = 2 \\max_{i} d_{TV}(P^k(\\cdot \\mid s_0=i), \\Pi)$. Combining all these facts gives the second term of line 912. \n\nTo see the first term of line 912, which is the bound for the first term in (23), we simply set $k=0$ for line 900, which hence is bounded by $\\max_i \\Vert v(i) \\Vert_{\\infty}^2 \\Vert I - \\mathbf{1}\\Pi^T \\Vert_{\\infty}$.\n\n2. Typo in Corollary B.4: We apologize for that typo. The second bound in Corollary B.4 should not depend on $\\sigma$ and we will fix it in the updated version.\n\n\n##  Response to \"Other Strengths And Weaknesses\"\n\n**About the cardinality of finite state space on the results**: We note that the hitting time in Theorem 4.2 is usually a function of the cardinality of the state space in practice. That is to say the number of states affects the sample complexity by means of the hitting time captured in our theorem. How the cardinality relates to hitting time varies case by case.\n\n## Response to \"Other Comments Or Suggestions\"\n\n1. Typo on line 595: We apologize for the typo. We will fix it in the updated version.\n\n2. Notation of $g$: In the paper, we consistently define $g(x;s) = \\nabla f(x;s)$, i.e., $g$ is the first-order stochastic gradient sampling from the Markov chain. In the updated version, we will clarify such notations for easy understanding.\n\n3. Notation in Lemma A.2: We will drop all subscripts of $t$ in the updated version.\n\n4. About Assumption 4.1: There is no expectation on the norm, saying the bound is assumed to hold almost surely. That also distinguishes the construction for the finite-state case from the countable-state case. Please refer to lines 282-292 for detailed discussion.\n\n## Response to \"Questions for Authors\"\n\nWe note that in our construction, the cardinality of the finite Markov chain is $\\Omega(\\tau)$ due to the fact that there are at least $\\tau$ states between $v^*$ and $s^*$ (see Figure 1). Since the hitting time of the chain is usually a function of the cardinality, our bound hence implicitly depends on the state space cardinality.", "claims_and_evidence": "All statements and theorems given by the authors in the main text are proved, the proofs are given in the appendix.", "methods_and_evaluation_criteria": "The analysis of sample complexity in first-order stochastic optimization is well-established. The authors provide an algorithm-independent lower bound on sample complexity for non-convex functions with markovian noise and, in the case of a finite-state Markov chain, propose an algorithm that nearly matches this bound.", "theoretical_claims": "1. In the proof of Theorem B.3., the transition from \n$$\n\\sum_{k=1}^{T-1}\\|P-e\\Pi^T\\|_{\\infty} \\leq c_0 \\tau_{mix}\n$$\nis not explained in the second and third claims (see line 912). To me it should be an additional factor $|S|$ coming from \n$$\n\\sum_{k=1}^{T-1} \\|P^{k}- \\1 \\Pi^T\\|_{\\infty},\n$$\nsince the supremum might be attained on different rows of $P^{k}$ for different indices $k$. If this is not the case, please provide nore detailed derivation. Otherwise I do not see how this fact directly follows Lemma B.2.\n\n2. In Corollary B.4. the second inequality has a dependence on $\\sigma$, but $\\||v_i\\|_{\\infty} = 1$ in this case.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This paper builds on existing research in stochastic optimization by strengthening lower bounds for nonconvex optimization under Markov sampling, improving on the work of [2] by establishing a tighter $\\Omega(\\tau \\varepsilon^{-4})$ bound that matches the upper bound obtained in [1]. This extends previous results for independent noise [3] to a more complex Markovian setting where dependencies between samples affect the convergence rate. In addition, the authors refine the lower bound for a finite Markov chain $\\Omega(\\tau \\varepsilon^{-2})$ and propose a new MaC-SAGE algorithm that tags the obtained lower bound.\n\n[1] Dorfman, Ron, and Kfir Yehuda Levy. \"Adapting to mixing time in stochastic optimization with markovian data.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Even, Mathieu. \"Stochastic gradient descent under Markovian sampling schemes.\" International Conference on Machine Learning. PMLR, 2023.\n\n[3] Arjevani, Yossi, et al. \"Lower bounds for non-convex stochastic optimization.\" Mathematical Programming 199.1 (2023): 165-214.", "essential_references_not_discussed": "No essential references are missed.", "other_strengths_and_weaknesses": "The provides an improvement in lower bounds for non-convex optimization under Markovian sampling. Its originality lies in tightening existing bounds and proposing the MaC-SAGE algorithm, which nearly matches the new lower bound for finite-state space Markov chain. However, the paper considers only discrete Markov noise, while in [1] an upper bound is given for non-convex functions and an arbitrary ergodic Markov chain admitting a stationary distribution. Also in [2] the uniformly ergodic Markov noise is considered and the lower bound is given for strongly convex functions. At the same time, is not clear to me, where exactly the current construction relies on the fact that we are working with a finite state space in the proofs of Section 4.2. In particular, factors relating $\\tau_{mix}$ and $\\tau_{hit}$ might depend on the size of the space $|S|$.\n\n[1] Arjevani, Yossi, et al. \"Lower bounds for non-convex stochastic optimization.\" Mathematical Programming 199.1 (2023): 165-214.\n\n[2] Beznosikov, Aleksandr, et al. \"First order methods with markovian noise: from acceleration to variational inequalities.\" Advances in Neural Information Processing Systems 36 (2023): 44820-44835.", "other_comments_or_suggestions": "The paper contains a few typos:\n\n1. Line 595-596: should be $\\|h_i(x)\\|_{\\infty}$ in the first norm. \n\n2. In Section 2.3 it is written that $g(x;s) := \\nabla f(x,s)$ and then the authors use one or the other notation in the text, e.g., in Assumption 4.1 or in formula (20) in the supplementary material. Different notations for the same object make it difficult to understand the text.\n\n3. In Lemma A.2, somewhere there is an index $t$ in $s$ and somewhere there is not;\n\n4. In Assumption 4.1 it is written that $\\|g(x,s_t) - \\nabla F(x)\\| \\leq \\sigma^2$. Is it an expectation missing or we rely on an almost sure bound here?", "questions_for_authors": "Where exactly the current construction relies on the fact that we are working with a finite state space in the proofs of Theorem 4.2? If there are some hidden constants depending on the cardinality of the space where the Markov chain runs, I suggest to trace them explicitly and provide them in the statement.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9EwYc7cuSW", "reviewer": "Reviewer_FyNE", "summary": "This paper studies non-convex stochastic optimization when the data is generated from a Markov chain. This is unlike most papers on the topic where one usually assumes that the noise process affecting the gradients is an i.i.d. process. The goal of this paper is to establish information-theoretic lower bounds on the number of samples needed to achieve an $\\epsilon$-accurate stationary point (in expectation). For both countable and finite-state Markov chains, the paper provides tighter lower bounds than those existing. For the latter case, an SVRG-like algorithm is proposed that additionally maintains estimates of the entries of the stationary distribution of the underlying Markov chain. It is shown that this algorithm achieves the $O(1/\\epsilon^2)$ rate for this setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comments on subsampling**: We really appreciate the reviewer for initiating such an interesting discussion. In the following we briefly present our understanding and hopefully would provide some insights to the comments. We think the reviewer’s intuition is correct and is aligned with ours. However, we would like to emphasize that simply using a subsampled sequence might not be enough to achieve the same rate as MaC-SAGE. This is because even under the i.i.d. case, vanilla SGD suffers from a slower rate. In other words, to get a faster rate as MaC-SAGE, variance-reduced techniques are needed. For the finite-state case, the main difference between the Markov sampling and uniform sampling (i.e., finite-sum for the i.i.d. case considered in literature) lies in that the stationary distribution $\\Pi$ is unknown and non-uniform, which makes its estimation necessary before applying existing algorithms designed for the i.i.d. case. Once it is guaranteed that the estimate of the stationary distribution converges no slower than the algorithm’s rate in the i.i.d. case, one can directly apply algorithms for the i.i.d. case (e.g. SAG, SVRG) to the Markovian case with the final rate scaled by $\\tau$. That is also the idea behind MaC-SAGE, where we maintain $y_t$ as an estimate of $\\Pi$. Also please refer to lines 300-310 on the right column for discussions. Finally, it is worth noting that the analysis for the Markovian case is non-trivial because of the correlation among time-dependent samples, although algorithmically the rate seems similar (up to $\\tau$) to the i.i.d. case.\n\n**Q1**: We thank the reviewer for bringing this to our attention. Actually, we are able to weaken such a strong assumption by now taking the expectation according to the stationary distribution $\\Pi$, i.e., $\\mathbb{E}_{s \\sim \\Pi}\\Vert g(x;s) - \\nabla F(x) \\Vert \\le \\sigma^2$, which is then similar to the bounded variance in i.i.d. setting. We note that considering this modified assumption does not affect our lower bound results (i.e., Theorem 3.1 still holds), as the proof of Lemma A.3 holds for any distribution of the chain.\n\n**Q2**: The stepsize $\\gamma_t$ is chosen as line 1026, which only needs the knowledge of hitting time. We will add its expression to the main text in our updated version.\n\n**Q3**: We think our proof techniques could be used to obtain high-probability results. Specifically, in Appendix A.3, eq. (19) holds almost surely, which hence indicates line 652 holds almost surely. Therefore, Theorem 4.2 is valid with probability one. For Theorem 3.1, similarly, we have shown Lemma 5.2, which is a high-probability result (see line 799 for details). In the proof, we set $\\delta = 0.5$ to get the final expectation bound (see lines 810-814). Thus, if we leave $\\delta$ as a parameter, a high-probability version can be characterized.", "claims_and_evidence": "The claims made in the paper are all rigorously supported by detailed proofs.", "methods_and_evaluation_criteria": "This is a theoretical paper, and there is not much to evaluate here.", "theoretical_claims": "I skimmed through the main proof ideas and they appear correct to me.", "experimental_designs_or_analyses": "There are no experiments in this paper. This is by no means a limitation since the focus of the paper is to establish fundamental lower bounds.", "relation_to_broader_scientific_literature": "The main contribution of the paper refines the existing literature on Markovian stochastic optimization by deriving tighter lower bounds than those available previously. The authors do a good job of positioning their contributions in this context.", "essential_references_not_discussed": "Relevant references are all well cited and discussed.", "other_strengths_and_weaknesses": "Strengths\n---------------\n- Time-correlated Markovian data shows up in a variety of stochastic approximation problems. Compared to their i.i.d. counterparts, much less is understood for such settings. In this regard, I find the contribution of the paper significant in improving the understanding of what is fundamentally achievable in the non-convex setting. \n\n- While the MaC-SAGE algorithm is essentially very similar to variance-reduced algorithms like SAG, SAGA, and SVRG, I still find it very useful to know that such an algorithm is minimax optimal in the finite-state Markov setting. \n\n- I think the ideas used for proving upper and lower bounds in this paper can find much broader applicability beyond just non-convex optimization. \n\nThere are no particular weaknesses that I can find.", "other_comments_or_suggestions": "In the finite-state setting, I have a comment regarding the MaC-SAGE algorithm. The algorithm needs to keep track of the number of occurrences of each state. I was wondering if this can be avoided using the following idea.\n\nSuppose the mixing time of the underlying Markov chain is $\\tau$. Then, the subsampled sequence $s_0, s_{\\tau}, s_{2 \\tau}, \\ldots, ..$ is ``almost\" i.i.d. with high probability. Now suppose one uses exactly the same algorithm as one would in the i.i.d. case, but updates it once in every $\\tau$ time-steps. In this way, one effectively runs the algorithm on i.i.d. data. So one should expect pretty much the same guarantees as in the i.i.d. case, inflated by a delay of $\\tau$, since one now effectively uses $T/\\tau$ samples, where $T$ is the total number of samples. Isn't this going to recover the same guarantees as MaC-SAGE, since it appears from Theorem 4.4. that the final error-bound is the i.i.d. bound scaled by $\\tau$? \n\nMore generally, unless I am mistaken, given data from an ergodic Markov chain, one could run any optimization algorithm (with no modification) on a subsampled data set (where the subsampling gap is informed by the mixing time of the Markov chain) and achieve the same guarantees as in the i.i.d. case, with $T$ replaced by the number of effective samples $T/\\tau$. \n\nSome discussion on this matter would be very helpful. Essentially, I want to understand whether there is any need to develop new optimization algorithms for the Markov setting, or would subsampling suffice.", "questions_for_authors": "I have some clarifying questions. I am happy to raise my score once they have been addressed. \n\n- Q1) The assumption of bounded variance in Assumption 2.2. seems a bit weird to me. In particular, at any given time $t$, the distribution of the state $s_t$ has not yet converged to the stationary distribution. Thus, $\\nabla F(x)$ is not the expected value of $g(x; s_t)$. Isn't this correct? If yes,  $\\mathbb{E} \\Vert g(x; s_t) - \\nabla F(x) \\Vert^2_2$ is not really the variance of $g(x; s_t)$ (unlike the i.i.d. case). What does it mean to assume a uniform bound then on this expectation? Wouldn't this bound depend on $x$, more generally, in the Markov case? Perhaps the authors can use the TD learning example presented earlier to validate this assumption. \n\n- Q2) How is the step-size sequence chosen to arrive at the result in Theorem 4.4.? This does not seem to be specified in the statement of Theorem 4.4., nor in the description of MaC-SAGE. Does it require knowledge of the mixing time $\\tau$? If yes, it brings me back to my earlier comment of simply sub-sampling the data based on the knowledge of $\\tau$. \n\n- Q3) The lower bounds pertain to the number of samples needed to ensure that the *expected* value of the gradient is below a specified tolerance. Can similar lower bounds be derived if one seeks guarantees with high-probability? To be more precise, given a failure probability $\\delta$, suppose we wish to determine the minimum number of samples $N(\\delta, \\epsilon)$ needed to ensure that $\\Vert \\nabla F(x_t) \\Vert $ is below $\\epsilon$. Is it possible to characterize $N(\\delta, \\epsilon)$ using the techniques developed in this paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the sample complexity of stochastic optimization for smooth, non-convex functions when the noise variables form a Markov chain instead of being i.i.d. 

In general, most of the reviewers support the paper. However, the are some concerns that the reviewer pointed out during the discussion: 

1) If the lower bound (Thm. 4.2) still depends on the hitting time but the upper bound (Thm. 4.4) also depends on potentially much larger mixing time (e.g., for periodic chains), then clearly these two bounds do not match. Also, since Thm. 4.4 depends also on the mixing time but the upper bound on [Powell & Lyu’24] does not, so the author's claim about optimality up to a constant factor does not seem correct without further modification of the setting. 

2) The reviewer was not convinced if this is a significant enough of a motivation to develop a new Markov chain optimization algorithm when there are well-established works out there. From the author's response, it seems that they wanted to additionally address the challenge of possibly not knowing the stationary distribution of the Markov chain. But does it fit the overall theme of the paper to proposing a lower bound for Markovian optimization algorithms and then providing a matching upper bound? 

In many practical instance of MCMC, one has the known target distribution $\pi$ which is hard to sample from in i.i.d. manner (e.g., uniform distribution over a complicated set), one designs an MCMC that correctly converge to the target distribution so that one can at least asymptotically approximately sample from $\pi$. In such situation, there is no reason to additionally estimate the stationary distribution.

In cases when one has an MCMC sampling algorithm with unknown stationary distribution, and suppose for some reason we believe it has some meaningful stationary distribution with respect to which we want to solve some expected loss minimization. In such situations, the author's motivation of additionally adding estimation step may make sense. However, the authors uses basic approximation of the stationary distribution using the empirical distribution by recursively updating proportion of times that the chain spends at each state. If the Markov chain is ergodic, this empirical estimate converges as fast as the Markov chain mixes and the estimation bias will be exponentially small. So the novelty of the proposed MaC-SAGE algorithm seems incremental over the existing results.

The authors are expected to discuss all these points in the final version of the paper.
Decision: Accept (poster)