INTRODUCTION

This paper considers the problem of collaboratively optimizing the average of n local cost functions, each owned by individual agents connected in a network. The local function at each agent depends on the corresponding local dataset. Mathematically, the problem is as follows:

where n is the number of agents, f i is the local loss of agent i ∈ [n] ≜ {1, 2, . . . , n}, m is the local dataset size, and f i,j is the loss corresponding to the j-th sample at the i-th agent. This problem has applications in signal processing and machine learning (ML), and has been studied for decades [1,2,3]. However, modern applications also face an explosion in the amount of data available at the edge devices. This additional challenge precludes the usage of classical algorithms like gradient descent [4], that require full gradient computation at each step. In this situation, distributed stochastic gradient methods emerge as simple yet powerful alternatives.

This work was supported in part by NSF grants CCF 2045694, CNS-2112471, CPS-2111751, SHF-2107024 and ONR N00014-23-1-2149.

Stochastic gradient descent (SGD) is one of the most popular methods in modern ML. Consequently, its decentralized versions have also been extensively studied in the literature [5,6]. When minimizing smooth objective functions, decentralized SGD (D-SGD) eventually achieves the same convergence as that of centralized SGD, implying network independence of the convergence error [7]. Subsequent work has focused on proposing more sophisticated algorithms to further improve the performance of D-SGD. Such methods include gradient tracking (GT) [8] and exact diffusion (ED) [9,10].

The theoretical analysis of vanilla SGD assumes withreplacement sampling at each step to compute the gradient estimate [11]. However, in practice, without replacement sampling is observed to perform better. A commonly used SGD variant, called Random Reshuffling (RR), is used in deep-learning packages like PyTorch and TensorFlow. RR permutes the dataset at the beginning of each epoch, and computes gradient estimates using mini-batches sampled from the permuted sequence. Recent work [12,13] has theoretically shown the benefits of RR compared to SGD. Specifically, given the dataset size Nfoot_0 and number of epochs T , for smooth strongly-convex problems RR achieves (for large enough T ) a convergence of O(1/(N T 2 )), compared to O(1/(N T )) for SGD. For smooth nonconvex objectives, RR achieves O(1/(N T 2 ) 1/3 ), compared to O(1/ √ N T ) for SGD. These benefits of RR over SGD naturally call for exploring RR in the decentralized setting.

The initial works that studied RR in the decentralized setting [14,15] do not show any superiority over decentralized SGD. Subsequent work in [16,17] proposed decentralized algorithms to solve smooth strongly-convex and nonconvex problems. Ignoring network dependence terms, the achieved convergence rates are O(1/(mT 2 )) in the strongly-convex, and O(1/(mT 2 ) 1/3 ) in the nonconvex case. These outperform D-SGD in certain parameter regimes (see Table 1). However, two crucial questions remain unanswered.

1. Can decentralized RR methods (D-RR and GT-RR) achieve convergence speedup with increasing network size n?

2. How to design RR-based algorithms that achieve network independent asymptotic convergence?

In this paper, we answer the first question in the affirmative, and highlight some interesting empirical observations that might help answering the second question.

Table 1: Comparison of the convergence rates of different decentralized algorithms. We omit the higher-order terms. O λ indicates that the dominant terms have network dependence that has been omitted for simplicity.

Contributions

We perform a refined analysis of two existing decentralized random reshuffling based algorithms: D-RR [16] for smooth strongly-convex, and GT-RR [17] for smooth nonconvex problems. Compared to existing results in [16,17], we achieve an additional speedup in terms of the number of agents n (see Table 1) in both the cases.

Further, our experiments reveal some interesting observations. First, D-RR (and GT-RR) achieves a smaller error than D-SGD even if the agents in the former communicate significantly less often, with agents taking multiple stochastic gradient steps between successive communications. Second, in the nonconvex case, we discover a gap in the existing theoretical analysis and the empirical results. The convergence results in this case (in [16,17], as well as ours) bound ∥∇f (x)∥ 2 , where x is the global average of iterates, and have network dependence (see [17, Table 1] and Theorem 2). However, our experiments in Figure 2 suggest that ∥∇f (x)∥ 2 is independent of the network across different topologies. On the other hand, the convergence of

in the analysis of D-SGD and related methods) does indeed depend on the underlying network.

ALGORITHM AND THEORETICAL RESULTS

We reproduce below the D-RR algorithm from [16], and refer the reader to [17] for the GT-RR algorithm. Next, we introduce the assumptions needed in our theoretical results.

Assumptions

We assume the agents in the network are connected via a graph G = (N , E), where N = [n] denotes the set of agents, and E ¦ N × N denotes the set of edges. We denote the set of neighbors of agent i by

Algorithm 1 Distributed Random Reshuffling (D-RR) [16] 1: Input:

for j = 0, . . . , m -1 do

end for

end for 13: end for 14: Output {x i,T } Assumption 1 (Network Weight Matrix). The network graph G is undirected and connected, i.e., there exists a path between any two nodes in G. There is a direct link between nodes i and j (i ̸ = j) if and only if w ij > 0 and w ji > 0; otherwise, w ij = w ji = 0. The mixing matrix is nonnegative, symmetric, and stochastic, i.e., W = W ¦ and W 1 = 1.

We denote by λ the spectral norm of matrix W -11 ¦ /n. By Assumption 1, λ < 1. Next, we discuss the assumptions on the loss functions in (1).

Assumption 2 (Smoothness). Each local component function f i,j is bounded from below and L-smooth, i.e., ∥∇f i,j (x) -∇f i,j (y)∥ f L ∥x -y∥ , for all x, y ∈ R d . Assumption 3 (Strong Convexity). Each local function f i,j is µ-strongly convex, i.e., for all i, j and x, y ∈ R d ï∇f i,j (x) -∇f i,j (y), xyð g µ ∥x -y∥ 2 .

The above assumption can be relaxed to PL condition on the global function f [17], but we retain it here for simplicity. Next, we state and discuss our convergence results.

Convergence Results

Theorem 1 (Strongly Convex Case). Suppose Assumptions 1, 2 and 3 hold. If we choose α t = θ mµ(t+K) with θ > 12 and appropriately chosen K, we have Theorem 1], with an addition speedup with respect to the number of agents n in the first term and improving the dependence on the number of component functions m in the second term. In settings with n < m and well-connected underlying graphs (such that 1 1-λ is independent of n), the first term dominates, and the convergence becomes almost network independent, recovering the performance of centralized RR (C-RR) [18]. For example, in Figure 1c, with exponential graphs, both D-RR and C-RR show similar convergence.

The improved bound in Theorem 1 results from a tighter bound on the shuffling variance σ 2 shuffle , defined in [16, Definition 1], which we state next.

Lemma 2.1. Under Assumption 2, we have

Remark 2. The bound in (3) has an extra 1/n factor that is missing in the corresponding bound in [16, Lemma 6], and results in the linear speedup in the number of agents n in Theorem 1. Note that σ2 * defined in Lemma 2.1 is different from σ 2 * in [16], where

However, it is easy to see that σ2 * f 4σ 2 * . Next, we state the convergence of GT-RR, a gradient tracking-based method proposed in [17], for smooth nonconvex problems. It is proved in [17] that GT-RR has better network dependence compared to D-RR.

Theorem 2 (Nonconvex Case). Suppose Assumptions 1, 2, and [17, Assumption 2.1] hold. Then, with appropriately chosen step-sizes {α t }, iterates generated by GT-RR satisfy

Remark 3. Our bound above improves the corresponding bound O

in [17, Theorem 4.1], by again achieving an addition speedup with respect to the number of agents n in the first term, and improving the dependence on the number of component functions m in the second term. Remark 4. We state the result in Theorem 2 in terms of E ∇f (x 0 t ) 2 for direct comparison with the corresponding results in [16,17]. However, there are two limitations of the current bound. First, the bound does not explicitly quantify how different the individual iterates {x 0 i,t } n i=1 are. Therefore, many existing works [6,10] bound

To see the benefit of the latter quantity, note that

which follows from Assumption 2. Second, our experiments suggest (see Figure 2 and the accompanying discussion) that ∇f (x 0 t ) 2 for both GT-RR and D-RR is independent of the network topology, and matches the performance of centralized RR. This suggests that the 1 1-λ factor in (4) might be an artifact of the analysis. On the other hand, Figure 2 shows that 1

2 is indeed network dependent.

EXPERIMENT RESULTS

We evaluate the numerical performance of D-RR and GT-RR algorithms on the same binary classification problems on CIFAR10 dataset [19], as those considered in [17], but uncover some interesting observations. Centralized-RR and SGD serve as the baselines in all our experiments. All the curves have values averaged over 5 independent trials. The per agent batch-size for decentralized algorithms is 10 (for the centralized algorithms, it is 10 × n). In the strongly-convex case, we solve the following optimization problem.

where D i (i = 1, . . . , n) denotes the local dataset for agent i, such that m = |D i | for all i. ρ is set as 0.2.

In Figure 1, we compare the performance of D-RR and GT-RR with that of D-SGD over a network of n = 16 agents connected in a ring, grid, and exponential graph. Centralized-RR (C-RR) and SGD serve as respective baselines. We plot the average iterate distance from the optimum

As discussed in Theorem 1 and Remark 1, the error floor for D-RR has network dependence. This is evident from the worse error floors of D-RR and GT-RR. However, if the graph is well-connected, as with exponential graph (Figure 1c), the difference is negligible.

We also explore the impact of changing the communication frequency. As communication becomes more infrequent (increasing value of C) the error floor worsens. However, for well-connected networks, D-RR can still achieve a significantly better error floor than D-SGD (with C = 1). For exponential graphs, we can choose C as large as 25 and still outperform D-SGD. This suggests that decentralized RR-based methods with multiple gradient steps between successive communications can be beneficial in communicationconstrained settings and require further exploration. The special case with C = m has been studied in [15]. 0 20 40 60 80 100 120 140 Epochs 10 -1 10 -3 10 -5 10 -7 10 -9 ||∇f (x 0 t )|| 2 SGD C-RR D-SGD (C=1) D-RR (C=1) GT-RR (C=1) 0 20 40 60 80 100 120 140 Epochs 10 -1 10 -3 10 -5 10 -7 10 -9 1 n n i=1 ||∇f (x 0 i,t )|| 2 SGD C-RR D-SGD (C=1) D-RR (C=1) GT-RR (C=1) (a) Ring graph 0 20 40 60 80 100 120 140 Epochs 10 -1 10 -3 10 -5 10 -7 10 -9 ||∇f (x 0 t )|| 2 SGD C-RR D-SGD (C=1) D-RR (C=1) GT-RR (C=1) 0 20 40 60 80 100 120 140 Epochs 10 -1 10 -3 10 -5 10 -7 10 -9 1 n n i=1 ||∇f (x 0 i,t )|| 2 SGD C-RR D-SGD (C=1) D-RR (C=1) GT-RR (C=1) (b) Exponential graph Fig. 2: Comparison of decentralized random reshuffling based algorithms: D-RR and GT-RR with centralized-RR, D-SGD and SGD for solving the strongly-convex binary classification problem (5) on CIFAR10 dataset, over networks with n = 16 agents.

C is fixed at 1. The step-size is sequentially set as 0.02, 0.004 and 0.001.

At the other extreme, in some cases, communication might be cheaper than gradient computation. This case is represented by the C < 1 case, where each gradient computation is followed by 1/C rounds of communication. As expected, more communication results in improved consensus error, hence better convergence.

In the nonconvex case, we again solve a binary classification problem, but with a different regularizer, which leads to the following optimization problem.

, where x q denotes the q-th element of x ∈ R d . We set η = 0.2.

In Figure 2, we fix the communication frequency to C = 1. We plot both the gradient norm at the average iterate ∇f (x 0 t ) 2 , as well as the average of gradient norms at individual iterates 1 n n i=1 ∇f (x 0 i,t ) 2 . For both ring and exponential graphs, the convergence of ∇f (x 0 t ) 2 seems independent of the network. This observation points to the need for an improved theoretical analysis, which removes the network dependence from the leading terms in Theorem 2.

On the other hand, 1 n n i=1 ∇f (x 0 i,t ) 2 has network dependence. GT-RR improves the error floor compared to D-RR but does not eliminate the network dependence completely.

CONCLUSION

We presented improved analyses of two existing randomreshuffling based decentralized algorithms, D-RR and GT-RR. We show that the convergence of the two algorithms improves with increasing network size. Experimental results, while corroborating our theory, also point out some gaps in the current theoretical understanding of the nonconvex case, which requires further investigation. Other pertinent directions for future work include proposing algorithms that achieve network-independent convergence and shorter transient times. Corresponding work on D-SGD like methods [7,10] can possibly provide some insights in this direction.