Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling

Comments on subsampling: We really appreciate the reviewer for initiating such an interesting discussion. In the following we briefly present our understanding and hopefully would provide some insights to the comments. We think the reviewer’s intuition is correct and is aligned with ours. However, we would like to emphasize that simply using a subsampled sequence might not be enough to achieve the same rate as MaC-SAGE. This is because even under the i.i.d. case, vanilla SGD suffers from a slower rate. In other words, to get a faster rate as MaC-SAGE, variance-reduced techniques are needed. For the finite-state case, the main difference between the Markov sampling and uniform sampling (i.e., finite-sum for the i.i.d. case considered in literature) lies in that the stationary distribution $\Pi$ is unknown and non-uniform, which makes its estimation necessary before applying existing algorithms designed for the i.i.d. case. Once it is guaranteed that the estimate of the stationary distribution converges no slower than the algorithm’s rate in the i.i.d. case, one can directly apply algorithms for the i.i.d. case (e.g. SAG, SVRG) to the Markovian case with the final rate scaled by $\tau$. That is also the idea behind MaC-SAGE, where we maintain $y_t$ as an estimate of $\Pi$. Also please refer to lines 300-310 on the right column for discussions. Finally, it is worth noting that the analysis for the Markovian case is non-trivial because of the correlation among time-dependent samples, although algorithmically the rate seems similar (up to $\tau$) to the i.i.d. case.

Q1: We thank the reviewer for bringing this to our attention. Actually, we are able to weaken such a strong assumption by now taking the expectation according to the stationary distribution $\Pi$, i.e., $\mathbb{E}_{s \sim \Pi}\Vert g(x;s) - \nabla F(x) \Vert \le \sigma^2$, which is then similar to the bounded variance in i.i.d. setting. We note that considering this modified assumption does not affect our lower bound results (i.e., Theorem 3.1 still holds), as the proof of Lemma A.3 holds for any distribution of the chain.

Q2: The stepsize $\gamma_t$ is chosen as line 1026, which only needs the knowledge of hitting time. We will add its expression to the main text in our updated version.

Q3: We think our proof techniques could be used to obtain high-probability results. Specifically, in Appendix A.3, eq. (19) holds almost surely, which hence indicates line 652 holds almost surely. Therefore, Theorem 4.2 is valid with probability one. For Theorem 3.1, similarly, we have shown Lemma 5.2, which is a high-probability result (see line 799 for details). In the proof, we set $\delta = 0.5$ to get the final expectation bound (see lines 810-814). Thus, if we leave $\delta$ as a parameter, a high-probability version can be characterized.

Response to "Theoretical Claims"

1. The proof of Theorem B.3: We think the proof of Theorem B.3 is correct and we will add details in the updated version. We detailedly explain how line 912 is derived as follows:

First, we derive line 907 from line 906: Denoting $v_{max} := \max_i \Vert v(i) \Vert_{\infty}$, we have

where due to display issue, we use $\vert A \vert_{i,j}$ to denote $|a_{ij}|$.

Since by definition of the matrix infinity norm (i.e., for matrix $A$, $\Vert A \Vert_{\infty} := \max_i \sum_j |a_{ij}|$), for any $i$, $\sum_j | P - \mathbf{1}\Pi^T \mid_{i,j} \le \Vert P - 1\Pi^T \Vert_{\infty}$, then we conclude line 907 by further noting $v_{max}^2 = \max_i \Vert v(i) \Vert_{\infty}^2$ and $\sum_i \pi_i = 1$.

Then, note that for finite-state case, since Lemma B.2 holds for any initial distribution $\mu$, setting $\mu = 1_{s_0 = i}$, meaning the chain starts from state $i$ with probability one, it yields that

Moreover, by definition of total variation distance, i.e., $d_{TV}(p,q) := (1/2) \sum_{z}|p(z) - q(z)|$, we conclude $\Vert P^k - \mathbf{1}\Pi^T \Vert_{\infty} = 2 \max_{i} d_{TV}(P^k(\cdot \mid s_0=i), \Pi)$. Combining all these facts gives the second term of line 912.

To see the first term of line 912, which is the bound for the first term in (23), we simply set $k=0$ for line 900, which hence is bounded by $\max_i \Vert v(i) \Vert_{\infty}^2 \Vert I - \mathbf{1}\Pi^T \Vert_{\infty}$.

2. Typo in Corollary B.4: We apologize for that typo. The second bound in Corollary B.4 should not depend on $\sigma$ and we will fix it in the updated version.

Response to "Other Strengths And Weaknesses"

About the cardinality of finite state space on the results: We note that the hitting time in Theorem 4.2 is usually a function of the cardinality of the state space in practice. That is to say the number of states affects the sample complexity by means of the hitting time captured in our theorem. How the cardinality relates to hitting time varies case by case.

Response to "Other Comments Or Suggestions"

1. Typo on line 595: We apologize for the typo. We will fix it in the updated version.

2. Notation of $g$: In the paper, we consistently define $g(x;s) = \nabla f(x;s)$, i.e., $g$ is the first-order stochastic gradient sampling from the Markov chain. In the updated version, we will clarify such notations for easy understanding.

3. Notation in Lemma A.2: We will drop all subscripts of $t$ in the updated version.

4. About Assumption 4.1: There is no expectation on the norm, saying the bound is assumed to hold almost surely. That also distinguishes the construction for the finite-state case from the countable-state case. Please refer to lines 282-292 for detailed discussion.

Response to "Questions for Authors"

We note that in our construction, the cardinality of the finite Markov chain is $\Omega(\tau)$ due to the fact that there are at least $\tau$ states between $v^*$ and $s^*$ (see Figure 1). Since the hitting time of the chain is usually a function of the cardinality, our bound hence implicitly depends on the state space cardinality.

1. By using $:=$, we actually define $g(\theta; s, s’) := (\phi(s)^T \theta - r(s, s’) - \gamma \phi(s’)^T \theta)\phi(s)$.

2. We will fix it in the updated version.

3. We thank the reviewer for the suggestion. By our notation, we mean $x_{t,i}$ being the $i$-th point at $t$-th iteration, whose dimension is $d$. We denote $x_t$ just for a collection of all updated points $x_{t,1},\dots, x_{t,M}$. And when $M=1$, $x_t = x_{t,1}$. The reason we define such multiple points of query is to include a broader class of algorithms, e.g., momentum-based algorithms. We present the example of Randomized ExtraGradient in line 204, where $M=2$, meaning two points are maintained to update at every iteration. In the updated version, we will clarify further clarify it.

4. In our setting, the support of a vector means the collection of all non-zero coordinates, i.e., $support(x)= \\{ i : x[i] \ne 0, \forall 1 \le i \le d \\}$.

5. We apologize for the typo. $x_{t+1/2}$ should be used in the update of $x_{t+1}$ in line 206. We will fix it in the updated version.

6. We apologize for the typo of missing $\inf$. We will fix it in the updated version.

7. We will fix it in the updated version.

8. By the definition of $N_s^{\epsilon}$, to ensure $N_s^{\epsilon} \ge N_T$ with $N_T$ being some constant, we only need to guarantee 1) the existence of an oracle (due to $\sup$ over $O_s$); 2) the existence of a function (due to $\sup$ over $\mathcal{F}$); 3) for any algorithm $\mathcal{A}$ (due to $\inf$ over $\mathbf{A}_{zr}$), 4) the smallest number of samples used by $\mathcal{A}$ causes its output leading to the expectation of the gradient norm firstly lies below the level of $\epsilon$.

9. Denote $\tilde{x}_T$ as the point which realizes the minimization, i.e., $\tilde{x}_T \in arg \min E\Vert \nabla F(x_t) \Vert^2$. Then, in order to force $\mathbb{E}\Vert \tilde{x}_T \Vert \le \epsilon$, it suffices to force $\mathbb{E}\Vert \tilde{x}_T \Vert^2 \le \epsilon^2$. Setting the bound on the right hand side of Theorem 4.4 gives that $T = \tilde{O}(\tau \epsilon^{-2})$. Moreover, since only one sample is drawn at each iteration, it concludes the sample complexity of Algorithm 1 is $\tilde{O}(\tau \epsilon^{-2})$.

10. We appreciate the reviewer’s suggestion. We will provide more detailed explanations of the algorithm class in the updated version. Roughly speaking, the algorithm class we consider in the paper captures almost all popular first-order methods in literature. At every iteration, the algorithm is allowed to take all histories of previous samples and $x_0,\dots, x_t$ to generate $x_{t+1}$ following (5) which is satisfied by almost all first-order methods in literature. Note that (5) generalizes [Even’23] where $x_{t+1}$ is linearly spanned by previous points and sampled gradients.

Q1. The core difference lies in how the stochastic gradient $g$ is constructed in the two settings. Assumption 2.2 for countable-state chains is weaker than Assumption 4.1 for the finite case (see lines 282–292). To address this, we design a countable-state Markov chain (Figure 2) by splitting $v^*, w^*$ into substates $v_1^*, v_2^*, w_1^*, w_2^*$ and define $g$ via (20). Unlike the finite case (Figure 1), where the transition from the parent of $v^*$ to $v^*$ happens with probability one, in the countable case, $v_1^*, v_2^*$ share the same parent, and the transition splits probabilistically: to $v_1^*$ with probability $q$, and to $v_2^*$ with $1-q$. Equivalently, the chain transitions to $v^*$, then flips a coin to select $v_1^*$ or $v_2^*$. This added randomness, combined with (20), makes the event “$prog_0(x)$ increases by one” succeed with probability $q$ (as shown in Lemma 5.2). As a result, more samples are needed—compared to the finite case—to ensure $prog_0(x) = d$ and hence $\Vert \nabla F(x) \Vert$ is sufficiently small. See lines 333–359 for details.

Q2. The main reason of considering different oracles is to bridge the gap between our lower bounds and upper bounds for different settings. Essentially we are searching for tight bounds under different settings. While we could get $\epsilon^{-4}$ for the finite case under a more general Assumption 2.2, we aim to prove that an improved bound $\epsilon^{-2}$ is tight under a more specific/easier setting for the finite state space case. This is both motivated by practical consideration and also the existing upper bounds. Then we propose a new algorithm such that the sample complexity can be improved to $\epsilon^{-2}$ under such a stricter but practical Markov-chain class further with the matching lower bound.

Q3. Please refer to Q1.

Q4. We note the hitting time is a function of the number of states which is different for different Markov chains. Therefore, the convergence rate of MaC-SAGE is affected case by case.

We sincerely thank the reviewer for positive and encouraging comments on our paper. In our updated version, we will promote the writing to make it clearer and easier to follow for the readers.

For zero-respecting algorithms we consider in the paper, we note that zero-respecting algorithms require the initial point $x_0$ to be zero, i.e., $x_0 = 0$ due to (5). That is to say random initialization is not allowed for zero-respecting algorithms. However, it is worth noting that such limitation on the initialization is also seen in lower bound analysis of literature [Even’23, Arjevani et al’23, Beznosikov et al’24, Duchi et al’12] and it does not affect the convergence result of the algorithm. We are willing to generalize our results to randomized algorithms in the future.

About extension to bounded gradient assumption: We appreciate the reviewer’s suggestion. Extension to bounded gradient case is interesting and we hope to address it in the future. Also we would like to note that smoothness is a common assumption for convergence analysis in optimization literature [Ghadimi and Lan’13, Even’23, Roy et al’22, Dorfman and Levy’22]. Therefore, our results are applicable for optimization problems under standard assumptions.

TC1: After double-checking, we modified the theorem. Now the rate scales with $\max ( \tau_{mix},\tau_{hit})$, but note MaC-SAGE remains optimal (up to constants).

TC2: We clarify that we are not claiming $B_l$s are i.i.d. Bernoulli r.v., but we claim $z_i$s (see its definition in the following) are i.i.d. Bernoulli r.v. We explain it as follows: First, we construct a Markov chain in which there are two states $v^*, w^*$ such that $\tau/2$ steps must be taken to commute each other. Then, we further introduce randomness in states $v^*, w^*$ to make sure that in the ideal case, when $\tau/2$ steps are taken, the event “$prog_0(x)$ increases by one” happens with probability at most $q$. To do this, we split $v^*$ (and $w^*$) into two substates $v_1^*, v_2^*$ (and $w_1^*, w_2^*$) and construct the gradient by (20). By Lemma A.2, every $\Omega(\tau)$ steps there is at most one $B_l$ being one, with its succeeding probability (if it could) at most $q$. To see line 790, in the ideal case, at least $\tau / 2$ steps are needed to increase $prog_0(x)$ by one and this becomes possibly true with probability at most $q$. That is to say, when $v^*$ or $w^*$ is visited, a coin is flipped where the flip’s result determines whether or not the event “$prog_0(x)$ increases by one” succeeds. And also the results of coin flips are independent across every time when $v^*$ or $w^*$ is visited. Therefore, $z_i$s record the results of coin flips, which are i.i.d.

TC3: To highlight novelty: [Even’23] assumes uniform stationary distribution $\pi$ ($\pi_i = 1/n$), while [Powell & Lyu’24] require prior knowledge of $\pi$. In contrast, MaC-SAGE requires no information about $\pi$ and allows it to be non-uniform. We design $y_t$ to estimate $\pi$ and address this challenge.

W1: We explain our construction of Markov chains by referring to Figures 1,2. Actually, transition probabilities are not critical for proving lower bounds; only the chain's structure matters. In the countable-state case (Figure 2), for the $S\setminus S’$ part (orange circle), starting from $v^*$ (union of $v_1^*, v_2^*$, red dashed circle), the chain can move only in one direction until hitting $s^*$; similarly for $s^*$ to $v^*$. The number of states along each path between $v^*$ and $s^*$ is $\tau/2$. The structure of the subchain in $S’$ (blue circle) is flexible—for example, it may be a complete graph. This construction ensures commuting between $v^*$ and $w^*$ requires at least $\tau/2$ steps, while maintaining ergodicity of the chain.

The substates $v_1^*, v_2^*$ lie within $v^*$, and similarly for $w^*$. Figure 2 shows: 1) exactly one common parent state of $v_1^*, v_2^*$; 2) conditioned on the parent, transition to $v_1^*$ happens with probability $q$, and to $v_2^*$ with $1 - q$. It is equivalent that, upon reaching $v^*$, a coin is flipped to determine $v_1^*$ (w.p. $q$) or $v_2^*$ (w.p. $1-q$). The conditional probability below (20) defines this flip.

W2: The constructed Markov chain and $f$ in (16) force any algorithm to iterate at least $\Omega(\tau)$ steps to make an increase in $prog_0(x)$. Then by Lemma 5.1, $\Omega(\tau d)$ samples are needed to make $\nabla F$ small (see lines 360-380). To see boundedness of hitting time, we note by our construction, as long as the hitting time of the subchain supported on $S’$ (blue circle) is $O(\tau)$, due to hitting time of the subchain in orange circle is $O(\tau)$, the hitting time of the whole chain is $O(\tau)$.

Q1: We note our lower bounds rely on hitting time, which is a function of cardinality of (finite) state space. Due to space limit, please refer to responses to Q1&2 of Reviewer eLLJ about differences and reasons of separating Theorems 3.1&4.2.

Q2: We acknowledge the limitation in finite hitting time assumption. We explain the idea how to construct a chain with bounded mixing time and hope to show it in future. First we design a cyclic-like subchain in orange circle with the number of states between $v^*$ and $s^*$ being $O(\sqrt{\tau})$. Second, we consider any subchain in blue circle whose mixing time is $O(\tau)$. If we restrict on the orange or blue subchain, we have the mixing times of them are $O(\tau)$. Then the mixing time of the composed chain is upper bounded by the larger mixing time of the orange or blue component. This is shown by [Madras&Randall’02] for reversible chains, while we conjecture it is also true for non-reversible chains.

[1].Madras, Neal, and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability,2002.

Q3: We acknowledge our proof techniques only suit stationary chains. But we note that many applications (e.g. TD learning, RL) belong to stationary case. And we highlight it is the first time improved lower bounds are provided for Markov sampling, with a new algorithm showing optimality of our bounds. Extending to non-stationary case is interesting and we hope to address it in future.