Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization

1 Introduction

Continuous DR-submodular maximization, which generalizes the diminishing returns property to the continuous domain, has attracted increasing attention in recent years due to its superior performance on various applications, such as resource allocation [Eghbali and Fazel, 2016; Staib and Jegelka, 2017], learning assignments [Eghbali and Fazel, 2016], and recommendation system [Mokhtari et al., 2018; Xie et al., 2019]. To optimize continuous DR-submodular functions for large-scale data, several stochastic Frank-Wolfe methods [Hassani et al., 2019; Mokhtari et al., 2020; Zhang et al., 2020; Hassani et al., 2017] have been proposed. However, with the emergence of large-scale distributed data, maximizing continuous DR-submodular functions with good computational time guarantees becomes a practically relevant open challenge. For example, for the data generated on mobile devices or monitoring sensors, it is prohibitive to upload the data to a central server to conduct centralized optimization due to communication and privacy concerns. Therefore, in this paper we study the continuous DR-submodular maximization in the decentralized scenario. Specifically, we are interested in optimizing the following function:

∗Corresponding author

where k is the index for workers, x ∈ Ω denotes the model parameters in the compact convex set Ω, f (k) (x) = Eξ∼D(k)F (k) (x; ξ) is the monotone continuous DR-submodular function on the k-th worker where F (k) is the local cost and D(k) is the local data distribution. The goal of Eq. (1) is to collaboratively learn the model parameters x ∈ Ω using the data from K workers. In this process, data are kept on each worker and only the model parameters (or gradients) are communicated across different workers.

Decentralized optimization methods, such as decentralized stochastic gradient descent (D-SGD), have been commonly used for training machine learning models when data are distributed on different devices. For instance, [Lian et al., 2017] studied the convergence rate of D-SGD for optimizing non-convex problems. [Koloskova et al., 2019] developed a communication-efficient D-SGD method to reduce the communication cost. [Pu and Nedi´c, 2020] proposed a gradient tracking technique to improve the convergence performance of D-SGD. However, all of these methods focus on the regular unconstrained machine learning problems. They are not applicable to solve the constrained optimization problems defined in Eq. (1).

To facilitate continuous DR-submodular maximization, several papers [Mokhtari et al., 2018; Xie et al., 2019; Wai et al., 2017] propose decentralized variants of FrankWolfe method. In those variants, each worker computes the stochastic gradient based on its local data and then communicates the gradient with its neighbors. Based on the received stochastic gradients from its neighbors, each worker optimizes its local cost function with Frank-Wolfe method. For instance, based on the gossip mechanism, [Mokhtari et al., 2018] proposed a decentralized stochastic Frank-Wolfe (DeSCG) method for optimizing Eq. (1). To achieve ϵ-accuracy tight approximation ratio, it requires O(1/ϵ3 ) sample complexity and O(1/ϵ3 ) communication complexity. Based on the gradient tracking technique, [Xie et al., 2019] proposed the decentralized stochastic gradient tracking Frank-Wolfe

(DeSGTFW) method, improving the communication complexity to O(1/ϵ). However, DeSGTFW still has the same sample complexity as DeSCG because it has to use O(1/ϵ2 ) samples to compute the stochastic gradient at each iteration. It can be seen that both DeSCG and DeSGTFW have a large sample complexity O(1/ϵ3 ), resulting in a large computation overhead. Then, a natural question follows: Is it possible to develop a new decentralized optimization method for continuous DR-submodular maximization defined in Eq. (1), with sample complexity comparable to the centralized scenario?

To answer the aforementioned question, in this paper, we first propose a gossip-based decentralized stochastic variance-reduced Frank-Wolfe (DeSVRFW-gp) method. In contrast to the existing methods [Xie et al., 2019], which have large sample complexity caused by the stochastic gradient application at each iteration, DeSVRFW-gp employs a variance-reduced stochastic gradient to improve the sample complexity. Our theoretical results show that DeSVRFW-gp achieves O(1/ϵ2 ) sample complexity, which is better than the previous work. However, DeSVRFW-gp can only converge to the neighborhood of the approximated solution. The reason is that the gossip communication strategy leads to a loose consensus error bound for the gradient. Therefore, to address this issue, we further propose a gradient-trackingbased decentralized stochastic variance-reduced Frank-Wolfe (DeSVRFW-gt) method where we combine the variance reduction technique and gradient tracking strategy. As a result, DeSVRFW-gt can get a tighter consensus error bound for the gradient than DeSVRFW-gp, and then it can asymptotically converge to the approximated solution. Moreover, the theoretical result demonstrates that DeSVRFW-gt also achieves O(1/ϵ2 ) sample complexity and enjoys the same communication complexity O(1/ϵ) as DeSVRFW-gp. The comparison between our methods and the existing methods is summarized in Table 1. In addition to the theoretical considerations, we perform extensive experimental evaluation to confirm the effectiveness of our proposed methods.

To the best of our knowledge, this is the first work applying the variance-reduced stochastic gradient to decentralized Frank-Wolfe methods. The variance reduction technique introduces several challenges when bounding the consensus error by the convergence analysis of the decentralized FrankWolfe method. Additionally, the consensus error among different workers brings another challenge when bounding the gradient variance. Our work is the first attempt we are familiar with at providing the convergence rate under this setting. The contributions of this paper are summarized as follows:

• We propose two novel decentralized stochastic variancereduced Frank-Wolfe methods, namely, DeSVRFW-gp and DeSVRFW-gt. Both of them achieve O(1/ϵ2 ) sample complexity and O(1/ϵ) communication complexity.
• We provide novel theoretical analysis for the proposed methods. Especially, we demonstrate how to bound the gradient consensus error for the decentralized stochastic variance-reduced Frank-Wolfe method.
• The extensive empirical results confirm the effectiveness of the proposed DeSVRFW-gp and DeSVRFW-gt.

2 RelatedWork

In this section, we give an overview of the existing work on the continuous DR-submodular maximization.

Continuous DR-submodular maximization. Submodular functions have a diminishing return property. They have been applied to a wide variety of machine learning applications, such as sensor placement [Krause et al., 2006] and human brain network analysis [Salehi et al., 2017]. The continuous DR-submodular function tailors the diminishing return to the continuous domain for addressing some new challenges in machine learning, such as budget allocation [Staib and Jegelka, 2017] and experimental design [Chen et al., 2018]. In this process, optimizing the continuous DR-submodular functions becomes a practically important problem. A number of novel optimization models for this problem were proposed during the last decade. For instance, [Bian et al., 2017; Hassani et al., 2017] showed that the first-order methods can be used for optimizing it approximately. In particular, [Bian et al., 2017] maximized the continuous DR-submodular function with a full conditional gradient descent method approximately and achieves (1 - 1/e)OPT - ϵ1 approximation ratio with the sample complexity of O(1/ϵ). Under the stochastic setting, [Hassani et al., 2017] applied the stochastic proximal gradient method to optimize this problem, but it can only achieve (1/2)OPT- ϵ approximation ratio and the sample complexity is O(1/ϵ2 ). [Mokhtari et al., 2020] further proposed a variant of stochastic Frank-Wolfe method, which can achieve (1 - 1/e)OPT - ϵ approximation ratio as the full-gradient based method, but it needs the O(1/ϵ3 ) sample complexity. Recently, inspired by the development of the variance reduction techniques [Fang et al., 2018; Cutkosky and Orabona, 2019] for stochastic gradients, two variance-reduced stochastic Frank-Wolfe methods [Hassani et al., 2019; Zhang et al., 2020] were proposed. Both of them enjoy (1 - 1/e)OPT - ϵ approximation ratio with only O(1/ϵ2 ) sample complexity. However, all of these methods only focus on the single machine scenario. It is not clear whether they can retain their favorable complexity when being applied to distributed data.

Decentralized optimization. Decentralized optimization [Lian et al., 2017; Pu and Nedi´c, 2020; Sun et al., 2019; Yu et al., 2019; Lu et al., 2019; Koloskova et al., 2020; Gao and Huang, 2020] has attracted increasing attention in recent years due to the emergence of decentralized data produced by a variety of smart devices and sensors. Unlike the centralized optimization scenario, there is no central server in a decentralized scenario. Each worker only communicates the model parameters or gradients with its neighbors. Thus, there is no communication bottleneck issue associated with the central server. Recently, [Lian et al., 2017] studied the convergence rate of the decentralized stochastic gradient descent (D-SGD) method. They showed that D-SGD enjoys the same convergence rate as the centralized distributed SGD method and the topology of the decentralized system only affects the high-order term of the convergence rate. [Pu and Nedi´c, 2020] further developed the gradient tracking technique to accelerate the convergence of SGD. In particular, each worker introduces an auxiliary variable to track the average gradients. Recently, [Sun et al., 2019] and [Xin et al., 2020] proposed a new variant based on the variance-reduced gradient, achieving a better communication complexity. However, all these methods only focus on the unconstrained problem and cannot be applied to the constrained optimization problem in Eq. (1).

1 OPT means the optimal function value, e is the natural number.

To facilitate the optimization of Eq. (1) in the decentralized manner, [Mokhtari et al., 2018] developed a gossip-like stochastic Frank-Wolfe method. Specifically, each worker uses the stochastic Frank-Wolfe method to update the local model parameter and then communicates the model parameter and gradient with its neighboring workers. However, this method can only achieve O(1/ϵ3 ) sample complexity and O(1/ϵ3 ) communication complexity. To improve it, [Xie et al., 2019] proposed a new decentralized stochastic FrankWolfe method based on the gradient tracking technique. The communication complexity is improved to O(1/ϵ). However, this method still has a worse sample complexity than that of the single machine methods. Thus, there might still be space to further improve the complexity.

3 Preliminaries

In this section, we introduce the necessary background regarding the decentralized continuous DR-submodular maximization problem.

Definition 1. (Continuous submodular function) Given X = ∏di=1 Xi ∈ Rd+ where Xi denotes a compact subset of R+, for the continuous function F : X → R+, if for all x, y ∈ X , we have

F is submodular. Here, x∨y denotes the element-wise maximization and x∧y represents the element-wise minimization.

Definition 2. (Continuous DR-submodular function) The differentiable submodular function F is called DRsubmodular, if for all x, y ∈ X and x ≤ y2 , it satisfies

Additionally, a submodular function is called monotone if F (x) ≥ F (y) for x ≤ y ∈ X . In this work, we will consider the decentralized optimization of the monotone continuous DR-submodular maximization problem which has a convex constraint Ω, just as shown in Eq. (1).

2 It means that each coordinate of x is less than that of y. So does Eq. (3).

In the decentralized optimization system, each worker connects with its neighbors, composing a communication network. Here, we use graph G = (V,W) to represent this communication network. V = [K] denotes all the workers in this system and W = [wij ] ∈ RK×K + represents the connections among the workers. If the i-th worker and the j-th worker are connected, wij > 0. Otherwise, wij = 0. In addition, the connection matrix W satisfies the following assumption.

Assumption 1. W ∈ RK×K + is symmetric (W T = W) and doubly stochastic (W1 = 1 and 1T W = 1T ). Regarding the eigenvalues |λn| ≤ · · · ≤ |λ2| < |λ1| = 1 of W, they satisfy

where 1-ρ = |λ2| < 1. Here, ρ ∈ (0, 1] is called the spectral gap of W.

Assumption 2. For the compact convex set Ω, its diameter supx,y∈Ω ‖x-y‖ is bounded by D and its radius supx∈Ω ‖x‖ is bounded by R.

Assumption 3. The local objective function on each worker f (k) (x) is L-smooth, i.e.,

where L > 0 is a constant.

Assumption 4. The stochastic gradient of the local objective function on each worker is bounded, i.e.,

where ξ denotes the randomly selected sample and G > 0 is a constant.

Assumption 5. The variance of stochastic gradients on each worker is bounded, i.e.

where ξ denotes the randomly selected sample and σ > 0 is a constant.

Algorithm 1 DeSVRFW-gp

Initialization: x(k) 1 = x1, T.

• 1: for t = 1, 2, · · · , T do
• 2: if t = 1 then
• 3: Draw S(k) 1 samples and compute v(k) t =∇F (k) (x(k) t ; S(k) 1 )
• 4: else
• 5: Draw S(k)
• 2,t samples and compute v(k) t = v(k) t-1 + ∇F (k) (x(k) t ; S(k) 2,t ) - ∇F (k) (x(k) t-1 ; S(k) 2,t )
• 6: end if
• 7: y(k) t = ∑j∈Nk wkjv(j) t
• 8: u(k) t = argmaxu∈Ω〈y(k) t , u〉
• 9: x(k) t+1 = ∑j∈Nk wkjx(j) t + 1 T u(k) t
• 10: end for

4 Decentralized Stochastic Variance-Reduced Frank-Wolfe Method

4.1 Gossip-based Decentralized Stochastic Variance-Reduced Frank-Wolfe Method

In Algorithm 1, we propose the decentralized stochastic variance-reduced Frank-Wolfe method based on the gossip communication strategy (DeSVRFW-gp). At the t-th iteration, the k-th worker computes the variance-reduced gradient v(k) t based on its local data, and then communicates v(k) t with its neighbors by using the gossip algorithm as follows:

where Nk denotes the neighboring workers of the k-th worker. It can be seen that y(k) t is the weighted average of the neighboring v(j) t after the gossip communication. With y(k) t , the k-th worker optimizes the following linear programming problem to get the feasible ascent direction as the regular Frank-Wolfe method:

After that, it updates the local model parameters as follows:

where the first term on the right-hand side is to get the model parameter from its neighboring workers by using the gossip algorithm, and the second term is to update the local model parameter with the feasible ascent direction u(k) t .

In Algorithm 1, we use the variance-reduced technique to reduce the variance of local stochastic gradients. On the contrary, existing works, such as DeSGTFW [Xie et al., 2019], just use the stochastic gradient as v(k) t . As a result, DeSGTFW has to use a large batch size of samples to reduce the gradient variance, resulting in a large sample complexity at each iteration. Here, inspired by [Fang et al., 2018], we use the variance-reduced gradient to improve the sample complexity. As shown in Algorithm 1, at the first iteration, the k-th worker randomly selects S(k) 1 samples and computes the stochastic gradient v(k) 1 . At other iterations, each worker selects S(k) 2,t samples and computes the following variancereduced gradient estimator:

This gradient estimator has a smaller variance compared with the standard stochastic gradient [Fang et al., 2018]. As a result, it does not need to sample a large batch of samples to reduce the gradient variance as [Xie et al., 2019]. Thus, our method is supposed to have a smaller sample complexity than existing works. In particular, we establish the following theorem to demonstrate the complexity of our Algorithm 1.

Theorem 1. For Algorithm 1, under Assumptions 1-5, when |S(k) 1 | = σ2 T 2 L2D2 and |S(k) 2,t | = 9R2 T ρ2D2 for ∀k, t, we have

Remark 1. From Theorem 1, it can be seen that DeSVRFWgp needs O(1/ϵ) iterations to achieve the ϵ-accuracy approximation ratio when optimizing Eq. (1). It also indicates that the communication complexity of our method is O(1/ϵ), which can match the best existing result [Xie et al., 2019]. Thus, our method is efficient in communication.

Remark 2. Since the number of iterations T is O(1/ϵ), the size of S(k) 1 is O(1/ϵ2 ) and that of S(k) 2,t is O(1/ϵ). Then, the sample complexity of Algorithm 1 is |S(k) 1 | + |S(k) 2,t | ∗ T = O(1/ϵ2 ). On the contrary, existing methods, such as DeSCG [Mokhtari et al., 2018] and DeSGTFW [Xie et al., 2019], require O(1/ϵ3 ) gradient evaluations. Thus, our method is computationally efficient.

From Eq. (12), it can be seen that the last two terms on the right-hand side are independent on T. Thus, it can only converge to the neighborhood of (1 - 1e )f(x∗ ), which is not satisfactory. To address this issue, in the following subsection, we propose a new method to have a better convergence result.

Algorithm 2 DeSVRFW-gt

Initialization: x(k) 1 = x1, T.

• 1: for t = 1 · · · , T -1 do
• 2: if t = 1 then
• 3: Draw S(k)
• 1 samples and compute z(k) 1 = v(k) 1 =∇F (k) (x(k) 1 ; S(k) 1 )
• 4: else
• 5: Draw S(k) 2,t samples and compute

v(k)

t = v(k)

∇F (k) (x(k)

t-1 ; S(k)

t-1 + ∇F (k) (x(k)

2,t )

• 7: end if

9: u(k)

t = argmaxu∈Ω〈y(k)

t , u〉

• 11: end for

t ; S(k)

2,t ) -

4.2 Gradient-Tracking-based Decentralized Stochastic Variance-Reduced Frank-Wolfe Method

In Algorithm 1, we use the gossip strategy to communicate with neighboring workers. In this subsection, we proposed a new method based on the gradient tracking technique. Specifically, our proposed gradient-tracking-based stochastic variance-reduced Frank-Wolfe method (DeSVRFW-gt) is shown in Algorithm 2. Its high-level idea is similar to Algorithm 1. The difference lies in the strategy of updating gradients. In detail, at the t-th (t > 1) iteration, after obtaining the local variance-reduced gradient v(k) t , each worker k uses the gradient tracking method to track the average of gradients as follows:

With this strategy, y(k) t is capable of tracking 1K ∑Kk=1 ∇f (k) (x(k) t ). The reason is that y(k) t is close to ¯yt = 1K ∑Kk=1 y(k) t and ¯yt is close to 1K ∑Kk=1 ∇f (k) (x(k) t ). Compared with Algorithm 1 which uses the gossip communication method, y(k) t can approximate ¯yt = 1K ∑Kk=1 y(k) t more tightly. In other words, Algorithm 2 has a tighter consensus error ‖y(k) t - ¯yt‖2 than Algorithm 1, which will be shown in the next section.

To see the sample and communication complexities of DeSVRFW-gt, we establish the following theorem.

Theorem 2. For Algorithm 2, under Assumptions 1-5, when |S(k) 1 | = σ2 T 2 L2D2 and |S(k) 2,t | = 9R2 T ρ2D2 for ∀k, t, we have

Remark 3. From Theorem 2, it can be seen that Algorithm 2 can converge to (1 - 1e )f(x∗ ) rather than its neighborhood. Thus, Algorithm 2 has a better convergence performance than Algorithm 1.

Remark 4. Theorem 2 indicates that the communication complexity of Algorithm 2 is O(1/ϵ) to achieve the ϵaccuracy approximation ratio for optimizing Eq. (1), which is the same as that of Algorithm 1 and can match the best existing result in [Xie et al., 2019].

Remark 5. As for the sample complexity of Algorithm 2, it is O(1/ϵ2 ), which is the same as that of Algorithm 1 and better than DeSCG [Mokhtari et al., 2018] and DeSGTFW [Xie et al., 2019].

From Theorems 1 and 2, we can find that the batch size |S(k) 2,t | at each iteration is O(1/ϵ). Compared with DeSGTFW [Xie et al., 2019] whose batch size is O(1/ϵ2 ), our two methods have a smaller sample complexity at each iteration, accelerating the convergence speed.

In summary, we proposed two computationally efficient decentralized Frank-Wolfe methods to optimize Eq. (1). To the best of our knowledge, this is the first work applying the variance reduction technique to the decentralized FrankWolfe method. Although the variance reduction technique has been studied for the single machine case, our methods are novel and challenging, especially for the convergence analysis. On one hand, unlike the traditional variance-reduced Frank-Wolfe methods, our methods need to deal with the consensus error among different workers. On the other hand, the introduced variance-reduced gradient makes it more challenging to handle the consensus error compared with the traditional decentralized Frank-Wolfe methods.

5 Main Proof

In this section, we present the high-level idea of proving the convergence rate of our proposed DeSVRFW-gp and DeSVRFW-gt.

According to the smoothness of the loss function, we can get the following inequality:

where T1 measures how the averaging stochastic gradient yt is close to the averaging full gradient 1K ∑Kk=1 ∇f (k) (x(k) t ), T2 measures the consensus error regarding the local model parameter, and T3 measures the consensus error regarding the local stochastic gradient. Thus, to establish the convergence results in Theorem 1 and 2, what we need to do is to bound these three terms.

Due to the space limitation, we only show the bound of the consensus error T3 for these two theorems. The bounds for T1 and T2 can be found in the Supplementary Materials.

Lemma 1. For Algorithm 1, under Assumption 1-5, when |S1| = σ2 T 2 L2D2 and |S2| = 9R2 T ρ2D2 , we have

Lemma 2. For Algorithm 2, under Assumption 1-5, when |S1| = σ2 T 2 L2D2 and |S2| = 9R2 T ρ2D2 , we have

From the above two lemmas, it can be seen that Algorithm 2 can obtain a tighter consensus error ‖Yt - Y t‖F . Specifically, the first term in Lemma 1 is a constant, resulting in the constant term in Theorem 1. Thus, Algorithm 1 can only converge to the neighborhood of (1 - 1e )f(x∗ ). On the contrary, all items in Lemma 2 are shrunk when increasing the number of iterations. Thus, its bound is tighter than Lemma 1.

6 Experiments

In this section, we describe the experimental design and results of an empirical evaluation of the proposed methods.

In the experiment, following [Xie et al., 2019; Mokhtari et al., 2018], we apply our proposed DeSVRFW-gp and DeSVRFW-gt to the movie recommendation system. The loss function can be found in Supplementary Material. Here, we use two datasets: MovieLens-1M and MovieLens-100K 3 . In detail, MovieLens-1M has 1 million ratings which are from 6,040 users on 3,883 movies, and MovieLens-100K has 100,000 ratings which are from 943 users on 1,682 movies. Ratings range from 1 to 5. The goal of this experiment is to recommend a group of |O| = 10 movies to users expecting the highest satisfaction based on users' historical ratings. In our experiment, we use 8 workers for MovieLens-1M and 4 workers for MovieLens-100K. For each case, the ratings from users are divided into all workers evenly. For instance, when there are 8 workers for MovieLens-1M, each worker will have 755 users and their associated historical ratings.

(a) MovieLens-100K

(b) MovieLens-1M

Figure 1: Comparison between different methods. The plots show the objective value versus the total number of function evaluation calculated.

As for the communication graph, we use the Erdos-Renyi random graph in our experiment. The mean vertex degree in the graph is 2. For the non-diagonal entries in the weight matrix W of the communication graph, if vertex i and vertex j are connected, wij = 1/(1 + max(Di,Dj)) where Di denotes the degree of the vertex i. If there is no edge between vertex i and vertex j, wij equals to 0. For the diagonal entries, wii = 1 - ∑j∈N(i) wij. This kind of weight matrix satisfies Assumption 1.

In Figure 1, we compare our proposed two methods with two baseline methods: DeSCG [Mokhtari et al., 2018] and DeSGTFW [Xie et al., 2019]. In particular, we plot the objective function value with respect to the number of function evaluations for two datasets, respectively. Here, for our methods, we use the batch size of 100 for MovieLens-100K and 200 for MovieLens-1M. Regarding the other two baseline methods, we set it according to their theoretical results.

3 https://grouplens.org/datasets/movielens/

From Figure 1, we can see that DeSCG converges much slower than all the other methods. The reason is that it uses the stochastic gradient at each iteration which has a large estimation variance, slowing down the convergence speed. In addition, it can be found that DeSGTFW converges faster than DeSCG but slower than our two methods. Here, DeSGTFW employs the gradient tracking technique so that it is faster than DeSCG. However, our methods employ the variance reduced gradient at each iteration. Thus, our two methods converge faster than DeSGTFW, which is consistent with our theoretical results. Note that, in Figure 1, DeSGTFW converges a little faster than our two methods at the beginning phase. The reason is that DeSGTFW uses O(1/t2 ) samples at each iteration where t represents the t-th iteration. Therefore, at the beginning phase, DeSGTFW is faster, but it becomes slower as the training progresses because more samples are needed for each update. Furthermore, we observe that DeSVRFW-gt outperforms DeSVRFW-gp. The reason is that DeSVRFW-gt employs the gradient tracking technique to estimate the global gradient across different workers so that y(k) t has a smaller variance compared to DeSVRFW-gp. Thus, DeSVRFW-gt converges faster.

Finally, in Figure 2, we plot the objective function value versus the accumulated communication cost. Due to the space limitation, we only show the result for MovieLens100K. The other dataset produces a similar result. It can be seen that our two methods have almost the same communication cost as DeSGTFW, which is consistent with the theoretical result. DeSCG has the largest communication cost, which is also consistent with Table 1.

7 Conclusions

In this paper, we proposed two novel decentralized stochastic Frank-Wolfe methods for optimizing the continuous DRSubmodular maximization problem. Our theoretical results demonstrated that our two methods have better sample complexities than the existing methods. This is the first work that achieves such sample complexities. Our extensive empirical evaluation is consistent with the theoretically predicted results.