Learning from A Single Markovian Trajectory: Optimality and Variance Reduction
Authors: Zhenyu Sun
Ermin Wei
Venue: NeurIPS 2025 poster ()
Keywords: stochastic optimization
Markov sampling
sample complexity
Primary area: optimization

Abstract: In this paper, we consider the general stochastic non-convex optimization problem when the sampling process follows a Markov chain. This problem exhibits its significance in capturing many real-world applications, ranging from asynchronous distributed learning to reinforcement learning. In particular, we consider the worst case where one has no prior knowledge and control of the Markov chain, meaning multiple trajectories cannot be simulated but only a single trajectory is available for algorithm design. We first provide algorithm-independent lower bounds with $\Omega(\epsilon^{-3})$ (and $\Omega(\epsilon^{-4})$) samples, when objectives are (mean-squared) smooth, for any first-order methods accessing bounded variance gradient oracles to achieve $\epsilon$-approximate critical solutions of original problems. Then, we propose \textbf{Ma}rkov-\textbf{C}hain \textbf{SPIDER} (MaC-SPIDER), which leverages variance-reduced techniques, to achieve a $\mathcal{O}(\epsilon^{-3})$ upper bound for mean-squared smooth objective functions. To the best of our knowledge, MaC-SPIDER is the first to achieve $\mathcal{O}(\epsilon^{-3})$ complexity when sampling from a single Markovian trajectory. And our proposed lower bound concludes its (near) optimality.

Learning from A Single Markovian Trajectory: Optimality and Variance Reduction
Zhenyu Sun," Ermin Wei
'Department of Electrical & Computer Engineering, Northwestern University
i Department of Industrial Engineering & Management Sciences, Northwestern University (zhenyu. sun, ermin. www.weeeoooottttttrreeee
Abstract
this paper, we consider the general stochastic non-convex optimization problem when the sampling process follows Markov chain. This problem exhibits its significance in capturing many real-world applications, ranging from asynchronous distributed learning to reinforcement learning. In particular, case where one has no prior knowledge and control of the Markov chain, meaning multiple trajectories cannot be simulated but only single trajectory is available for algorithm design. We first provide algorithm-independed
consider the worst
lower bounds with (( (and (e( ()) samples, when objectives are (mean-squared) smooth, for any first-order methods accessing bounded variance gradient oracles to achieve e-approximate critical solutions of original problems. Then, we propose Markov- techniques, to achieve ( 3) upper bound for mean-squares smooth objective functions. To the best of our knowledge, MaC-SPIDER is the first to achieve (c--3) complexity when sampling from single Markovian trajectory. And our proposed lower bound concludes its (near) optimality.
Chain SPIDER (MaC-SPIDER), which leverages
Introduction
Many modern learning tasks can be modeled stochastic optimization problems. Specific applica- tions range from (un)supervised learning, reinforcement learning to large-scale generative models. In particular, the surge deep learning and large models has made first-order methods those that rely solely on gradient information attractive due to their ease of implementation and computational efficiency 40
Yet, the commonly assumed i.i.d. data setting rarely reflects real-world scenarios. In many practical applications, data arrive sequentially and exhibit temporal dependencies, often shaped by underlying dynamical systems that can be modeled as Markov processes. For instance, in reinforcement learning, data are collected through interactions with an environment governed by a Markov decision process (MDP), producing inherently correlated samples (35]. In recommendation systems, user feedback unfolds over time, where each action depends on previous interactions in Markovian fashion 2]. Time-series data from sensors to financial markets are also naturally Markovian [8] 13]
MCMC methods, widely used Bayesian inference, rely on Markov chains to sample from complex posteriors g (28). Even in language modeling, transformer architectures produce token sequences with local dependencies that can interpreted through a Markovian lens 27).
These examples point to a clear fact: i.i.d. assumptions are sometimes insufficient, and optimizing in the presence of Markovian data requires more careful analysis. As result, growing body of work has emerged to study stochastic optimization under Markov sampling, spanning areas such as reinforcement learning 39 distributed optimization 33 [5] and federated learning (34] These
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

developments underscore the need for more unified and general theoretical foundation that can account for the challenges introduced by Markovian dynamics.
Compared to the extensively studied i.i.d. setting, analyzing first-order optimization methods under Markov sampling introduces new and significant challenges due to data correlation. In the i.i.d. case, each data point is sampled independently from a fixed distribution, yielding unbiased estimates of the stochastic gradient. This independence enables the direct application of standard tools such as However, when data are generated by a Markov process, consecutive samples are inherently correlated, complicating the statistical properties of gradient estimates. Specifically, the Markovian dependence introduces bias into the gradient estimates, which disrupts the foundational assumptions that are crucial for -.aedd analysis. As a result, many classical techniques no longer apply directly, and alternative tools are required to handle the joint effects of bias and temporal correlation 7
variance bounds and concentration inequalities (29 22 25
21
There are fruitful results about stochastic optimization with Markovian samples in literature, where a large amount focus on designing new algorithms and deriving corresponding sample complexity upper bounds. A common assumption placed by these works is that the algorithm is implemented in the simulated environment, meaning multiple trajectories can be incorporated
facilitate the performance of the algorithm. For example, in (36 23 multiple trajectories are sampled from the underlying Markov chain for an update of policy in the RL problem. And variance-reducee techniques are incorporated by utilizing multiple trajectories to obtain better convergence rates and sample complexities [0 26 37 38). However, in practice one may have no access to multiple trajectories due to no prior know ledge and uncontrollability of the Markov chain. In such case, once the sampling begins, the chain keeps evolving and cannot be restarted, i.e., only a single trajectory is available for algorithm design. Based on this restriction,
[14] 11 establish SGD-basee approaches with batched samples drawn from a single trajectory and (6] further proposes the accelerating versions and generalizes them to variational inequalities. However, these methods suffer from slow convergence rates or high sample complexity, which is mainly because no variance reduction technique is considered as the i.i.d. counterpart. Moreover, when considering variance reduction for the Markov setting, biasness and time dependence make the analysis developed for the i.i.d. case fail to hold, which bring challenges in the derivation of new mathematical tools. Therefore, in this paper we are interested in understanding whether variance reduction can be achieved in the Markov sampling case when only one trajectory is available and aim to derive new pariance-reducet method to reduce sample complexity. Besides, we would also like to figure out what is the fundamental limit of our method and all existing methods. To achieve this, we further develop lower bound of sample complexity under both smooth and mean-squared smooth (which is commonly assumed for variance reduction applications) settings for any first-order algorithms, which nearly match the upper bound of our method. This concludes the near min-max optimality of our algorithm. Our main contributions are summarized as follows:
We provide the algorithn-independent sample complexity lower bound for any first-order methods of stochastic non-convex optimization problems, given data samples are generated by a Markov chain for smooth functions. Our lower bound shows complexity with the order of e e which nearly matches the upper bound of algorithm MAG provided in [1] O.
We also consider the case of mean meea--squred smooth functions, which shows broad applica- tions in variance reduction for the i.i.d. case. We provide lower bound of order e c when samples are Markovian.
We then propose new algorithm, called MaC-SPIDER. The convergence and sample complexity analysis is provided for MaC-SPIDER, which indicates nearly the same order of 3 hence combining with our lower bound demonstrates its (near) min-max optimality.
Variance reduction for non-convex stochastic optimization. Variance reduction has drawn much attention very recently. It effectively controls the variance to a low level and hence improves sample efficiency of solving stochastic optimization problems. Mature rrrranee-reduced techniques have been successfully applied to the i...d. case to reduce sample complexity. Popular methods include but not limited to SAG [32) SVRG (20 4. SPIDER [6]. In particular, it is shown that SPIDER can achieve the optimal order of e - sample complexity. However, in practice data might not be i..dd but Markovian. For the RL problem, variance-reduced methods have been developed by assuming multiple trajectories can be used for every iteration of the algorithm. Under this assumption

---

incorporating with SVRG gives sample complexity of O(e 10/3) when combining with SPIDER 38
30 37 and ( is achievable
Lower bounds for stochastic optimization. The sample complexity of first-order stochastic optimization has been central topic of study the past two decades. Among these developments, lower bounds play fundamental role, as they characterize the inherent difficulty of optimization and set performance limits for all algorithms within given class. In the full-batch setting, where the algorithm has access to all data, lower bound of (2(c-2) has been established for smooth non-convex objectives [T],, and this rate is achieved by standard Gradient Descent (18] Under the i.i.d. sampling assumption, lower bounds of S2(=-3 for convex objectives [ and S +) for general non-convex [5] have been proven. The latter improves to ( under a mean -uuane smoothness
objectives
assumption [5]. Correspondingly, stochastic gradient descent (SGD) [7 [8] and SPIDER [[6] achieves matching upper bounds in both settings, respectively. In the Markovian sampling regime, where data are temporally correlated, complexity results explicitly depend on the chain's mixing or hitting time, denoted by т. For strongly convex functions, [6] establishes a lower bound of
S( log(e-))) while for general convex objectives, matches the known upper bound for SGD in that setting. For non-convex objectives, [14] recently
[12] proves a lower bound of (2(TT=))) which
derived loose lower bound of (T =),, whereas the best-known upper bound remains (TT--))
2 Problem Formulation
Consider the general stochastic optimization problem,
(I) unknown underlying distribution. In this paper we focus on the Markovian case, i.c.. we assume that the samples {s:](= form a sequence generated by some underlying Markov chain with its stationary distribution being æ. Moreover we focus on countable-state Markov chains, meaning the state spaces are countable but may not be finite. Note that the Markovian setting reduces the i.i.d. setting by decoupling the dependence across time.
min Fzz) (x=s(f(r;s)
where S for S being the support, and denotes
Since exactly solving IT is NP-hard [19.. by restricting to first-order methods, search for an e-apprxximate critical solution, which is widely adopted by literature [T0] 5| of F(x) defined in In particular, given differentiable function F' _Rd + R, our goal is to find some x such that |VF((>)] Se
for any e >> 0.
2.1 Function class
Particularly, we consider all smooth functions in the following class:
F(A. L): {F. Rdd IR
F(O) inf F(x) < A
(2) where 2 0 and are fixed parameters. The condition F(O) inf, F(x) A on F(O) can be generalized to any initial value F(Zo). However, for zero-respecting algorithms (to be defined in Section 2.2 we have Fo = 0. In particular, we consider the case where the objective F is smooth and has bounded initial gap to the optimum.
[v) VF(I)l S L| yll. Vv, E Rd)
2.2 Algorithm class
Our algorithm class is inspired by [5] We consider the following first-order algorithms such that:
the algorithm can access an unknown F F(A, L) by stochastic first-order oracle O; the oracle O returns a sequence of samples z == { (B can be time-dependent) generated by a Markov chain and mapping
Or(z, (x)) == (g(2; &
where g(x;s) = vf(2; s) is the stochastic gradient.
3

---

at iteration t, the algorithm queries batch of M point
2t (Zt,1 2,, F(,M):
for each batch query zt, O responses with
Op( == (0,( OF =,,)),
where Zt,i is the sequence of sample drawn for 2z,i and 21 U 2t,
Then algorithm A consists of a sequence of measurable mappings {Ar] to generate a sequence of iterates [ satisfying the following conditions:
the (t + 1)-th iterate is the output of Ar when taking all previous oracle responses as imput, i.c.,
Alrl = A. (1 AlOr] (1 22)::
Algorithm A zero-respecting, i.c., for any O and samples 2o, 21 with any M, satisfies for any 2 -1 and any E [M]
support
A[0rly H11m
support(gs..r),
kst.mm E[M]
A[OOr] and support(x) represents non-zero
where Ok.m the stochastic gradient for "kmm coordinates of x.
We denote (M) the class all zero-respecting algorithms. It is worth noting that for any AlOrl A E Azr (M). 00
by definition.
We note that the above-mentioned algorithm class is general, which captures many existing first-order algorithms. For example, the vanilla MC-SGD [14]
It++ Iz (hg(s st)
corresponds M 1, 1, 0. For Randomized ExtraGradient 6 which maintains the update by
1t+1/2 2 mp((1 S1.+1)
I++1 U/
where by generating J, Geom(1/2)
{
2 2 u 1 ir2 < K
ui +
0 otherwise
with
2
un = 2
Σ 0(1441/288844tt)) T+t1 = T, + +1+ 2 for To = 0,
1=1
one can clearly see that it fits in the case of M = 2 and B = 2
2.3 Markov-Chain Classes
In this section, are interested in any sampling schemes characterized by finite-state Markov chains, i.e., |S| < oc. Before formally defining the classes Markov chains, we present the definitions of eritical quantities characterizing the structure of chain.
hitting and mixing times which Definition 2.1 (Hitting time). For any state w E S, define
= inf 2 8, =
the time Markov chain firstly reaches state w. The hitting time Thas is defined by
That : max 'The batched queries represent multiple variables maintained by the algorithm to update iteratively at every iteration.
E/T So v).
v.wESxS

---

Intuitively, the hitting time measures the maximal number of steps for which any pair of states take to transit between each other.
Definition 2.2 (Mixing time). Consider Markov chain P. For any 0, define
(E) = in 2 0 dP T S c)
where dr (P, Q) represents the total variation distance between probability measures and Q. We call Tmir the mixing time of P, where Tiii Emin (1/4).
The mixing time measures the convergence speed of a Markov chain to its stationary distribution. Then we consider the class of Markov chains for which the stationary distribution exists and the hitting time Thit is upper bounded by parameter 2 (scaled by some numerical constant). We denote the chain by P. Specifically.
M(T) = That S CoT, lim pP n. Vu)
(4)
10000
where co is some numerical constant; Thit is defined in Definition 2.1 nPt represents the distribution the chain after t-step transitions starting from the initial distribution
2.4 Oracle Classes
Recalling that the oracle O returns a sequence of stochastic gradient evaluated at each query, we place the following assumption.
Assumption 2.3. There exists some 0 < o² < co, such that Eg-x (lg(1;; (000--FF()l Ep-n s)] (x) for any z.
VF(2)] < a² and
Basically, Assumption 2.3 only limits the asymptotic behaviors the stochastic gradient: 1) gradient
estimate, i.c., Ea~x g c; s) V=(x); and 2) bounded variance, i.c., Es>a [1; F()))
(=)]l <
a². Note that this assumption does not place any restriction when the chain not yet converged to its stationary distribution. Moreover, it becomes aligned with the bounded variance assumption of stochastic first-order methods under i.i.d. sampling by further foreing independence across samples
118 4
Then, are interested in oracle classes. The first natural class, denoted by O(o², r), is that the stochastic gradient is sampled from a chain contained in .M(T) by 4 and such that Assumption is satisfied. This oracle class is considered in SGD-based analysis in literature 6].
The second class we consider is inspired by applications of variance reduction in the i.i.d. setting 5). where besides bounded variance of stochastic gradients, stronger requirement is placed. In particular, we assume that the stochastic gradient 9 satisfies the mean- -quurre smoothness:
Assumption 2.4. There exists
such that EE ll s) g s)1? < L | y11 Yx, y Rd
It is straightforward to observe that mean- smoothness implies smoothness of F by observing |T [g(=; - gly; +]]l|² Bg>><lg(<;; 8) g s) T.21| y|l2. Then, the second oracle class, denoted by (o²2, T, T.2), we force the stochastic gradient g is sampled from a chain in ((T) and such that both Assumptions 2.3 and 2.4 are satisfied.
2.5 Sample Complexity Measures
Our results of lower bounds are established in terms of the sample complexity for finding an approximate critical solution of F. Define P the collection of all well-defined probability measures supported on S. Let (xA)) = U.ge 2 be the collection of all samples utilized til time t by algorithm A.
Concretely, the sample complexity measure for the smooth setting is defined by
(M, L 1,
sup sup TEP 000 FEF(A.) (MA
sup
inf
inl 2 B/ A(0F)
5e
(5)
5

---

Similarly, for the mean-squared smooth setting, the sample complexity measure is given by
N A, L
1 sup TEP OE0(o" FEF(A AEA2r(Ad)
sup
inf
inf (ST(A)) 2
A |1 S EEJ.
(6)
When (M,, A, L, o². is lower bounded by Nr, i... (M, L, 02,, 2 Nr with Ny denot- ing all collected samples up time it indicates that there exists some stationary Markov sampling process P with bounded hitting time and an oracle O E D(a²,7) such that for any A E Agr (M)
there exists F F(A,L) L) for which VF (=)()))) > c, where the expectation taken over randomness in A and O. other words, least NT number of samples must be required to (possi- bly) achieve an e-approximate critical solution for any first-order algorithm (and similarly for the mean-squared smooth setting).
3 Algorihmn-independent Lower Bounds
In this section, we show our main results on the lower bounds of sample complexity for stochastic non-convex optimization under Markov sampling. The result is all first-order methods that are respectnng take at least such samples to reach an e-approximate critical point of the non-convex objective function.
implying that
We show the following sample complexity lower bounds for any finite Markov sampling processes under both smooth and mean-squared smooth settings. Please refer Appendices B and C for detailed proof.
Theorem 3.1. For the smooth setting, there exist numerical constants C1, 02 > such for any M, I, A, 0,
TLA E
TO² min {aio", ,202))
( =
+
et
For the mean-squared smooth setting, have
TLA
TLA02
N A, T.2 12, 7) S
Remark 3.2. Note that the extreme case T corresponds to the i.i.d. sampling case. To see this,
recalling the definition of hitting time v = 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 i and there is time dependence across samples drawn at different time steps, hence reducing to i.i.d. case. Thus, when σ² > LA our lower bound results are aligned with those provided in (5). Moreover, noting that for the smooth setting the lower bound reduces to
مييم
+ TO'LA
if o2 LA,
nearly matches the best-known upper bound in literature 6) which is Ō (Tmer + T LL
4 Min-max Optimality for Mean-squared Smooth Functions
In this section, we propose Markov-Chain SPIDER (MaC-SPIDER) ,which is a variant of SPIDER [66] under Markov sampling, manifesting the (near) min-max optimality of sample complexity. In particular, we show that the sample complexity of MaC-SPIDER is OTTmirr7 1122 (-3 (with
min
Tiin min, (s)), which is comparable to our proposed lower bound ((Tc-3) 3) up to some constant
1/2 gap (independent of <) between π min Tmiz and the hitting time r. Proof for this section is deferred to Appendix D
We present MaC-SPIDER in Algorithm [ which exhibits effective variance reduction ability, hence improving sample complexity. Algorithmically, it is similar to SPIDER (16), while now the sampled
Note that this upper bound is achieved under stronger assumption than Assumption 2.3 i.c., in 6 it is
assumed that [[g[;; s) VF(x)]] < o Vz, But we conjecture this bound also holds under Assumption 2.3

---

Algorithm 1 Markov-Chail SPIDER (MaC-SPIDER)
1: Input: initial point zo. No O, batch size Mi and M2. integers and r, stepsizes {m))=
2: for [- 0, ,...,,
do
3: if't mod r = then
4:
Draw M1 samples and compute 1t Mi E g(1
5:
N111 N₁ Mi.
6:
else
Draw M2 samples and compute it 1t-1 + Ma E M2 SN.ti11) ((14-1;8N.+1)
7:
N141 NN+ + M2. 8:
9:
end if
10: Set the learning rate The min
8L Pxll
24+-1 2, U/
12: end for
Output: ör sampled uniformly from (r+) T-
gradients are drawn from some unknown Markov chain rather than identically and independently. One crucial characteristic of MaC-SPIDER is that only single trajectory generated by the chain is used for implementation. In other words, one needs not to care about when or where to restart the chain once the sampling process begins, but just keeps in mind how many samples should be drawn every iteration. This also enables its broader application in practice. For example, in literature 30 [66] multiple trajectories must be simulated before variance-reduced techniques to be applied, which costs extra resources and waiting time since every trajectory requires restart and then wait until enough collected samples. More problematically, multiple trajectories may even become unavailable in practical scenarios, when the chain is uncontrollable to simulate. MaC-SPIDER only uses single trajectory with no further limitation and knowledge on the chain, which in this sense distinguishes its simplicity and applicability for practical implementation.
In particular, 2t maintained in Algorithm | serves an estimate of Fx;;;) that incorporates the history of sampled gradients for better estimation with fewer samples to control the variance. This intuitive and understandable when samples are i.i.d., each sample is independent and unbiased estimate of the true gradient. However, such unbiasedness no longer holds in our case, since Markovian samples are essentially biased and time-dependent, which makes it unknown whether or not variance can still be reduced effectively. Fortunately, by carefully analyzing the coupled correlation across different samples, we provide positive answer the controllability of the variance of Uz, formally stated by Proposition 4.3
We first present the following useful lemma, which generally provide the basic guidance the variance control of Markov sampling.
Lemma 4.1. For a Markov chain {&t fo with state space S and stationary distribution n, consider any function h S + Rd and define h2 == Eewn [h()]] Denoting Ez(-) the expectation conditioning on filtration F3 and Tmiz as the mixing time, the following holds:
(I). Ef [[((s) - 11 < o², given any ES,
1
M
7Tmsz
78
min 0²
E2
h(8+++)
:)- hr
M
Tumin M
Tmin M2
1=1
(2). 18 TTREsTIIM6 [|{(s]] B2, then for any St
M
Grmiz B
E
h(s++e)
- hr
(8)
M
Tinnn M'
14rmix B²
2
B²
E,
(((s44))
hr
min
(9)
M
T M
Tmin M
Remark 4.2. Note that similar variance bounds as Part (1) are provided in 6 However, either of their analysis requires bounded gradient assumption, i.c., [[FF())] < G < co, Vz or bounded
7

---

noise assumption, i.c., (lg(x; s) VF(2))l oo oo, while ours do not depend on such restrictive assumptions.
Then leveraging Lemma gives the following result, which indicates that the variance of e can be well controlled to an arbitrary level.
Proposition 4.3. Considering Algorithm Lnd supposing Assumptions 2.3 2.4
hold, by setting
112mmia max
16Tmia
Mi
max (o, o²}, M2
VTmint
we have for any S
E 1t
VF(x:)]12 Se, V2
worth noting that Proposition 4.3 implies that to control the variance to level of Oc²2), the average number of samples per iteration that Algorithm I Jsees is O(c-1), while simply using batched samples requires (ce-2) samples [ Thus MaC-SPIDER successfully reduces the variance with fewer samples. This is the main reason why the sample complexity can be improved to O(e ()) It is
formally summarized by the following theorem.
Theorem 4.4. For Algorithm wwith any e S 1 assuming Assumptions 2.3 2.4 hold, setting
M1 = 112 maxfor o² M2 = 16Tmix
167A
T
Tiiin?
Vimint
e²
2²
where A = F(no) - ming F(x),, we guarantee
E VF II S Te.
Moreover, the lotal number of samples is ( min
1/2 -3).
Remark 4.5. Combining with the lower bound in Theorem 3.1 we note that MaC-SPIDER achieves 1/2
almost the same order of -3 up to some gap (independent e) between т and π. min Tmiz- This shows its near min-max optimality.
Proof Idea of the Lower Bounds
In this section present the proof idea of how obtain the sample complexity lower bounds for Markov sampling. We first clarify the proof sketch by focusing on the case where = 1, i.c. only sample is drawn from the underlying Markov chain by the algorithm. Then, generalize it to the case of B 2 which can also be time-dependent. Full proofs are presented in Appendices B and
The core technique inspired by [5] is to construct "hard" function F' with f(: supported on each state of Markov chain lying in the required class such that the gradient norm, FFx)), is small only each coordinate æ 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 a, i...
prog, (x) == max{k: 2 1 |<>|a| > a}
where [zr]a represents the k-th coordinate of ar. We prog., if [a]kl] S a, vk [d]. Then the task of finding an e-approximate critical solution is equivalently transformed to finding a solution whose coordinate progress is high. Formally it is stated by the following lemma.
Lemma 5.1. There exists some F+ E F(O(Aed) such that [V)] > e 0 if progo(2) (x) d.
Indicated by Lemma 5.1 ensuring [>)](=)] S e requires all coordinates of be nonzero. Then for the smooth setting, we construct a chain with its hitting time upper bounded by and at least ((T/q) (with q e (0, 1)) iterations are needed to make one increase in progo( It is stated by the following lemma.
Lemma 5.2. For any q E (0,1) and any rerperespnn algorithum A Agr there exist Markov
chain contained in M(T) and some F E F(O(Ade) ) L) with g" (x; s) satisfying VF* = Bgw [g" (x;; 8)) and Bywr llg" (ax; 8) F (2) < 26 2//g) such that for any 0 < 5 < with
probability at least 8
7 1
(I=A] < d, Vt <
max max progo maxprog, ME[M] #51
4g
8

---

In fact the constructive function F* in Lemma 5.2 coincides with the one in Lemma 5.1 which then implies that at least (Q(d//q) iterations are needed guarantee an e-approximate critical solution output by any algorithm and hence (TTd/g) samples (due to B = 1). Finally setting d = (2(E and 1 = (e2) concludes the lower bound ((T shown by the smooth setting of Theorem 3.1
For the mean-squared smooth setting, we have the following result.
Lemma 5.3. For any q E (0, 1) and any zero-respecting algorithm A E Agr, there exist Markov chain contained
M(T) and some F E F(O (Ade); L) with g (x; 8) satisfying VF
Ee~n (2; (2; 8)] and Bg llğ (z) VF (x)]l I ( such that for any 0 < 8 < 1. with
probability at least
< - logg 0-
max progo (I.A)O < d, V1 mE[M] #5t
4g
Thus, taking d = O(c=l) and q = 0(2)) recovers the bound for the mean-squared smooth setting in Theorem 3.1
Note that the above proof derivations are established on the precondition when B = 1 by which we able directly obtain the sample complexity bounds through the iteration complexity analysis, since the iteration complexity is the same as the sample complexity. To generalize our results to B 2 present the following result.
Lemma 5.4. There exist a Markov chain in (4) and some functions F",g" (F*,g") .g") satisfying corresponding conditions in Lemma 5.2 (or Lemma 5.3) such that for any zero-respecting algorithm Agr with B 2 1, there is a zero-respecting algorithm Agr with B = ffr which the following holds:
for any 2 0 if maxmma [M] max,51 progggg p01) k. then maX maXy5: progo aTa.
progo A(Orly S
k YA < S d.
The above lemma indicates that we can always find an algorithm 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, combining with Lemmas 5.1 and [52 yields that accessing multiple samples every iteration has benefit on improving the sample complexity for the algorithm, which hence implies the lower bounds that holds for B = also holds for B 2 1.
Limitation
The paper only considers the case of finite-state Markov chains, while in practice it is highly possible that the underlying Markovian sampling process admits infinitely many states. Besides, we only consider stationary Markov chains in the paper, which limits the generalization to the non-stationary setting. Therefore, extension non-stationary Markov chains is interesting direction and may need extra efforts.
7 Conclusion
In this paper, we study the first-order non-convex stochastic optimization problems. Unlike the conventional i.i.d. sampling, we focus on the case where data samples and stochastic gradient estimates generated by an unknown Markov chain, which introduces additional data correlation and hence non-trin con-trivial analysis difficulties. Due to the lack of sample complexity lower bound results and the gap the best-known upper bound under the Markovian setting, we provide improved complexity lower bound with the order of e for general smooth functions, which nearly matches the best-known upper bound. We also consider the mean-squared smooth setting, which exhibits broad applications in variance reduction literature. We prove that for the mean-squared smooth setting, the sample complexity lower bound the order of for Markovian samples. Finally, we propose a new algorithm MaC-SPIDER, which to the best of our knowledge is the first variance-reduced method under a single Markovian trajectory, such that its sample complexity upper bound nearly matches our proposed lower bound, implying its near min-max max optimality and the tightness of the lower bound.
Acknowledgements
This work is supported by NSF awards ECCS- 1030225,,,,, 2216926, CMM1-2024774 and AST-2421845.

---

References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Tlge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidr, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[2] M Mchdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: survey. ACM Computing Surveys, 55(7):1-38, 2022.
[3] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradcep Ravikumar. Information- theoretic lower bounds the oracle complexity of convex optimization. Advances in Neural Information Processing Systems, 22, 2009.
[4] Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707. PMLR, 2016.
[5] Yossi Arjevani, Yair Carmon, John Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165-2)) 2023.
[6] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Advances in Neural Information Processing Systems, 36, 2024.
[7] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691- 1692. PMLR, 2018.
[8] George EP Box, Gwilym M Jenkins, Gregory C Reinsel, and Greta M Ljung. Time series analysis: forecasting and control. John Wiley & Sons, 2015.
[9] Stephen Brooks. Markov chain monte carlo method and its application. Journal of the royal statistical society: series (the Statistician), 47(1):69-100, 1998.
[10] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):11-12,, 2020.
[11] Ron Dorfman and Kfrr Yehuda Levy. Adapting to mixing time in stochastic optimization with markovian data. In International Conference on Machine Learning, pages 5429-5446. PMIR, 2022.
[12] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549- 15788 2012.
[13] Philippe Esling and Carlos Agon. Time-series data mining. ACM Computing Surveys (CSUR), 45(1):1-34, 2012.
[14] Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference on Machine Learning, pages 9412-9439 PMLR, 2023.
[15] Mathieu Even, Anastasia Koloskova, and Laurent Massoulić. Asynchronous sgd on graphs: a unified framework for asynchronous decentralized and federated optimization. International Conference on Artificial Intelligence and Statistics, pages 64-72. PMLR, 2024.
[16] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018.
[17] Dylan J Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, and Blake Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, pages 1319-1345. PMLR, 2019.
[18] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal optimization, (144:2341-2366) 2013.
10

---

[19] Christopher Hillar and Lek- Hek- Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
[20] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
[21] Kyurae Kim, Jisu Oh, Jacob Gardner, Adji Bousso Dieng, and Hongseok Kim. Markov chain score ascent: unifying framework of variational inference with markovian gradients. Advances in Neural Information Processing Systems, 35:34802-344 34816, 2022.
[22] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):365-33) -376 2012.
[23] Yuheng Lei, Yao Lyu, Guojian Zhan, Tao Zhang, Jiangtao Li, Jianyu Chen, Shengbo Eben Li, and Sifa Zheng. Zeroth-ordes actor-critic: An evolutionary framework for sequential decision problems. IEEE Transactions on Evolutionary Computation, 2025.
[24] David Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[25] Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In International Conference on Machine Learning, pages 12931-12963. PMLR, 2022.
[26] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance- reduced) policy gradient and natural policy gradient methods. Advances Neural Information Processing Systems, 33:7624-7633 2020.
[27] Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar. Attention with markov: A framework for principled analysis of transformers via markov chains. arXiv preprint arXiv:2402.04161, 2024.
[28] Christopher Nemeth and Paul Fearnhead. Stochastic gradient markov chain monte carlo. Journal of the American Statistical Association, 116(533)433--55, 2021.
[29] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on optimization, 19(4): 1609, 2009.
[30] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026-40240000 4035. PMLR, 2018
[31] Abhishek Roy, Krishnakumar Balasubramanian, and Saeed Ghadimi. Constrained stochastic nonconvex optimization with state-dependent markov data. Advances in neural information processing systems, 35:23256-23270, 2022.
[32] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112,200 2017.
[33] Tao Sun, Dongsheng Li, and Bao Wang. On the decentralized stochastic gradient descent with markov chain sampling. IEEE Transactions on Signal Processing, 2023.
[34] Zhenyu Sun, Ziyang Zhang, Zheng Xu, Gauri Joshi, Pranay Sharma, and Ermin Wei. Debiasing federated learning with correlated client participation. arXiv preprint arXiv:2410.01209, 2024.
[35] Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
[36] Philip Thomas and Emma Brunskill. Data-efficient off- aff-policy policy evaluation for reinforce- ment learning. In International conference machine learning, pages 2139-2148. PMLR, 2016.
[37] Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. arXiv preprint arXiv:1909.086111 08610, 2019.

---

[38] Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty Artificial Intelligence, pages 541-551. PMLR, 2020.
[39] Sheng Zhang, Zhe Zhang, and Siva Theja Maguluri. Finite sample analysis of average-reward learning and q-learning. Advances in Neural Information Processing Systems, 34:1230-1242, 2021.
[40] Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. A survey of large language models. arXiv preprint arXiv:2303. 18223, 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Both the abstract and introduction discuss the sample complexity lower bound and the new proposed algorithm MaC-SPIDER with near optimality, which reflects the contribution and scope the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitation of the paper is clearly discussed.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The paper provides complete proof for each theoretical result and clearly states the corresponding assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper is purely theoretical and has no empirical result.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper is purely theoretical and has no experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cippscc/puullc//guu /ttoe//uuuddeeoooouuuubiiiiiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is purely theoretical and does not have experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is purely theoretical and has no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is purely theoretical and has no experiment.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://ps...aooss.ccoooooo/////a
Answer: [Yes]
Justification: The authors reviewed the NeurlPS Code of Ethics and affirm the paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper studies the theory of stochastic optimization and has no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper studies the theory of stochastic optimization and has no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper is purely theoretical and does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is purely theoretical and does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the datasettcooeemmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper studies the theory of stochastic optimization and does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is purely theoretical and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
The paper provides the sample complexity theory of stochastic optimization and does not involve LLMs any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bestps:/nneurdee ///Coonfreeenee/22225 for what should or should be described.
19

---

A Constructions of the Markov Chain and "Hard" Function
A.1 Construction of Markov chains
In this section, we construct a Markov chain that used for the lower bound proofs. The idea is to construct a chain such that there exist two states between which least steps must be take to transit; 2) the hitting time of the constructed chain is upper bounded by т. Without loss of generality we assume T is even.
In particular, we consider a directed cyclic- like chain with self-loops. Denote s = be the i-th state of the Markov chain for i E {0, 1..... 2r' 1) with r' r/2.. Then for any q (0, 1/2) the transition of the chain defined as follows:
0 P(s 2|s 0) = P|=
1/2: + +
P(s T' + 3|s = T' + = -|====>
P(s r' + 2|s 7' 2 1/2:
.
- 1/2; P(s = 0/s = 2T' g 1|s 2r' + = -, P(s = 2 + 1|s
P(s - +
1) 1/2;
.
i) P(s - 1/2, v $ (,,,,T',''+ 1, + 2,27'' +1}.
Then letting of = 0, w = + 1, +
= + is straightforward that the above constructed Markov chain guarantees that transitioning between of and wi takes at least r/2 steps. Moreover, the hitting time of the chain is (T) by noting the hitting time of directed cyclic chain with self-loops and states is (n).. We denote this chain by p and hence P E M(T).
A.2 Construction of function F
Now we construct a "hard" function that is difficult for any first-order algorithm to search for the critical point. Specifically we consider the following two functions
[d/2]
h1(x) = -b=1))((=)1)+
+ (V(-Lalaa)((11<bbaa)) - (1((=))))0(((
(10)
[d/2]
h2(x)= =
(#b (1]-(=)2---00 bal (((0)2=-))(((0)2))))
(11)
1=1
where
u S
v(u))=
exp
120-174)
u
and
d(u) = Ve L e e-fdd
with u E R.
We denote т, as the corresponding probability of state of the stationary distribution π. Then, given the Markov chain H constructed Appendix A. we know that at least }7r steps are required to take transiting from of to wi and vice versa. Then, we construct function F such that F(x) (x) + hz)x, where we denote 8" = [Mi v5), w" = [w], wz} and n,- = ne + Teg Tw- = Tw; + Twg. For any and i 0 define Zgg ([x]1..... [m]s,, 0, ... 0) as the truncated version by only keeping the first i coordinates. We also set I<u = r. Then we have the following properties of F.
Lemma A.1. Let F(x) = Th (x) Tw- he(x) for hi he defined by 10 following:
Then we have the
(1). F(0) inf, F(x)= & And for some constant Do >
(2). [V))(=)] I 23 and Vh,(2)] < 23vd, 2,
20

---

(3). F(x) is smooth for some constant 1 > O.
(4). pfprog < d, |VF(()) 1.
(5). [Vh,(t))<smgg (a) = | (* (c) spross (x)) 8 == 1,2.
(6). If (a) odd, progo (hi (z)) S progy (x), progu (V (h2(z)) S progy (x) If progo (x)
even, progo Vh1 (z)) - p (z) + progo (h2(2)) S progy (z).
(7). If progy (z) is odd, Vh1 Vh (h ( even, Vhi(z)= (hi (z)) Vh²(2) 2 (z)) Vhg(2) Vh2 (o)) If prog y (x) is
(h2 (z))
Proof. For Part (I), observing that F(0) < 0 and noting that 0 S (bu)) S e, Φ(u) S V2Te.
F(x) 2 -+())((==)))
Σ (( dev deve -doo
with 4. = 2xc, which completes its proof.
For Part (2), noting that 0 S v'(u)) S v54e-I and O S d'(u) S Ve, combining with the fact that for each 1.2
Oh, (x) 2 w0 -- - ( ()))) ("((a))) -1
dx;
yields
Th; 0æ, (x) S Leve V/4e V S 23
implying [h+(2)]] s 23 and
[,)] < d3 vi 1,2.
Parts (3) and (4) follow directly from 10 Parts (5)-(7 follow from the observation that
1
Vhi (x)
(x) [0]2:+1 ..... 0), if (22
Vj
Vjii+1
2'
1
Vh2(x) = Vha(l=),..... [xl2: ...................... 0). if |x2j
S
Vj
21+1.
2"
B Lower Bound for the Smooth Setting
In this section, we show the lower bound of the smooth setting in Theorem 3.1 Based on the contructive F in the last section, we consider the following gradient oracle g: for each i-th coordinate of g
if E (vi, wih lo(2; s)], = (x), 1 1ii progy (x))
Lezut
if e (wi, wi}, [g( = [Vh2(=))
(1+1fi> > prog (z)}
1 |س==
otherwise, g(r; 0.
(12)
Recalling the definition of P*, note Ipss = of I fuf, vz1) P(s wi q E (0, 1/2). Then, we have the following lemma.
s fwf, w5})
Lemma B.1. Considering stochastic gradient g(2; 8) constructed as 12 the following statements hold:
(1). For E (vi, wf, wz}, with probability at least 1 (r(g)(((1;))) S prog (x) and g(x; 8) g( (x); for all x.
21

---

(2). For & {ef, 12, wf, w2). with probability 1, progn(o(1; I prog (z) and g(z;,t) glasome (1))81) for all x.
(3). For any s, with probability 1, progo(g(x;s)) s)) S + prog, (x) and g(æ;s) = g( (1)) for all x.
(4), (esTlg(Z; = F())).
Proof. We firstly show Part (3). Note that by 12 and Part (7) of Lemma A.1 for any I, 8,
[a(2; st]]; 0, vi 1 4 (2) in the sense that Whi (z)]; [V)] 0, vi > 1+ prog (z), (x;
which implies (g s)) < + progg (z). Moreover, by Part (7) of Lemma A. defin-
ing x' = 2g1+pm (a) gives (z) = (z') and Vh2(r) = Vh2(2'). Thus, we obtain
g(:; 8) g(x;; s) for any implying Part (3).
For Part (1), note that when i 2 1 prog (x) and E {es, w²), g(x; 8) [Vy prog (x)
for j 1, which implies progu(g(z;) s)) S progy (I), Vs E {uz, wi}. Further, according to (5) of
Lemma A.1 we have g(x; s) = g ( (a); 8) for E {uz, wa} and all æ. Since P(= = 0) = 1 1-
hence Part (1) is proved.
Part (2) holds trivially in the sense that (x;; 8t) = when & $ {vi, uzz w wz} Finally, Part (4) holds since E[A./q {of, u5}] E B[1./9 E {wf, w 1.
Also, we show in the following lemma that g has bounded variance.
Lemma B.2. For F(x)= (x) R -w- (2(2) and g defined as 12 then for any Markov chain with stationary distribution given any x E Idd
Esen (192;5) - VF(x))1 < and + 02 1-9
for some constant 01, 02,02 > O.
Proof. By Part (4) of Lemma we know [g s)] = V=(x).
Denote i' = 1 + progy (z). For any E {ui, Up wi, wi we have
g(:; 8) Fx)) = (0,...,0, (,] (1g=0 0
0) (1 - -. V/, - n.. Vh2(a), if E e5]
g(x; 8) V F(x) = (,, 0, [z)] (1 /4 1),0..... (1 -.. Vh2(2) - म.. Vhi if E w1]
When 1" 1 is odd, from Part (6) of Lemma A.I know that [v)((=);; 0. Therefore,
23- s SE {ui, o < Vh, (z)) 4- 23
(1)(;;)) ((()))))F(()) <3
+ V (z) 2 3| (/2+))] 3. 232 (1.=w;/9-11 2 (wi,w/)
and
[1((;;)))
< 2322dd, when a & {ui ug w w[}
where we use (2) of Lemma A.1 Combining the above three inequalities, it yields that when i" odd, for any Markov chain, any x, t 0 and any initial distribution of the chain,
E (z) [F(2)] a + a2 1-9 -q
q
where a1 =6 6.23. 02 3 23 and we use that BB(111/-1111 1)2 8 E (wi, w3)] = (1 - -g//4 The
case when i* 1 is even be derived similarly.
D
22

---

Then, we are ready to show Lemmas 5.1 and 5.2 We first focus on the case B = and then generalize B 2
Proof of Lemmas
5 and 5.2
Given any
>
0, we consider the following F
(*)x) = LX2 F
2/1
where
(13)
L
And we consider the following gradient g"
LA x
g²1;;) == 11
Tio)
with s) defined as 12 12 Since VF(x) Eg (g( (z; 8)}, (ar) = (a>xlg"(<0;00) We note
that
(F) -
1,
which implies that F* is L-smooth by Part (3) of Lemma A.1 Moreover, by Part (1) of Lemma A.J we obtain that
inf F(x)) E 41 Age
(0) inf F (x)
(F(0)
L d.
All the above concludes Lemma 5.11
To see Lemma 5.2 note by Lemma B.2 we have
4ajde² + 402(1 - 4) e
Eown | (2; VF (x)]l
q
Then, define
B, R===1 F progo (2; 8t)) + prog (x)}
Note that under the construction of the Markov chain P and F and g" for any zero-respecting algorithm A
Bo*k 0, Vk .,... 2T: conditioning on B,
That is to say within every 1 iterations B, can be at most once. And Part (I) of Lemma B.1 indicates that the probability of B, being 1 is no greater than q. Let k(t) =
mM maxis: progo (" A[O)=*) Then, the above implies that
k(1) < Σ Bi-
ISt
Also recalling the definition of P* guarantees for any / in the ideal case the number of possible non-zero B₁ can be at most 21/T with each being with probability at most q, implies
/2t/7]
BBS
Σ
ISt
1=1
where denotes the Bernoulli random variable with succeeding probability being at most q. Note that 2,5 are independent in the sense that conditioning the chain hits v" [w vz) and will hit w = [wi wš} at exactly 7/2 steps later, whether wi or w will be visited is independent of which of of or vn has been visited. Thus
P(((()) 2 SP
Σ Bi 2 d
1st
P exp
Σ B1
2
1st
$ "B Eigs Bi]
Se BB [22/-) 24)
= e 41 - + eq) 120/v]
< [41/7/g-d
23

---

Therefore, we conclude that for any å E (0, 1) and E (0, with probability at least 1 - 8,
(() < d, 14 < T(d - log(1/6))
4q
which completes the proof of Lemma 5.2
Proof of Lemmal 5.4 To see the part of the smooth setting of Lemma 5.4 note that for any algorithm A with B 2 we simply observe that by the construction of F and g and the Markov chain P
for any t 2 0 and m E [M], there exists an algorithm A with B = 1 for which progo(Fi,m -/0===1) <
progo fi. AlOr+)) since multiple samples do not contribute additional progress of which then proves the part of smooth setting (Similar claims can achieved for the mean-squared setting of Lemma 5.4).
Proof of the smooth setting of Theorem
3.7 Now to show the lower bound for the smooth setting of
Theorem 3.1 setting
LA
d = min
(14)
41 2
,
Saje2
and
σ²
(15)
9
8aze2
vields that F* E F(A, L) and Assumption
2.3 is satisfied. By Part (4) of Lemma A.1 and Lemma
5.2 choosing 5 1/2 renders that for any [M] with probability at least 1/2,
V F*
t
A|O
||| 2 2e,
A1 5
7(d 1)
4q
which implies that
7(d -
VF
100=-111 Fr,m
2
Vt
4q
Therefore, we conclude that
L, T(d -)
LLA
T
min (0102,021A4
4q
2
by the selections of d, q as 14 15 for some constants c 0.
C Lower Bound for the Mean-squared Smooth Setting
In this section, we show the lower bound of the mean- mean-squared smooth setting in Theorem 3.1 The idea is similar to the proof for the smooth setting, except that we replace the indicator function in 12 by its smoothed surrogate:
1/2
d
Ox(x) :
Σ r (1
(16)
k=
where I' is defined by
T(t) = JijA A(T)dr
f1/2 A(T)dT
with
A(t)= = exp (1/(10((t-1/4))))))) 1/4)(1 151/4
1/4<1<1/>
Then, consider the following stochastic gradient g: if [ø(z; s)]; (x), 1 (+00((x)
1 Lsme
if s (w], w s)); [h)( ( (1()) otherwise, g(x;5) = 0.
1 1s==;
(17)
24

---

It is straightforward to see Ex-, (2;; (x) V. prog (x) and hence [0(2; s)}; (V) j.j 1,2, vi Σ prog (x) when
(x). According to Observation of [5], we know
8 E {M], up, w wē}. Moreover, according to Part (6) of Lemma A.1 we have for any 8 E S
(o; s)] 0, vi
prog (z).
(x))), it yields that there is eactly one non-zero coordinate of 6(x; s). which is the + prog (z)-tth coordinate. Moreover, we have the following results for g.
Defining 6(;; s) = (a; 8)
Lemma C.I. Consider defined
17 Then,
1-
Esnn (g s) VF(2)]I S a3d as
(18)
for some constants dg, > O. for some constant 1 >
1 1 yll? Vx, y E R4.
E E [0 8) 8)1
(19)
Proof. Similar the proof of Lemma
B. 2
easily obtain 18
To show 19
note that
Blgg(r;)) - Fly: .)(l = [E16 (æ; s)
8(y; s) + [VF - VF
Σ
[E( s)]; (o(;; s)};) [VF(=)
where i 1 progy (z), + progy (v). Since
[((((z)))] - (8(y: s)(,)² (VP())). [V
([VF())) - (,(1)) + (VF(>) - VF()).
< (( - 0,(')) VF(() VFW))
and by Observation 1.3 of 5 [0((x) (v)) S 36| y/ and noting [0,(z) 1, (1. S
23, we obtain
B(8((;; s)], (ō(y; s)),)² < 2 (232 36 ul1 + VF(2)) vF())
9
Finally leveraging Part (3) of Lemma A. gives
P 1 | y11
(x; 31
q
with 22 = 4. 242 2 51..
Then we show the lower bound corresponding to the mean-squared smooth setting of Theorem 3.1
Proof of the mean-squared smooth setting of Theorem 3./ and Lemma 5.3 Noting that L-mean- squared smoothness implies L smoothness, thus consider the case L < L with L to be determined later. Consider the same F* as (13) and let g" s) = (LAl1)g X; s). Similarly, we have F* is L-smooth. Also
LA
Ex "awwllg" (x;s) VF <
(azd + a1(1- 9)/9)
1
and
7.X 2
E E E,-zzlg" (2; - -" (y: =
E [0(x/\;3)) - F(u/\;
1
Ll
|| - yl12.
h/
25

---

Then taking
LA
o²
d = min
4/1 Aue
Sage?
1
o²
Pa
max
1+
SagE²
Dl
L
S
11
guarantee that F E F(L, A) and Assumptions 2.3 smooth setting, we can easily obtain Lemma 5.3 and then conclude that
2.4 satisfied. Similar to the proof of the
LLA
ToA02
(M, 12,
0²
which completes the proof.
D Convergence Analysis of MaC-SPIDER
In this section, we provide the proof for Section We first present the following technical lemma.
Lemma D.I. We have the following claims:
drv(up't) x) S drv (uPt, T).
For k 2 2, tmix (2 S (k- T)mizz
Moreover,
T drv dr ,T) S mi 4T 2 0.
Proof. The first two claims are directly from 24 To the third claim, note that
Σ drv ,T)
drv (uPk :T)
Imir (2 (1(11)
duP xx) +
Σ
drv(uP' x))
1=0
k= t= L=tis (2-
drv 7 Tmic
(tmix (2 (2(2)))) tmie 22-
ddy (1, π Tmir
k2 Tmii
k=
S drv (1s, xt Tmmr
2Tmix
which completes the proof with drv (M, x) + +2 3.
D.1
Proof of Lemma 4.1 and Proposition 4.3
Proof of Lemma
4.1
Let ht h(s(++) b and h(s) h(s) hg. We have
M
2
M
M
2
E
h(8++s)
hx
E,
|
M
M
M
j=it1
26

---

First, we show the following useful bound: for any E S, given t 2 0 and 1 i j.
2
Σ
P((s+t = 6' 1 1844s = -s)-x(s() =){{(()]1[(({{]
SEES
Σ T(0') 7(6))-1/21P(044) 1112(((((=)--11111 18843 8) - 1100-10800 =(O')l (6))<(()))))) )
YES
- Σ SEES
Tyain P((sts = 8 1844 = 5)- - T(s')12 Σ
{()))1((2)11
EEES
2
1/2 P(s = 8/ 18441 1 = 5) -))-10 --((')] o²
min
EES
I 40 2 1
min (max drv (p- |/8 |s==))= =x))
(20)
Then, noting that for any 1 S i <i<js M,
E, (ht, h2.) =
Σ
P(Sl+i = || 82) Σ
P(sL+s = 5' |844 = (((((),h(s'))
#ES
x'ES
> (P((+++ =8| - -s(s)
Σ (P(stt)= = 5' |444) = =) - -m(s)) h(2'))
aES
e'ES
Σ (()) Σ (P(5tt)= = 8 114s = 5) - T ((s)))
+)
SES
EES
+)
> P(s = (1)) Σ (h(s))))))
SES
s'ES
<>
Σ> |P(8+4 = 81 (1)) - -s(
Σ
P(stt5 = 5 118445 8) - --((m)) m(3))|1((()|
#ES
D'ES
Σ ((s) Σ |P(S+5 = 5 1141 = 8) - ((s')||((ss]]ll
+)
SES
EES
< 40 2
max drv (Pi x) max drv v (pi s)
man
+ 20 max drv (pi- (. T)
2 1/2
where we use
20
and note En (()))
h(d'))
(h(s), Exx (s)((((())))
(h(s), Ega= [
O. Further using the fact Σt max, dry (P'(. 1 s), S 3rmiz by
Lemma D.I.
we obtain
2
M
M
E, (M. <
72 mimi 0²
6Tmiz
+
M
Tmin M2
TTmin M
i=1
j=i+1
Similarly we note that
Ex 11:1111
Σ
Piscti = 8 ss))(((s))
(P(44+ = s s|ss) (6)))]]((>) P Σ (()))(((s)
SES
SES
< Σ
P((44 = s st) - [s)]][((s)] 00
Σ
P(( s180) -(s) Σ (s))[((s)1+++
< mia
SES
SES
< 20 2 -1
min max dr (Pi(. 188)) T) +
27

---

which then implies by Lemma D.1
M
d² M
m Tiin M
E.
2
+
M
2=1
Combining all above gives To show note that
M
2
E2
(8++5)
- 117
M
M
M
M
E,
h($++1) - Et
h(st+t)
+ E.
(h(se+e) - 127)
M
M
M
M
2
Md
1
< 2
((c+1))
+
Ee
(h(s2++) - haT))
M
M
where we use (a + b)² < 2a² + 26 and E[X - B(X) & E[X}?
We note that by replacing h(s)) in (0) by /ss),
M M
E
(h(s:+z) - -1+)) h+m)
=s ( (()))=5//s))
M
1=
SES
P(stti = = (() x (s)
SES
M
2B
max drv d 1
Tmin M
1=1
6Tmin
<
v Tmin M
where we use Es-x [[((s)]] S (E,=x < B and this concludes 88. Moreover, similar to analysis of E, (ht, R2), we have
B
6Tmin B²
M-1
E
h
h($44))
Σ
E, (0(0444)
M
M
n min M2
j=it1
B²
GTmin B²
6Tmin B²
7 B2
<
M
Tmin M
Timin
Tmin M
7 B²
78 B
v Timin M
Tmin M2
and hence
M
14 14Tmin B²
22872 B²
E,
h(se+z)
hr
+
min
M i=1
Tinn M
M
which concludes
Proof of Proposition
4.3 We denote (.).) as the expectation conditioning on filtration F,
28

---

Note that for t mod r O,
M₁
E,lle - VF(x,)] E,
1
Σ
g 8 &N.ts) - (2()
M1
TTmiz
78 mix" o²
Mm
Tmin MP
by 7 of Lemma 4.1 and noting M1 = 112T min max
1/2
For L. mod * 0, conditioning on F+t1 and letting 9:41
g SNe1+ti) yields
Ex41 |1411 VF(++1))1 = E++1 or VF((a)) - - +
+ VF(zz)
|10e
VF(x:))]
E F4+1 91 M2
(F(*++1) VF(x)]]
+ 2( VF(x)), 14
10
F VF(=:)))
$ | VF 2
91+1
M2
VF( + VF()))]
2/ 0/ VF(x;) ( Ma VF(=++1) VF
Noting that E.41 1lg g s) - L 2|| - xz ||. Vs E S and E E441,5 (g( (14118))
g( s)] [ (x:)). combining with (8) and of Lemma
gives
Ex+1|| VF(I++))] < 10:- VF(=))I* + 12Tmi B
14Tmin B²
228 2
min 1
lIue VF(x))l +
miin M2
Tiim M2
Tmin M
where = max, |,141 - xell- Further noting
M2 = 16Tmiz
< I max maxx(mllall] c
mmiin
we have
Bes1 Se+1llu441 V VP( $ 110, vF(x))1 + -
e² E²
4 -1l1: VF(x,))
+ +
16
16
< 110 (xx))1 + / [110 - vF + g (c2 + 1/2)
where noting that for rto < f < r(to 1) given any to 0. we have for L/e
f1 VF(x:)]l < ll: VF 1/2 1 2 in the second inequality. Then
1
Ella V (1+ (1+c Ure vF(2r.)) + (1+ ( + +
4e
2
2
2
<
8
4
3ea
3
< 4
where we use the fact (1 (1+)/2) < Ve < 2 and Bllure - 2l 2/8.
D.2 Proof of Theorem 4.4
Noting L-mean squered smoothness implics L-smoothness of F, we have
F( F(x.) < (VF(2)), 22))
|
xz 12
2
Lnf
=-n((F(2)) (x+); v1) ||02|12
=-n(VF(x;) - ve, vz) +
||eel -
2
Th (1 --m) || + 77 2
<
1/ VF(x))
29

---

Noting that 7/ S 1 21. then using the fact that min
arl,a?/22 2 |a|
2, vr E R,
T (1 L Lat)leea1
|
c²
110/11
|ee|
min
16L
2ca
2²
|
2
167.
2
|eel
16L
8L
which hence induces
e²
1
F(F++1) F(xe) S
well
1x
VF(x.)1
167.
8T.
4T.
Taking expectation both sides and using Lemma
4.3
gives
3c²
B|
B
([F(())
F(x441)]+
16L
8L
which indicates
1
T-1
Σ
Bl|e ||
<
(6LE(F((a)) - F(WT)]
Te + 6E
T
1=
16LAo
6c.
Te
By T 166LAe -2 we conclude
T-1 1 Fxx))l
E V(FT(()))
T 1=
T-1 1 T 0=
<
+ + (z()))))
< 7e.
is straightforward to see that the total number of samples is upper bounded by
T
(Mi M2r) O min 1/2 c )
30


Reviews:
[{"review_id": "e4mAmOSJsv", "reviewer": "Reviewer_bozm", "summary": "This work studies the problem of general stochastic non-convex optimization for $F(x)$ under the setting that the sampling process (randomness) follows a finite-state stationary Markov chain (MC), which has many applications in machine learning. It considers the case where only one trajectory is sampled and no restarts are allowed. The interaction protocol is through a stochastic first-order oracle, which returns unbiased and variance-bounded samples of the gradient ($\\mathbb{E} [g(x, s)] = \\nabla F(x)$), and the random seed $s$ is from the MC. This work then focuses on zero-respecting algorithms, where at each step $t$, the evaluation point $x_t$ can only be taken from previous points with non-zero gradients. This is a broad algorithm class which stochastic gradient descent and randomized extragradient fall in. First, a sample complexity lower bound of $\\Omega (\\epsilon^{-3})$ is proven, which is the first in the literature. Then, an algorithm, MaC-SPIDER, built upon a previous algorithm SPIDER, is proposed, and is shown that its upper bound is also $O (\\epsilon^{-3})$ up-to other factors such as the mixing time and the minimal stationary probability.", "questions": "Do you think the problem-dependent quantities of $\\tau_{mix}$ and $\\pi_{min}$ are necessary in the lower-bound (in the minimax sense)? Why is the specific value of $1/4$ chosen for the mixing time?", "limitations": "As the authors admitted, the setting of finite-state stationary MCs is restrictive. Though the dependence of $\\epsilon$ is tight, the necessity of other problem-dependent quantities is not discussed.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- **Important Problem:** This work advances the theoretical understanding of stochastic optimization, which is crucial for modern ML applications where i.i.d. assumptions often fail. The results could influence algorithm design in machine learning, both theoretically and practically.\n\n- **Fundamental Contribution:** First to establish matching (the gap being only problem-dependent constants) lower and upper bounds for single-trajectory Markovian optimization, filling an important gap in the literature.\n\n- **Technical Innovation:** Successfully adapts variance reduction to handle bias and temporal dependence in Markovian samples, which is non-trivial.\n\n\n### Weaknesses\n\n- **Lack of Intuitive Explanation:** Section 2.2 introduces many concepts, which may confuse readers not specialized in this problem. The authors did not provide enough explanations for these settings.\n\n- **Limited Scope:** Restricts to finite-state Markov chains, excluding many practical scenarios with continuous or countably infinite state spaces. Restricts to stationary MCs, limiting applicability to non-stationary settings.\n\n- **Lack of Numerical Simulation:** An experiment showing MaC-SPIDER is indeed converging faster than previous algorithms is missing.", "was_revised": true, "final_justification": "The authors' response addresses my concerns and improves the clarity of this paper. I'll keep my positve score.", "rebuttal": "## Response to \"Lack of Intuitive Explanation\"\nWe thank the reviewer for pointing out the clarification problem of Section 2.2. We will add more explanation in the final version and we also briefly explain it here for clarity. From high-level, one can think of the algorithm class considered in Section 2.2 has the following key properties: \n\n(1). For each $x$, one can calculate the per-sample first-order information (i.e., the gradient $g(x;s_i)$) with an arbitrary batch size (i.e., B can be arbitrary and time-varying);\n\n(2). For each iteration $t$ of the algorithm, there can be multiple query updates in $x$. For example, SGD with momentum lies in the class, since \n$$\nx_{t+1,1} = \\beta x_{t,1} + (1-\\beta)g(x_{t,2};s_t), ~~~~ x_{t+1, 2} = x_{t, 2} - \\eta x_{t+1, 1} .\n$$ \nAnd MaC-SPIDER is another example, where we have $x_{t, 1} = v_t$ and $x_{t, 2} = x_t$.\n\n\n(3). The update of next iteration in $x$ can use all history information, including history of all sampled gradients.\n\n(4). The algorithm is zero-respecting, meaning that the support of $x_t$ lies the union of supports of historical sampled gradients. This is a generalization to the linear span setting [Even’23, Beznosikov et al’24]. Moreover, we would like to note that for lower bound analysis with i.i.d. samples, similar assumptions on zero-respecting algorithms are placed [Arjevani et al’23].\n\nWe also show algorithms in Lines 138-142 which are exact examples fitting in the algorithm class we consider in Section 2.2.\n\n\n\n\n## Response to \"Limited Scope\"\nWe acknowledge finite state space and stationarity are the limitations of the paper. However, we would like to note that even for the finite-state, stationary case, to the best of our knowledge, this paper is the first work to establish an $\\epsilon^{-3}$ algorithm-independent lower bound for mean-squared smooth functions under Markovian samples, and it is also the first work which provides an algorithm under the same assumptions as those for the lower bound that achieves $\\epsilon^{-3}$ upper bound (up to some constant), showing its min-max optimality. We believe extending the current results to infinite-state and non-stationary cases is non-trivial, and we hope to put it in our future plan.\n\n## Response to \"Lack of Numerical Simulation\"\nDue to time limitation, we have only compared MaC-SPIDER with SGD under Markov sampling setting. And we would like to add more baseline algorithms in the final version. \n\nIn particular, we have run experiments under MNIST dataset with a customized Markov sampler. Each data point in the training split of MNIST is treated as a unique state, i.e., there are in total 60k states. The Markov sampler is defined to be sparse such that given the $i$-th data point is sampled, ten of the remaining data points have equal probability to be sampled in the next step of Markov chain evolution. We set $\\epsilon=0.05$ for both SGD and MaC-SPIDER. Then we choose the batch size of SGD by 500 (which is ~ $\\epsilon^{-2}$ as in literature) and let $M_1 = 500$ (~ $\\epsilon^{-2}$), $M_2 = 20$ (~$\\epsilon^{-1}$) as we indicate in the paper. For the learning rates, we set 0.02 for SGD and 0.5 for MaC-SPIDER. Our experimental results show that with the same amount of drawn samples, MaC-SPIDER achieves better performance than SGD. In other words, MaC-SPIDER has lower sample complexity than SGD. See the following table for detail. Moreover, as shown in the table, **with only 50k samples, MaC-SPIDER has achieved comparable performance as SGD with 90k samples**, which further indicates its sample efficiency and faster convergence. \n \n\n\n| Performance | SGD (50k samples) | MaC-SPIDER (50k samples) |SGD (90k samples) | MaC-SPIDER (90k samples) |\n|----------------|------------------|------------------|------------------|------------------|\n| Train Loss   | 0.8068    | 0.3454     | 0.3776    | 0.2691     |\n| Test Loss   | 0.7931     | 0.3305     | 0.3653     | 0.2571     |\n| Train Acc (%)   | 71.43| 89.53     | 89.01     | 91.91     |\n| Test Acc (%)   | 71.57     | **90.34**     | 89.49     | **92.47**     |\n\n\n## Response to \"Questions\"\n We appreciate the reviewer for the comment on problem-dependent quantities. From our current development of lower bound proof, we are unclear about whether lower bounds can be related to $\\tau_{mix}$ or $\\pi_{min}$ or both. In fact, relations among $\\tau$, $\\tau_{mix}$ and $\\pi_{min}$ vary a lot for different Markov chains. We would like to investigate their relationships and hope to develop lower bounds characterized by $\\tau_{mix}, \\pi_{min}$ in the future. \n\nIn terms of why choosing 1/4 for the mixing time, the reason follows it is conventionally adopted in Markov chain literature [Levin and Peres’17]. Choosing another value does not affect our results. In the second statement of Lemma D.1., it is shown that $t_{mix}(2^{-k}) \\le (k-1)t_{mix}(1/4), \\forall k \\ge 2$, i.e., different values only scale $\\tau_{mix}$ by some constant.\n\n\nReferences:\n\n[1]. Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference on Machine Learning, pages 9412–9439. PMLR, 2023.\n\n[2]. Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Advances in Neural Information Processing Systems, 36, 2024.\n\n[3]. Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood333 worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165–214, 2023.\n\n[4]. David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017."}, {"review_id": "mm7O5AE9Pv", "reviewer": "Reviewer_7A1K", "summary": "This paper looks at optimizing non-convex functions when data comes from a single Markov chain trajectory—no resets, no i.i.d. samples. That makes things harder due to data correlation. The authors prove a lower bound showing you need at least Ω(ϵ⁻³) samples in the best case. Then they propose MaC-SPIDER, a smart variance-reduced method that hits this bound (up to constants), making it nearly optimal. It’s the first method to do this using just one trajectory. The work is purely theoretical and highlights that it doesn't cover infinite or non-stationary chains.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Weakness:\n1. The novelty is limited. The paper extends known SPIDER-style variance reduction to the Markov setting, but the core idea is a relatively straightforward adaptation. The analysis borrows heavily from prior i.i.d. literature and lower bound techniques.\n\n2.The core technical difficulty (dealing with Markovian bias and variance) is acknowledged. The novelty is incremental.\n\n3. The method is motivated by practical problems like RL, but the paper does not test on any real or synthetic Markovian datasets to show relevance.\n\n4.The algorithm relies on mixing time and stationary distribution parameters, but how to estimate them or deal with their unknown nature?\n\n5. The technique can reduce variance, but how to handle the bias introduced by Markovian sampling?", "was_revised": true, "final_justification": "Thanks for the clarification. I've raised my score.", "rebuttal": "## Response to Weaknesses 1 and 2\nWe would like to argue that analysis of MaC-SPIDER is technically non-trivial, even though it algorithmically looks similar to SPIDER. In fact, the correlation among Markovian samples introduces much more difficulty in analyzing variance control using $v_t$. Particularly, Lemma 4.1 is the core result that we leverage to reduce variance. In the i.i.d. case, it is straightforward to obtain \n$\n\t\\mathbb{E}\\left\\Vert \\frac{1}{M} \\sum_{i=1}^M h(s_{t+i}) - h_{\\pi} \\right\\Vert^2 = \\frac{1}{M} \\sum_{i=1}^{M} \\mathbb{E}\\Vert h(s_{t+i}) - h_{\\pi} \\Vert^2\n$\ndue to independence across samples. However, for the Markovian case, this equation fails to hold. In particular, if simply using $\\Vert \\sum_{i=1}^M a_i \\Vert^2 \\le M \\sum_{i=1}^M \\Vert a_i \\Vert^2$, we only have $\\mathbb{E}\\left\\Vert \\frac{1}{M} \\sum_{i=1}^M h(s_{t+i}) - h_{\\pi} \\right\\Vert^2 = \\sum_{i=1}^{M} \\mathbb{E}\\Vert h(s_{t+i}) - h_{\\pi} \\Vert^2$, which makes the variance uncontrollable. Therefore, to obtain a tighter bound, we carefully analyze the correlation among Markov samples, combined further with the mixing theory of Markov chains, to finally obtain the results in Lemma 4.1. We would like to highlight again that deriving the variance bounds in Lemma 4.1 needs new mathematical tools that are not required for the i.i.d. setting. We refer the reviewer to Appendix D.1 for detailed proof.\n\nBesides much more difficulty in deriving Lemma 4.1, we further note that even with Lemma 4.1 ready to use, achieving $\\mathbb{E}\\Vert v_t - \\nabla F(x_t) \\Vert^2 \\le \\epsilon^2$ needs careful and technical analysis which is not required for the i.i.d. case. Specifically, in Line 898 in Appendix, the cross product term cannot be neglected (which is instead zero in the i.i.d. case), which thus induces more sophisticated analysis to achieve the final bound (see Lines 898-904 for more details). Therefore, we argue that the analysis is much more challenging and we indeed use new techniques and mathematical tools to deal with the challenge which is not encountered in the i.i.d. case. \n\nIn terms of the lower bound analysis, we acknowledge that we borrow the idea of function construction in [Arjevani et al’23]. However, we note that naively adopting i.i.d. analysis fails to obtain the lower bounds that depend on $\\tau$. In fact, our construction is more challenging in the following sense: Unlike the i.i.d. case considered in [Arjevani et al’23], where only unified, state-independent stochastic gradient $g$ are constructed, in our paper, due to inherent correlation across different states caused by Markovian property, we construct $g$ which is a function of states (see eq. (12) in Appendix B). Then a Markov chain is carefully designed (see Appendix A) such that combined with constructed $g$, making one increase in the number of non-zero elements (i.e., progress) at least takes $\\tau$ iterations (while noting that for the i.i.d. case making progress at least takes only one iteration [Arjevani et al’23]). In particular, we note that bounding the probability of progress in Lines 840-844 is totally different from the i.i.d. case, as Markovian samples are correlated. This distinguishes our analysis from classical lower bound analysis for the i.i.d. case. \n\n\n## Response to Weakness 3\nWe appreciate the reviewer for the suggestion on adding empirical evaluation. We have added the empirical results of MaC-SPIDER and SGD with Markov sampling MNIST dataset. We would like to add more experiments for real-world RL problems in the final version due to the time limit.\n\nIn particular, we have run experiments under MNIST dataset with a customized Markov sampler. Each data point in the training split of MNIST is treated as a unique state, i.e., there are in total 60k states. The Markov sampler is defined to be sparse such that given the $i$-th data point is sampled, ten of the remaining data points have equal probability to be sampled in the next step of Markov chain evolution. We set $\\epsilon=0.05$ for both SGD and MaC-SPIDER. Then we choose the batch size of SGD by 500 (which is ~ $\\epsilon^{-2}$ as in literature) and let $M_1 = 500$ (~ $\\epsilon^{-2}$), $M_2 = 20$ (~$\\epsilon^{-1}$) as we indicate in the paper. For the learning rates, we set 0.02 for SGD and 0.5 for MaC-SPIDER. Our experimental results show that with the same amount of drawn samples, MaC-SPIDER achieves better performance than SGD. In other words, MaC-SPIDER has lower sample complexity than SGD. See the following table for detail. Moreover, as shown in the table, **with only 50k samples, MaC-SPIDER has achieved comparable performance as SGD with 90k samples**, which further indicates its sample efficiency and faster convergence. \n \n\n| Performance | SGD (50k samples) | MaC-SPIDER (50k samples) |SGD (90k samples) | MaC-SPIDER (90k samples) |\n|----------------|------------------|------------------|------------------|------------------|\n| Train Loss   | 0.8068    | 0.3454     | 0.3776    | 0.2691     |\n| Test Loss   | 0.7931     | 0.3305     | 0.3653     | 0.2571     |\n| Train Acc (%)   | 71.43| 89.53     | 89.01     | 91.91     |\n| Test Acc (%)   | 71.57     | **90.34**     | 89.49     | **92.47**     |\n\n\n\n## Response to Weakness 4\nWe acknowledge that the implementation of our algorithm needs the information of the mixing time and the minimal element of $\\pi$. We note that if the upper and lower bounds of $\\tau_{mix}$ and $\\pi_{min}$, respectively, are known, (meaning we can upper bound $\\tau_{mix}\\pi_{min}^{-1/2}$) we can replace them by their corresponding bounds, which will not hurt the performance too much. Theoretically, by doing this, the sample complexity scales constantly (i.e., independent of $\\epsilon$) according to the bound of $\\tau_{mix}\\pi_{min}^{-1/2}$. Moreover, we argue that existing algorithms with Markov sampling require hyperparameters to be chosen with the knowledge of problem-dependent quantities. For example, for vanilla SGD, the learning rate is chosen as $\\mathcal{O}(1/(\\tau_{mix}\\log T))$ [Even’23]; for Randomized GD, the batch size is set as $\\mathcal{O}(\\tau_{mix}\\sqrt{T})$ [Beznosikov et al’24]. We further note that the convergence results of the above-mentioned two algorithms are placed under a stronger bounded noise assumption, i.e., $\\Vert g(x;s) - \\nabla F(x) \\Vert \\le \\sigma$ rather than the bounded variance assumption $\\mathbb{E}\\Vert g(x;s) - \\nabla F(x) \\Vert^2 \\le \\sigma^2$ in our paper. If considering the same bounded noise assumption, our convergence results can further get rid of the dependence on $\\pi_{min}$. That is to say, **our algorithm needs exactly the same knowledge of problem-dependent quantities as in literature**. Furthermore, when considering the bounded variance assumption (which is the focus of this paper), we present a simple way to estimate $\\pi_{min}$, which can be plugged into MaC-SPIDER easily. The idea is to maintain a vector $y \\in \\mathbb{R}^{|\\mathcal{S}|}$, where $y(s) = \\sum_{i=1}^{N} h(s_i) / N$ with $h$ being the indicator function, and N being the number of total samples. By Lemma 4.1, it is straightforward to obtain $y \\to \\pi$ as $N \\to \\infty$ and hence $\\min_s y(s) \\to \\pi_{min}$. Therefore, by plugging in estimate $y$, we can get rid of knowing $\\pi_{min}$.\n\n\n## Response to Weakness 5\nWe note that although Markovian samples are biased, asymptotically there is no bias due to the mixing property of Markov chains. In Theorem 4.4, we show that for arbitrary small $\\epsilon$, MaC-SPIDER can output a $\\tilde{x}_T$ such that $\\Vert \\nabla F(\\tilde{x}_T) \\Vert \\le 7\\epsilon$, which indicates MaC-SPIDER has no bias while preserves variance reduction. \n\n\n**References**\n\n[1] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood333 worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165–214, 2023.\n\n[2] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Advances in Neural Information Processing Systems, 36, 2024."}, {"review_id": "02zz9GZcqg", "reviewer": "Reviewer_obPR", "summary": "This paper studies stochastic non-convex optimization with samples from a single uncontrolled Markov chain. It establishes an $\\Omega(\\epsilon^{-3})$ lower bound under the mean-squared smoothness assumption and an $\\Omega(\\epsilon^{-4})$ bound without it. The proposed MaC-SPIDER algorithm matches these bounds, achieving near-optimal sample complexity.", "questions": "(1) In Remark 4.5, we see that there is still a gap between $\\tau$ and $\\pi_{min}^{1/2}\\tau_{mix}$. Could you provide a concrete example to show this gap?\n\n(2) Could you provide any empirical validation?\n\n(3) What result does MaC-SPIDER have without the mean-squared smooth assumption? Can it also match the lower bound?", "limitations": "Yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well presented. It proposes a new algorithm based on the variance reduction (SPIDER) algorithm in optimization for the setting of learning from a single Markov chain. Lower bound analysis shows that the result is nearly minimax optimal.\n\nWeaknesses:\n\n(1) The abstract and the introduction are inconsistent: the lower bound in the abstract is $\\epsilon^{-3}$, while that in the intro is $\\epsilon^{-4}$.\n\n(2) There are some typos in the sample complexity definition (equation 6, the left part should depend on both $\\bar L$ and $L$). Moreover, it’s hard for me to understand the meaning of this metric. For example, it is not clear to me what the final infimum is taken over. Could you clarify more about its definition?\n\n(3) The algorithm requires prior knowledge of some parameters like $\\pi_{min}$ and $\\tau_{\\min}$, which is hard to know in advance.", "was_revised": true, "final_justification": "The rebuttal addresses my concerns. Thus, I lean towards acceptance.", "rebuttal": "## Response to Weakness 1\nWe appreciate the reviewer for the comment. Actually, lower bounds of $\\epsilon^{-3}$ and $\\epsilon^{-4}$ are established under different settings, and hence there is no contradiction. For $\\mathbf{\\epsilon^{-4}}$, we only require $F$ to be **smooth**, while for $\\mathbf{\\epsilon^{-3}}$, we further need **mean-squared smoothness**, i.e., Assumption 2.4, which is also a widely-adopted assumption for variance reduction analysis of the i.i.d. case. Obviously, mean-squared smoothness indicates classical smoothness, meaning $\\epsilon^{-3}$ lower bound is established under a smaller function class. Specifically, in the statement of Theorem 3.1 we clarify different settings under which two lower bounds are proved. We will further clarify their differences in the final version to avoid any misunderstanding.\n\n\n## Response to Weakness 2\nYes, the left part of eq. (6) also depends on $L$ and we will add it in the final version. In terms of the complexity measure, we explain its meaning as follows: First, the final infimum means the minimum number of samples are drawn when the gradient norm of $F$ evaluated at all historical outputs of algorithm $\\mathcal{A}$ for the first time becomes less than $\\epsilon$, i.e., optimality criterion is reached. Then, if we lower bound that measure by some $N$, then we basically conclude that there exist some $\\pi$, some $F, g$ (due to supremum) such that for any algorithm (due to infimum), the minimum number of samples to be drawn for the algorithm to achieve arbitrarily small gradient norm for the first time is at least $N$. This establishes the meaning of algorithm-independent sample complexity lower bound. See Lines 185-191 for discussions as well. \n\n\n## Response to Weakness 3\nWe acknowledge that the implementation of $\\pi_min$ and $\\tau_{mix}$. However, we note that for existing algorithms in literature, the knowledge of these problem-dependent quantities are unavoidable for algorithm design.  For example, for vanilla SGD, the learning rate is chosen as $\\mathcal{O}(1/(\\tau_{mix}\\log T))$ [Even’23]; for Randomized GD, the batch size is set as $\\mathcal{O}(\\tau_{mix}\\sqrt{T})$ [Beznosikov et al’24]. It is also worth noting that convergence results of the above-mentioned algorithms are established on a stronger assumption $\\Vert g(x;s) - \\nabla F(x) \\Vert \\le \\sigma, \\forall s$ rather than the one we consider in this paper (see Assumption 2.3). In fact, when assuming $\\Vert g(x;s) - \\nabla F(x) \\Vert \\le \\sigma, \\forall s$, we can get rid of the dependence of $\\pi_{min}$ in Theorem 4.4. This guarantees that **our algorithm needs exactly the same knowledge of problem-dependent quantities as in literature**. Furthermore, even under Assumption 2.3, we have a practical way to estimate $\\pi_{min}$. Specifically, the idea is to maintain a vector $y \\in \\mathbb{R}^{|\\mathcal{S}|}$, where $y(s) = \\sum_{i=1}^{N} h(s_i) / N$ with $h$ being the indicator function, and N being the number of total samples. By Lemma 4.1, it is straightforward to obtain $y \\to \\pi$ as $N \\to \\infty$ and hence $\\min y(s) \\to \\pi_{min}$. Therefore, by utilizing estimate $y$, we can get rid of knowing $\\pi_{min}$.\n\n\n## Response to Question 1\nFor example, if we consider directed cycle with self-loop, i.e., for state $i$, it has probability $1/2$ staying at the current state or transiting to $i+1$ mod $n$, where $n$ is the number of states, the hitting time is $2n$. The mixing time of this chain is $\\Theta(n^2)$ and $\\pi_i = 1/n, \\forall i$. Therefore, the gap is $\\Theta(n^{3/2})$.\n\n\n## Response to Question 2\nWe appreciate the reviewer for the suggestion on empirical validation. We have added the empirical comparison between SGD and MaC-SPIDER with Markov sampling. And we are willing to add more baselines in the final version.\n\nIn particular, we have run experiments under MNIST dataset with a customized Markov sampler. Each data point in the training split of MNIST is treated as a unique state, i.e., there are in total 60k states. The Markov sampler is defined to be sparse such that given the $i$-th data point is sampled, ten of the remaining data points have equal probability to be sampled in the next step of Markov chain evolution. We set $\\epsilon=0.05$ for both SGD and MaC-SPIDER. Then we choose the batch size of SGD by 500 (which is ~ $\\epsilon^{-2}$ as in literature) and let $M_1 = 500$ (~ $\\epsilon^{-2}$), $M_2 = 20$ (~$\\epsilon^{-1}$) as we indicate in the paper. For the learning rates, we set 0.02 for SGD and 0.5 for MaC-SPIDER. Our experimental results show that with the same amount of drawn samples, MaC-SPIDER achieves better performance than SGD. In other words, MaC-SPIDER has lower sample complexity than SGD. See the following table for detail. Moreover, as shown in the table, **with only 50k samples, MaC-SPIDER has achieved comparable performance as SGD with 90k samples**, which further indicates its sample efficiency and faster convergence. \n \n| Performance | SGD (50k samples) | MaC-SPIDER (50k samples) |SGD (90k samples) | MaC-SPIDER (90k samples) |\n|----------------|------------------|------------------|------------------|------------------|\n| Train Loss   | 0.8068    | 0.3454     | 0.3776    | 0.2691     |\n| Test Loss   | 0.7931     | 0.3305     | 0.3653     | 0.2571     |\n| Train Acc (%)   | 71.43| 89.53     | 89.01     | 91.91     |\n| Test Acc (%)   | 71.57     | **90.34**     | 89.49     | **92.47**     |\n\n\n## Response to Question 3\nWithout assuming mean-squared smoothness, the upper bound of MaC-SPIDER becomes $\\tau_{mix} \\pi_{min} \\epsilon^{-4}$. We note that this $\\epsilon^{-4}$ result matches the first lower bound in Theorem 3.1, since now only smoothness assumption of $F$ is placed, i.e., MaC-SPIDER is still nearly min-max optimal for smooth (but not mean-squared smooth) functions. This also guarantees that without mean-squared smoothness, it is impossible for MaC-SPIDER to achieve $\\epsilon^{-3}$ complexity. In fact, mean-squared smoothness is a common assumption to achieve $\\epsilon^{-3}$ complexity in variance reduction literature for the i.i.d. case. \n\n\n**References**\n\n[1]. Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference on Machine Learning, pages 9412–9439. PMLR, 2023.\n\n[2]. Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Advances in Neural Information Processing Systems, 36, 2024."}, {"review_id": "lXSPqmQfLg", "reviewer": "Reviewer_2E35", "summary": "This paper explores a general stochastic non-convex optimization problem, which lies outside the scope of my current research expertise and academic focus. As such, I do not feel adequately qualified to provide a fair and informed evaluation of the technical contributions and significance of the work. I respectfully request that my review be disregarded in the decision-making process, and that greater consideration be given to the assessments provided by reviewers with relevant expertise in this area.", "questions": "This paper explores a general stochastic non-convex optimization problem, which lies outside the scope of my current research expertise and academic focus. As such, I do not feel adequately qualified to provide a fair and informed evaluation of the technical contributions and significance of the work. I respectfully request that my review be disregarded in the decision-making process, and that greater consideration be given to the assessments provided by reviewers with relevant expertise in this area.", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper explores a general stochastic non-convex optimization problem, which lies outside the scope of my current research expertise and academic focus. As such, I do not feel adequately qualified to provide a fair and informed evaluation of the technical contributions and significance of the work. I respectfully request that my review be disregarded in the decision-making process, and that greater consideration be given to the assessments provided by reviewers with relevant expertise in this area.", "was_revised": true, "final_justification": "This paper is out of the scope of my research area. Please ignore my review and consider the reviews from other reviewers. Please find other reviewers and assign this paper to them.", "rebuttal": "We appreciate the reviewer for the kind review."}]

Author rebuttal:

Meta-review: The paper studies stochastic non-convex optimization when samples are generated by a finite-state stationary Markov chain (MC). The authors derive lower bounds on the sample complexity for this setting, then adapt the SPIDER algorithm and show that the resulting method, MaC-SPIDER, achieves performance close to the lower bound, up to terms involving the mixing time and the minimal state visitation probability.

The reviewers acknowledge the theoretical contribution, which goes beyond the standard i.i.d. assumption. That said, several issues should be addressed to strengthen the manuscript:

•	Motivation and experiments. The paper does not present a compelling real-world motivation; the rebuttal offered only a toy example of Markovian data. The experimental results in the reubttal are limited to classical SGD. Please compare against algorithms designed for dependent/Markovian data from the literature.
•	Novelty and related work. The algorithmic novelty appears modest (MaC-SPIDER is largely an adaptation of SPIDER), and the analysis relies on a few concentration results for Markov chains. A related-work discussion on this topic should be included, for example, to include established concentration results for MCs (e.g., Paulin, 2015).

•	Unknown parameters. The method assumes knowledge of the mixing time and the minimal visitation probability. The rebuttal’s asymptotic argument is insufficient from a sample-complexity standpoint (just mentioning an asymptotic argument of convergence  is not enough when considering sample complexity). Please discuss how much samples do we need to estimate these quantities (see e.g., Wolfer and Kontorovich papers) and explain what would be the impact on the results.

•	Presentation and correctness. The exposition can be significantly improved; e.g., the definition of mixing time is currently incorrect and should be fixed.
Decision: Accept (poster)