Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes an asymptotic analysis of SGD when the noise sequence is not necessarily iid but can be a Markov chain such as a random walk over an arbitrary graph. The main contribution of this work is to connect the concept of efficiency ordering (which was previously introduced in the literature to compare Markov chains with the same stationary distribution and hence compare MCMC algorithms) with an ordering of covariance matrices inherited from Central Limit Theorems controlling rescaled SGD iterates driven by Markov chain noise sequences. As a consequence, SGD algorithms can achieve smaller covariance errors when using more efficient noise sequences for MCMC sampling. As applications of this result, the paper considers decentralized optimization over a graph using high-order random walks for SGD on the one hand and (mini-batch) gradient descent with shuffling on the other hand, confirming the superiority of these mechanisms as previously noticed in the literature. The paper also notably shows how some non-Markovian processes (for which non-asymptotic analysis are not available in the literature) can outperform Markovian input sequences for SGD in terms of efficiency ordering. Numerical experiments illustrate the theoretical findings.
strengths_and_weaknesses: — STRENGTHS: 

1. The paper states that the covariance matrices associated to two random walks following an efficiency ordering are Loewner ordered even for non-Markovian stochastic processes. This is an advantage of the asymptotic approach compared to its non-asymptotic counterpart which cannot handle the non-Markovian setting for which the mixing time is irrelevant beyond the Markovian noise setting (see a clarification question regarding this point in the next section below). Moreover, the result implies that better MCMC samplers could be used to enhance SGD thanks to the connection between AV for MCMC and covariance matrices for SGD algorithms from CLT. The paper hence establishes an interesting connection between the MCMC literature and the asymptotic covariance associated to (rescaled) SGD iterates (using the same noise sequence). 

2. The comparison between shuffling and iid input sequence and the use of shuffling in mini-batch gradient descent are interesting questions even in practice and prior work has observed and established some advantages of these techniques. The present work compares them using an alternative asymptotic point of view compared to the more common non-asymptotic (finite-time bounds) in the literature relying on mixing times.  

3. The paper also extends prior art regarding applications. For instance, it shows that a high-order random walk (NBRW) which is non-Markov is more efficient than SRW for SGD on general graphs beyond d-regular graphs for which this was previously established using mixing times. It also confirms some known advantages of shuffling over iid sampling for SGD and addresses a class of functions (verifying (A2)) that is not covered by prior work. 

4. Clarity: the paper is well-written and the contributions are clearly stated. The results are sound and the paper is technically solid (I only quickly went through appendices A, C (checked the proof of the main result) and D though). 

— WEAKNESSES:

1.  Unlike the asymptotic approach, a non-asymptotic analysis captures the dependence on constants of the problem such as the data and the graph topology in the distributed optimization setting. 

2. Among other experimental facts, two main elements are presented as motivation to consider asymptotic variance as a tool for the analysis. First, the paper mentions the connexion of AV with the MSE. Nevertheless, this connexion between finite-time MSE and the covariance matrix does not seem to be straightforward beyond the case of quadratic objective functions (or linear stochastic approximation) which is well understood in the literature with existing thorough non-asymptotic analysis (for e.g. [18, 45] as mentioned in the paper). Second, the paper also mentions confidence intervals: although a smaller covariance matrix indeed reduces the confidence interval length, this covariance matrix depends on the Hessian at the minimizer which is unknown. Hence, it is hard to exploit the asymptotic analysis in practice, although this may not be the main purpose of the paper regarding this confidence interval remark. 

3. The asymptotic analysis seems to provide little additional actionable information compared to the non-asymptotic approach. In l. 112-117, the paper mentions that the asymptotic variance provides more information than non-asymptotic MSE bounds, but is this information usable in practice? Can we leverage this additional information to improve the algorithms easily beyond the case where we already have a more efficient sequence (in the sense of the MC ordering) at hand? Also, for instance, in the paper, if the asymptotic analysis addresses a different class of functions (satisfying (A2)) which does not include PL functions (as previously addressed in the literature), it only confirms previously known facts regarding shuffling for SGD for which more informative finite-time bounds exist as stated by the paper (l. 323). 

4. Using Theorem 3.6 may not be easy in general, one needs to know an efficiency ordering of two sequences to transfer it to SGD. Is the problem of determining the efficiency ordering between two sequences easier than comparing the covariance matrices inherited from the CLT corresponding to SGD with the two different noise sequences? (see question in the next section)

5. Technical significance: The main contribution of the paper as highlighted by the paper is Theorem 3.6. From the technical point of view, this result follows from the definition of the asymptotic variance of the Markov chain in one direction and from the well-known explicit integral form of the covariance matrix together with the stability of the Loewner ordering (Lemma D.2) for the converse (Appendix, p.6). Compared to the proof of this main result, the applications require more technical work. As acknowledged by the authors (especially in the appendix), CLTs are known in the literature, even for general stochastic approximation schemes driven by Markovian noise, of which SGD with Markov noise is a particular case. The paper relies on this prior work for the CLT. 
questions: 1. Regarding the main contribution (Theorem 3.6), in general, is showing that the AV is small easier than controlling the asymptotic covariance from the CLT? The applications (Props. 4.1 to 4.4) seem to exploit previously known efficiency ordering from the MCMC literature and transfer them to SGD using Theorem 3.6 whereas these last results (from the MCMC literature) may not be easy to establish in general. 

2. The example of Fig. 1 is interesting and motivates looking at the AV as a metric for ordering instead of SLEM. However, I am wondering if one can also find an example where the converse holds, i.e. where SLEM may be more relevant if this makes sense. I understand that the point in the paper is to motivate looking at AV but commenting on the converse would also be interesting to complete the picture for the reader regarding the comparison between the asymptotic approach and its non-asymptotic counterpart. 

3. In the contributions, it is stated that the analysis covers non-Markovian stochastic processes beyond Markovian sequences. The example in p. 7 is a second-order Markov chain (which is non-Markov) and it is analyzed via an augmented process which is a Markov chain. Could one also use non-asymptotic analysis based on the mixing time for this same augmented process? This type of approach does not seem to be out of reach for this specific kind of non-Markovian process compared to the asymptotic approach pursued in the paper. 

Typos: 
- l. 188: (A2), what is a? It should rather be \alpha defining the step size in (A1) I guess. 
- l. 364-365: what are f and g? Is it \tilde{f} and \hat{f} instead?
limitations: Limitations are not explicitly discussed by the paper (as acknowledged by the authors in the checklist in Question1. b). Some comments and questions regarding limitations of the work are discussed in the section above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors introduce the notion of efficiency ordering to classify stochastic algorithms.
They claim that some non-Markovian dynamics are more efficient that the Markovian ones for SGD.

strengths_and_weaknesses: The paper is unclear, and the claims seem to overstate the results in general.
The figures present data which are far from convincing.
In particular, the numerical experiment made on the Dolphins graph of 62 nodes is not meaningful.
Given the generality of the statement made by the authors, I would have expected much higher accuracy numerical experiments run on much larger graphs.

questions: The authors should first provide evidence that their proposal is indeed an improvement for stochastic algorithms on very large graphs and non-convex functions to optimize.

limitations: Do not apply.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the stochastic gradient descent algorithm as a stochastic sequence generated by a random walk on an arbitrary graph. It explores various Markov Chain Monte Carlo (MCMC) sampling techniques and proposes "efficiency ordering" of Markov chains. This is used to demonstrate that more efficient MCMC sampling can also lead to smaller covariances for SGD algorithms in the limit.
strengths_and_weaknesses: Strengths
- Paper is well written and presents both theoretical and empirical studies of the effect of MCMC sampling on SGD algorithms
- It introduces the novel concept of "efficiency ordering" of Markov chains and its. theoretical underpinnings
-Comparison of non-Markov random walks to their Markovian counterpart.

Weakness
- The main paper lacks sufficient details on the simulation and figures are too small for readability
-The overall readability of the paper needs to be improved 

questions: - The discussion on the mini-batch gradient descent can perhaps be relegated to the Appendix which would both free up space for more appropriate and thorough descriptions on empirical analysis of the efficiency ordering and ensure that variants of SGD are handled / discussed more efficiently. For e.g. if one discusses mini-batch gradient descent, why not other variants including momentum acceleration methods and other known techniques?

- The main paper does not discuss the effect of the underlying graph structure (which affects SLEM) and its impact on efficiency ordering of SGD

- The paper does not have a conclusion or future work section. It lacks a discussion on potential drawbacks of the technique.

Minor comments
- 1. Asymptotic covariance matrix - definition of \hat{mu}_t (g) -> sum_k=1 to t g(X_k) NOT X_t?

limitations: Societal impact of the work is not discussed in this paper. Furthermore, limitations of the proposed technique need further thought.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: At each iteration, stochastic gradient descent (SGD) processes data sampled randomly from the training set. Denote this sequence of training data by $(X_t)_t$, which includes the case where $X_t$ are mini-batches. Empirical evidence by the authors suggest that the convergence of SGD is faster when the asymptotic variance (AV) of the chain $(X_t)_t$ is smaller, contrary to the commonly held belief that smaller SLEM (second largest eigenvalue modulus) lead to faster convergence of SGD. This motivates the authors to study the AV of data sampling approaches commonly employed in SGD, such as mini-batch shuffling, and define efficiency ordering on chains based on their AV (lower AV implies higher efficiency). They prove rigorously that certain non-Markovian sequences such as shuffling give better efficiency ordering than Markovian i.i.d. input sequences. They then demonstrate experimentally that the former indeed gives rise to faster converging SGD when applied to the CIFAR-10 dataset.
strengths_and_weaknesses: Strengths:
- The results in the paper give new insights into SGD. In particular, it opens up a direction to look for more efficient SGD algorithms.
- The techniques involved in the proof are interesting and completely non-trivial. In particular, the idea of lifting non-Markovian sequences to an augmented space to make it Markovian was intriguing. The maths overall seem correct (although I do have some questions below) and fully rigorous.
- The main body of the paper is well-written and easy to follow.

Weakness:
- While the main body of the paper is well-written, the appendix, which contains all the proofs, can be improved. I defer some of my issues in the appendix to "Questions".
- Plots can be improved by:
   - Using larger label sizes (e.g. labels in Figure 2 are almost impossible to see without zooming in. Also better to increase label sizes in figure 1. Applies also to the figures in the appendix).
   - Improve colour-scheme by taking into consideration colorblindness. For instance, avoid red-green-blue combination (see e.g. https://davidmathlogic.com/colorblind/#%23D81B60-%231E88E5-%23FFC107-%23004D40 for more details).
- There are a few misprints/suggestions in the text of the main body that I spotted:
   - Line 140: $\mathbf{M}" \in \mathbb{R}^n$ should be $\mathbf{M} \in \mathbb{R}^n$ (note the quotation mark)
   - Line 268: "From the nature of same limiting distributions" can be phrased better. Maybe along the lines of "Since the limiting distributions are the same".
   - Line 369: "we random generate" should be "we randomly generate".

questions: - While the main body of the paper is well-written, the appendix I believe is not at the same quality and can be improved. For instance:
   - Line 69: "We can check the solution $\tilde{F}(\theta, z)$". What are we checking?
   - The proof of Proposition 4.1 (Appendix F) is confusing. What are the processes $X$ and $X'$? How are they related to the NBRW and SRW? While I agree with the computations in the proof, I still don't understand how it can be used to conclude that NBRW is more efficient than SRW.
   - In Appendix G, the line "regroup all the terms in each $k$-th epoch with length $n$" (line 226) is difficult to understand (I do understand now, but it took a while). It may help to supplement with a diagram.
   - What is $\hat{\pi}$ in the proof of Lemma H.1? How is it different from $\pi$?
   - I don't understand how the following line is true (Line 291-292):
> We also note that $P(s_t, s_{t+j}) = 0$ for $j \neq kn$ and $k \in \mathbb{N}$.

      Please could you explain more?
   - What do the embedded plots in figures 5a), 5b), 6a) and 6b) show?

- There are several misprints peppered throughout the appendix.
   - Line 72: I suggest phrasing "are right and left eigenvector of P" as "are the right and left eigenvectors of P respectively".
   - Line 94-95: "to ensure $\theta^*$ being local minimizer" should be "to ensure that $\theta^*$ is the local minimizer".
   - Line 226: I think "$\sum_{i = (k-1)n}^{kn-1} (g(X_i) - E_\pi (g))$" should read "$\sum_{i = (k-1)n}^{kn-1} (g(X_i) - E_\pi(g)) < \infty$".
   - Line 229: "because of bounded function $g$" should be "because of the boundedness of function $g$".
   - Line 247: "Especially, $u_m = \hat{\pi}$" should be "In particular, $u_m = \hat{\pi}$"
   - $s_6$ in line 268 should be $s_8$.
   - $a_j^{(t)}$ in line 290 should be $A_j^{(t)}$.
   - Appendix G: Lemma 4.2 is mislabelled as Proposition 4.2.

- While the results point to new methods for improving SGD, in practice, how easy is it to compute the asymptotic variance for a given chain? Also, is efficiency ordering still valid for other stochastic optimization methods such as Adam?

limitations: The work is mostly theoretical and as far as I can see, has no potential negative societal impact.
review_title: null

Meta-review: metareview: The paper proposes an asymptotic analysis of SGD when the noise governed by a Markov chain such as a random walk over an arbitrary graph. The paper connects efficiency ordering with an ordering of covariance matrices inherited from the Central Limit Theorems. 
One of the results of the work is that SGD algorithms can achieve smaller covariance errors by using a more efficient noise sequences from MCMC sampling. The paper considers decentralized optimization over a graph using high-order random walks for SGD and mini-batch gradient descent with shuffling on the other hand, as applications. The reviewers raised questions on experimental results on larger graphs for their applications, and the authors have preformed and committed to including these new experiments. As a result, all the reviewers are in favour of accepting, and are now confident in their scores.
confidence: Certain
Decision: Accept