1 Introduction↩︎

Submodularity of a set function implies a natural diminishing returns property where the marginal benefit of any given element decreases as we select more and more elements. Formally, a set function \(F\colon 2^E \to \mathbb{R}\) is submodular if for any \(S \subseteq T \subseteq E\) and \(e \in E\setminus T\) it holds that \(F(S \cup \{e \}) - F(S) \geq F(T \cup \{e\}) - F(T).\) Decomposable submodular functions is an important subclass of submodular functions which can be written as sums of several component submodular functions: \(F(S) = \sum_{i=1}^N f_i(S)\), for all \(S\subseteq E\), where each \(f_i:2^E\to \zR\) is a submodular function on the ground set \(E\) with \(|E|=n\).

Decomposable submodular functions include some of the most fundamental and well-studied submodular functions such as max coverage, graph cuts, welfare maximization etc., and have found numerous applications in machine learning [1]–[5], economics [6]–[10], and data summarization and recommender systems [1], [2], [11], [12]. The main approach in these cases is the centralized and sequential greedy.

The need for scalable and efficient optimization methods, which do not require collecting raw data in a central server and ensure secure information collection, is widespread in applications handling sensitive data such as medical data, web search queries, salary data, and social networks. In many such cases, individuals and companies are reluctant to share their data and collecting their data in a central server is a violation of their privacy. Moreover, collecting and storing all data on a single server or cluster is computationally expensive and infeasible for large-scale datasets, particularly when working with high-dimensional data or complex models. Thus, there is a widespread demand for scalable optimization algorithms that are both decentralized and prioritize privacy. Below are some examples that motivate the focus of this paper.

Federated setting [19], [20] is a novel and practical framework that addresses issues regarding privacy, data sharing, and centralized computation. On one hand, it is a distributed and collaborative approach that allows multiple parties, such as different organizations or devices, to train a shared model or collaboratively optimize an objective function while keeping their data locally. This approach helps to protect the privacy of data by ensuring that the raw data is never shared or moved outside of the individuals’ systems. Instead, only the model updates are exchanged and aggregated to improve the shared model and improve the objective value.

On the other hand, the federated framework reduces the amount of data that needs to be transferred and processed at any one time, which can significantly reduce the computational complexity of the overall process. Additionally, federated setting can also take advantage of the computational resources available at each party, such as the processing power of mobile devices or edge devices, which can further reduce computational load on the server. This way, federated learning can train models more efficiently, even with large-scale datasets and complex models, and provide a scalable solution for distributed learning.

In this paper, we introduce the problem of maximizing a submodular function in the federated setting. Let \(E\) be a ground set of size \(n\) and \(c_1,\dots,c_N\) be \(N\) clients each of whom has a private interest over \(E\). Each client’s interest is expressed as a submodular function. Let \(f_i:2^E\to \mathbb{R}_{+}\) be the associated submodular function of the \(i\)-th client. A central server wants to solve the following constrained distributed optimization model \[\begin{align} \label{eq:objective-constrained} \max_{S\in \mc{I}}\left\{F(S)=\sum_{i=1}^N p_i f_i(S)\right\}, \end{align}\tag{1}\] where \(\mc{I}\) is the independent sets of a matroid \(\mc{M}\) with ground set \(E\), and \(p_i\) are pre-defined weights such that \(\sum_{i=1}^N p_i=1\). For instance, they can be set to \(1/N\), or the fraction of data owned by each client. The constraint implies sets of particular properties, e.g., subsets of size at most \(k\). Note that, the unconstrained optimization is a special case of this.

In the optimization problem 1 the data can be massively distributed over the number of clients \(N\), which can be huge. Moreover unlike the traditional distributed setting, in the federated setting the server does not have control over clients’ devices nor on how data is distributed. For example, when a mobile phone is turned off or WiFi access is unavailable, the central server will lose connection to this device. Furthermore, client’s objective can be very different depending on their local datasets. To minimize communication overhead and server computation load, the number of communication rounds need to be minimal.

We formally discuss factors of efficiency and restrictions that should be considered.

One of the main appeals of decentralized and federated setting is to preserve the privacy. There are several models of privacy and security that have been considered in the literature such as Differential Privacy (DP) and Secure Aggregator (SecAgg), and a mix of these two. Single-server SecAgg is a cryptographic secure multi-party computation (MPC) that enables clients to submit vector inputs, such that the server (an aggregator) can only decipher the combined update, not individual updates. This is usually achieved via additive masking over a finite group [21], [22]. Note that secure aggregation alone does not provide any privacy guarantees. To achieve a DP-type guarantee, noise can be added locally, with the server aggregating the perturbed local information via SecAgg. This user-level DP framework has recently been adopted in private federated learning [23]–[27].

In this paper we use Single-server SecAgg model of privacy, a dominant and well-established approach in the field. We leave other notions of privacy, such as a mix of DP and SecAgg, for future works. There has been a recent and concurrent progress towards this direction in terms of cardinality constraints [27].

There are a few aspects to this, firstly the number of communication rounds should be as small as possible. Second, the information communicated between should require low bandwidth and they better require small bit complexity to encode.

While the above impose strong restrictions, a good decentralized submodular maximization algorithm should not scarify the convergence rate by too much and should yield to an accurate and acceptable result in comparison to the centeralized methods.

We present the first federated (constrained) submodular maximization algorithm converging close to optimum guarantees known in centralized settings.

\(\bullet\) We propose a decentralized version of the popular Continuous Greedy algorithm Federated Continuous Greedy (FedCG) and prove its convergence whenever the client functions are nonnegative monotone submodular achieving the optimal multiplicative approximation factor \((1-\frac{1}{e})\) with a small additive (3).

\(\bullet\) We incorporate important and practical scenarios that are relevant for federated setting such as partial client selection, low communication rounds and computation cost. We give rigorous theoretical guarantees under each scenarios matching the optimal multiplicative approximation of \((1-\frac{1}{e})\) and small additive error (4).

\(\bullet\) We introduce a new algorithm that serves as a discrete federated optimization algorithm for submodular maximization. Its convergence and applications to discrete problems such as Facility Location and Maximum Coverage are explored (Section 5).

1.1 Related Work↩︎

1.1.0.1 FedAvg, its convergence, and assumptions.

The concept of Federated Learning (FL) [20] has found application in various domains such as natural language processing, computer vision, and healthcare. The popular FL algorithm, Federated Averaging (FedAvg), is an extension of Local SGD that aims to reduce communication costs in distributed settings [28]–[31]. However, despite its practical benefits in addressing privacy, data heterogeneity, and computational constraints, it may not converge to a “good enough” solution in general [32], [33]. Analyzing the convergence of FedAvg and providing theoretical guarantees is challenging and necessitates making certain assumptions. Assumptions related to bounded gradients, convexity, Lipschitzness, statistical heterogeneity, and bounded variance of stochastic gradients for each client have been explored in recent works [31], [34]–[37].

The main approach to submodular maximization is the greedy approach which in fact, in the centralized setting yields the tight approximation guarantee in various scenarios and constraints e.g., see [10], [17], [38]. Centeralized submodular maximization under privacy constraints is an active research area [39]–[41]. However the sequential nature of the greedy approach makes it challenging to scale it to massive datasets. This issue is partially addressed by the means of Map-Reduce style algorithms [42] as well as several elegant algorithms in the distributed setting [4], [43]. Recent work of [44] ventures towards decentralized submodular maximization for continuous submodular functions. In general continuous submodular functions are not convex nor concave and there has been a line of work to optimize continuous submodular functions using SGD methods [45]. [44] under several assumptions, such as assuming clients’ local objective functions are monotone, DR-submodular, Lipschitz continuous, and have bounded gradient norms, prove that Decenteralized Continuous Greedy algorithm yields a feasible solution with quality \(O(1- 1/\mathrm{e})\) times the optimal solution. The setting in [44] is fundamentally different from the federated setting in a sense that they require sharing gradient information of the clients with the server or with the neighboring nodes in an underlying graph. Perhaps the most closely related method to our work is due to [46], [47]. [46] consider Frank-Wolfe Algorithm [48] in the federated setting and propose Federated Frank-Wolfe (FedFW) algorithm and analyze its convergence for both convex and non-convex functions and under the \(L\)-Lipschitzness and bounded gradients assumptions.

2 Preliminaries↩︎

Let \(E\) denote the ground set, \(|E|=n\). For a vector \(\mb{x}\in\zR^{|E|}\) and a set \(S\subseteq E\), \(\mb{x}(S)\) denotes \(\sum_{e\in S}\mb{x}(e)\). A submodular function \(f:2^E\to \zR\) is monotone if \(f(S)\leq f(T)\) for every \(S\subseteq T\subseteq E\). Throughout this paper we assume \(f(\emptyset)=0\).

The multilinear extension \(\widehat{f}:[0, 1]^{|E|}\to \zR\) of a set function \(f:\{0,1\}^{|E|}\to \zR\) is \[\begin{align} \widehat{f}(\bx) &=\sum_{S\subseteq E}f(S)\prod\limits_{e\in S}\bx(e)\prod\limits_{e\not\in S}(1-\bx(e))= \mathbb{E}_{R\sim \mb{x}}[f(R)] \end{align}\] where \(R\subseteq E\) is a random set that contains each element \(e \in E\) independently with probability \(\mb{x}(e)\) and excludes it with probability \(1-\mb{x}(e)\). We write \(R \sim \mb{x}\) to denote that \(R\subseteq E\) is a random set sampled according to \(\mb{x}\).

Observe that for all \(S\subseteq E\) we have \(\widehat{f}(\mb{1}_S) = f(S)\). For monotone non-decreasing submodular function \(f\), \(\widehat{f}\) has the following properties [17] that are crucial in analyses of our algorithms:

\(\widehat{f}\) is monotone, meaning \(\frac{\partial \widehat{f}}{\partial \mb{x}(e)}\geq 0\). Hence, \(\nabla \widehat{f}(\mb{x})=(\frac{\partial \widehat{f}}{\partial \mb{x}(1)},\dots,\frac{\partial \widehat{f}}{\partial \mb{x}(n)})\) is a nonnegative vector.

\(\widehat{f}\) is concave along any direction \(\mathbf{d}\geq \mathbf{0}\).

Note that \(\frac{\partial \widehat{f}}{\partial \mb{x}(e)}=\mathbb{E}_{R\sim \mb{x}}[f(R\cup\{e\})-f(R\setminus \{e\})]\). That is the expected marginal contribution for \(e\) where the expectation is taken over \(R\subseteq E\setminus \{e\}\) sampled according to \(\mb{x}\). By submodularity, for any \(\mb{x}\in [0,1]^n\), \[\begin{align} |\nabla \widehat{f}(\mb{x})|_{\infty} \leq \max_{e\in E}f(\{e\}):=m_f. \end{align}\] A pair \(\mathcal{M} = (E,\mc{I})\) of a set \(E\) and \(\mc{I}\subseteq 2^E\) is called a matroid if 1) \(\emptyset \in \mc{I}\), 2) \(A\in \mc{I}\) for any \(A \subseteq B\in \mc{I}\), and 3) for any \(A,B\in \mc{I}\) with \(|A| < |B|\), there exists \(e \in B\setminus A\) such that \(A\cup \{e\}\in \mc{I}\). We call a set in \(\mathcal{I}\) an independent set. We sometimes abuse notation and use \(S\in\mc{M}\). The rank function \(r_{\mc{M}}\colon 2^E \to \mathbb{Z}_+\) of \(\mc{M}\) is \(r_{\mc{M}}(S)=\max\{|I|:I\subseteq S, I\in \mc{I}\}\). An independent set \(S\in \mc{I}\) is called a base if \(r_{\mc{M}}(S)=r_{\mc{M}}(E)\). We denote the rank of \(\mc{M}\) by \(r(\mc{M})\). The matroid polytope \(\mc{P}(\mc{M}) \subseteq \zR^E\) of \(\mc{M}\) is \(\mc{P}(\mc{M})=\mathrm{conv}\{\mathbf{1}_I : I\in \mc{I}\}\) where \(\mathrm{conv}\) denotes the convex hull. Or equivalently [49], \(\mc{P}(\mc{M})=\left\{\mb{x}\geq \mb{0} : \mb{x}(S)\leq r_{\mc{M}}(S) ;~ \forall S\subseteq E \right\}.\)

Our algorithms for maximizing a submodular function in federated settings are based on the Continuous Greedy (CG) algorithm. We briefly explain this algorithm. The results mentioned are from [10], [17]. Let \(\mc{M}=(E,\mc{I})\) be a matroid and \(\mc{P}(\mc{M})\) be its matroid polytope of rank \(r\), let \(f\) be a nonnegative and monotone submodular function and \(\widehat{f}\) be its multilinear extension. CG starts with \(\mb{x}^{(0)}=\mb{0}\). For every \(t\in\{0,1,2,\dots,T-1\}\) it computes \(\mb{x}^{(t+1)}\) using the following update step \(\mb{x}^{(t+1)}\gets \mb{x}^{(t)} + \eta \mb{v}^{(t)}\), where \(\mb{v}^{(t)}=\argmax_{\mb{w}\in\mc{P}}\langle \mb{w},\nabla\widehat{f}(\mb{x}^{(t)})\rangle\). For \(\texttt{OPT}=\max_{\mb{x}\in\mc{P}}\widehat{f}(\mb{x})\) we have \((1-(1-\eta)^T)\texttt{OPT}\leq \widehat{f}(\mb{x}^{(T)})+C\eta^2/2\). Here, the constant \(C\) depends on the Lipschitz of the function, and \(\mb{x}^{(T)}\in\mc{P}\) as it is a convex combination of vectors from the polytope. For \(\eta=1/T\) and large enough \(T\) we get \((1-1/\mathrm{e})\texttt{OPT}\leq \widehat{f}(\mb{x}^{(T)})+\epsilon\). Given \(\mb{x}^{(T)}\in\mc{P}\), there are rounding procedures to obtain \(S\in\mc{I}\) with \(\widehat{f}(\mb{x}^{(T)})\leq f(S)\). The approximation factor \(1-1/\mathrm{e}\) is the best possible assuming \(\mb{P}\neq \mb{NP}\) [50].

3 Federated Continuous Greedy↩︎

In this section, we propose our Federated Continuous Greedy (FedCG) method. We start with a simplistic scenario of federated model with full participation which already shows some of the challenges that we have to overcome before delving into the partial participation model which is more computationally feasible. Consider optimization problem 1 where each \(f_i\) is a nonnegative monotone submodular function, \(\sum_{i=1}^{N} p_i=1\), and \(\mc{I}\) is the independent sets of matroid \(\mc{M}=(E,\mc{I})\) of rank \(r\).

For every client \(i\) and every \(\mb{x}\in \mc{P}\), the vector \(\mb{v}_i=\argmax_{\mb{w}\in\mc{P}}\langle \mb{w},\nabla\widehat{f_i}(\mb{x})\rangle\) is determined by maximizing a linear function \(\langle \mb{w},\nabla\widehat{f_i}(\mb{x})\rangle\) over matroid polytope \(\mc{P}\). This problem can be solved very efficiently. We can assume that \(\mb{v}_i\) is a vertex of \(\mc{P}\) and furthermore, since \(\nabla\widehat{f_i}\) is a nonnegative vector, that this vertex corresponds to a base of matroid \(\mc{M}\). Hence, without loss of generality \(\mb{v}_i\) is the indicator vector of a base with \(r\) ones and \(n-r\) zeros. Thus it can be encoded using \(O(r\log(n))\) bits, sublinear in the size of the ground set. On the other hand, the vector \(\nabla\widehat{f_i}(\mb{x})\) itself requires \(\tilde{O}(n)\) bits for encoding. In what follows we will see how restricting the bit complexity effects the accuracy, and the amount of computation that server should do.

First consider the case where clients can send their gradients. We proceeds in rounds. Initially \(\mb{x}^{(0)}=0\). On the \(t\)-th round, first, the central server broadcasts the latest model \(\mb{x}^{(t)}\) to all clients. Each client \(i\) after receiving the update sets \(\mb{x}_{i}^{(t)}=\mb{x}^{(t)}\) and computes \(\nabla\widehat{f}_i(\mb{x}^{(t)})\). The server then aggregates local information via SecAgg, and computes \(\nabla\widehat{F}(\mb{x}^{(t)})=\sum_{i=1}^N p_i \nabla\widehat{f}_i({\mb{x}^{(t)}})\). After receiving \(\nabla\widehat{F}(\mb{x}^{(t)})\), the server computes \(\mb{v}^{(t)}=\argmax_{\mb{w}\in \mc{P}}\langle \mb{w},\nabla\widehat{F}(\mb{x}^{(t)})\rangle\) by maximizing a linear function subject to the matroid constraint and produces the new global model with learning rate \(\eta\): \(\bx^{(t+1)}\gets \bx^{(t)} + \eta \mb{v}^{(t)}\). It is clear that, similar to the centeralized CG, large enough \(T\) yields \(F(\mb{x}^{(T)})\geq (1-\frac{1}{\mathrm{e}})\texttt{OPT}\). This simple framework has an advantage over centralized CG, it is taking advantage of the computational resources available at each client.

Second consider a more challenging case where clients can send at most \(\tilde{O}(r)\) bits information. We see how this restriction effects the accuracy. Our algorithm, FedCG, proceeds in rounds. Initially \(\mb{x}^{(0)}=0\). On the \(t\)-th round, first, the central server broadcasts the latest model \(\mb{x}^{(t)}\) to all clients. Each client \(i\) after receiving the update sets \(\mb{x}_{i}^{(t)}=\mb{x}^{(t)}\) and performs one step of continuous greedy approach to find a direction that best aligns with her local gradient: \[\begin{align} \label{eq:v} \mb{v}_i^{(t)}\gets\argmax_{\mb{v}\in \mc{P}} \langle \mb{v},\nabla \widehat{f}_i(\bx_i^{(t)})\rangle \end{align}\tag{2}\] Lastly, clients send their update directions \(\mb{v}_1^{(t)},\dots,\mb{v}_N^{(t)}\) to the secure aggregator to compute \(\Delta^{(t)}=\sum_{i=1}^N p_i \mb{v}_i^{(t)}\). After computing \(\Delta^{(t)}\), the server produces the new global model with learning rate \(\eta\): \[\begin{align} \bx^{(t+1)}\gets \bx^{(t)} + \eta \Delta^{(t)} \end{align}\]

Even in this unrealistic setting where all clients participate in each round the convergence analysis requires new insights. In order to provide an approximation guarantee for our algorithm, we shall obtain a lower bound on the function value improvement by taking the direction \(\Delta^{(t)}\), that is providing a lower bound for \(\langle \Delta^{(t)},\nabla\widehat{F}(\mb{x}^{(t)})\rangle\). However, each \(\mb{v}_i^{(t)}\) is the projection of the local gradient into the matroid polytope and it does not carry information about the magnitude of the expected marginal contributions i.e. \(\|\nabla\widehat{f}_i(\mb{x}^{(t)})\|\). Without assuming an assumption on the heterogeneity of local functions one can construct examples where a single element and corresponding client’s marginal contribution are significantly more dominant than others and hence taking direction \(\Delta^{(t)}\) results in a very bad approximation guarantee.

We therefore need an assumption that acts as a tool in constraining the level of heterogeneity which poses a significant obstacle in federated optimization. A common way to handle heterogeneity is to impose a bound on the magnitude of gradients over each clients’ local function i.e \(\|\nabla \widehat{f}_i(\mb{x})\|\leq \gamma\). This types of assumption is not only common in the literature regarding submodular function maximization in decentralized settings [33], [44], but also in studies of convex and non-convex optimization in federated learning [31], [34], [35], [46], [51].

In the case of submodular functions, each coordinate of the gradient of the multilinear extension corresponds to the marginal gain of adding one single element. In this paper we impose the following assumption which is much more relaxed than assuming a bound on the magnitude of the gradients from each client.

Monotonicity of \(f_i\) implies that for every \(\mb{x}\leq \mb{y}\) coordinate-wise, it holds that \(\widehat{f}_i(\mb{x})\leq \widehat{f}_i(\mb{x})\). Additionally, gradients are antitone i.e., for every \(\mb{x}\leq \mb{y}\) coordinate-wise, it holds that \(\nabla\widehat{f}_i(\mb{x})\geq \nabla\widehat{f}_i(\mb{y})\). Thus as the algorithm advances and \(t\) grows, \(\gamma_t\)’s change but never exceed the upper bound in 3 . Additionally, in numerous instances, \(\max_{t\in [T]}\gamma_t\) is relatively small. For instance, in Max Coverage problem each \(f_i(S)\) is either 0 or 1 , depending if a client is covered by \(S\) or not, thus for this problem \(\gamma=1\).

We now have enough ingredients to prove the following convergence theorem for the case where all clients participate in every communication round. Let \(D=\sum_{t=1}^T\gamma_t\)

3.1 Partial Participation and Client Selection↩︎

Client sampling in the FL optimization framework is imperative for various practical reasons, including the following:

\(\bullet\) Large scale and dynamic nature. In real-world applications, a server usually serves several billions of devices/clients who can join or leave the federated optimization system due to several reasons like intermittent connectivity, technical issue, or simply based on their availability or preferences. Hence, it is computationally inefficient and often impossible to get updates from all clients.

\(\bullet\) Communication and bandwidth. On one hand, waiting for the slowest client to finish can increase the expected round duration as the number of participating clients per training increases, a phenomenon known as “straggler’s effect”. On the other hand, communication can be a primary bottleneck for federated settings because of clients bandwidth limitation and the possibility of server throttling.

\(\bullet\) Small models and redundancy. It is often the case that FL models are small because of clients limited computational power or memory, it therefore is unnecessary to train an FL model on billions of clients. Note that for optimization problem 1 in many practical scenarios models have smaller size in comparison to the number of clients, this is because of the matroid constraint or simply because the size of the ground set is much smaller than the number of clients.

Here we discuss our sampling scheme which crucially does not violate clients’ privacy; see 1.

At each communication round the server chooses an active client from \(i \in [N]\) with probability \(p_i\), and repeats this process \(K\) times to obtain a multiset \(A^{(t)}\) of size \(K\) which may contain a client more than once. Then the aggregation step is \(\Delta^{(t)}=\frac{1}{K}\sum_{i\in A^{(t)}}\mb{v}_i^{(t)}\) where \(\mb{v}_i^{(t)}\) defined in 2 .

The next lemma shows that this sampling scheme is unbiased and in expectation the average update from chosen clients \(A^{(t)}\) is equal to the average update from all clients.

The following lemma allows us to bound the variance which in turn helps to provide our convergence guarantees. To show the following result, it is required to upper bound the difference between the improvement on the function value by taking the direction suggested by a selected client versus taking the direction obtained by averaging all the directions from the clients. That is bounding \(|\langle \mb{v}_{s},\nabla\widehat{F}(\bx^{(t)}) \rangle - \langle \sum_{i=1}^N \mb{v}_i^{(t)}, \nabla\widehat{F}(\mb{x}^{(t)}) \rangle|\), for a selected client \(s\) in \(A^{(t)}\). This in turn needs providing an upper bound for \(\langle \mb{v}_i^{(t)}, \nabla \widehat{f_i}(\mb{x}^{(t)}) \rangle - \langle \mb{v}_s,\nabla\widehat{f}_i(\bx^{(t)}) \rangle\), for all \(i\neq s\). At the heart, our proof relies on the properties of multilinear extensions of local submodular functions, the fact that each \(\mb{v}_i^{(t)}\) corresponds to a base of the matroid, and Assumption 1.

Armed with the above lemmas and concentration inequalities e.g., Chebyshev’s inequality, we can prove the convergence of Algorithm 1. This essentially is done by bounding the error introduced by the decentralized setting and carefully carrying the error through the analysis.

4 Practical Federated Continuous Greedy↩︎

One of the main considerations in federated optimization is the number of communication rounds. In this section, we show how Algorithm 1 can be further improved to reduce communication rounds while simultaneously incorporating partial participation.

Initially \(\mb{x}^{(0)}=0\). On the \(t\)-th round of the Practical Federated Continuous Greedy (FedCG+), the central server first broadcasts the latest model \(\mb{x}^{(t)}\) to a subset of active clients of size \(K\) denoted by \(A^{(t)}\). Next, each client \(i \in A^{(t)}\) sets \(\mb{x}_{i}^{(t,0)}=\mb{x}^{(t)}\) and performs \(\tau\) steps of continuous greedy approach locally. More precisely, let \(j\in\{0,1,\dots,\tau-1\}\) and \(\mb{x}_i^{(t,j)}\) denote the \(i\)-th client’s local model at communication round \(t\) and local update step \(j\), then the local updates are \[\begin{align} \label{eq:update95local} &\widetilde{\mb{v}}_i^{(t,j)}\gets\argmax_{\mb{v}\in \mc{P}} \langle \mb{v},\nabla \widetilde{f}_i(\bx_i^{(t,j)},\zeta_i^{(t,j)})\rangle;\\ &\mb{x}_i^{(t,j+1)} = \mb{x}_i^{(t,j)} + \widetilde{\mb{v}}_i^{(t,j)}/\tau \end{align}\tag{4}\] Here \(\zeta_i^{(t,j)}\) is a set of subsets from the ground set \(E\) sampled according to \(\bx_i^{(t,j)}\), and \(\nabla\widetilde{f}_i(\bx_i^{(t,j)},\zeta_i^{(t,j)})\in \mathbb{R}_{\geq 0}^n\) is an estimation of the gradient \(\nabla\widehat{f}_i(\bx_i^{(t,j)})\) (more on this later).

After \(\tau\) steps of local update, the \(i\)-th client from \(A^{(t)}\) send her update \(\widetilde{\Delta}_i^{(t+\tau)}=\bx_i^{(t,\tau)}-\bx_i^{(t,0)}\) to the secure aggregator to compute \(\widetilde{\Delta}^{(t+\tau)}=\frac{1}{|A^{(t)}|}\sum_{i\in A^{(t)}} \widetilde{\Delta}_i^{(t+\tau)}\). Note that each \(\widetilde{\Delta}_i^{(t+\tau)}\) belongs to \(\mc{P}\) since it is a convex combination of vectors \(\widetilde{\mb{v}}_i^{(t,j)}\in \mc{P}\). However, \(\widetilde{\Delta}_i^{(t+\tau)}\) may not be an integral vector and in the worst case \(\tilde{O}(n)\) bits are required to encode it. After receiving \(\widetilde{\Delta}^{(t+\tau)}\), the server produces the new global model with learning rate \(\eta\): \[\begin{align} \bx^{(t+\tau)}\gets \bx^{(t)} + \eta\widetilde{\Delta}^{(t+\tau)} \end{align}\] Evaluating the multilinear extension involves summing over all subsets \(S\) of \(E\), there are \(2^{|E|}\) such subsets. However, recall \(\partial\widehat{f}/\partial\mb{x}(e)=\E[f(R\cup\{e\})]-\E[f(R\setminus \{e\})]\) where \(R\subseteq E\) is a random subset sampled according to \(\mb{x}\). Hence a simple application of Chernoff’s bound tells us by sampling sufficiently many subsets we can obtain a good estimation of \(\nabla \widehat{f}(\mb{x})\) [10], [17] (more details in the Appendix). For large enough \(m\), let \(\zeta_{i}^{(t,j)}=\{R_i^{(t,j,1)},\dots,R_i^{(t,j,m)}\}\) be subsets of \(E\) that are sampled independently according to \(i\)-th client’s local model \(\mb{x}_i^{(t,j)}\). Let \(\nabla\widetilde{f_i}(\mb{x}_i^{(t,j)},\zeta_{i}^{(t,j)})\) denote the stochastic approximation of \(\nabla\widehat{f_i}(\mb{x}_i^{(t,j)})\). Then with probability \(1-\delta\) we have \(\|\nabla\widehat{f_i}(\mb{x}_i^{(t,j)}) -\nabla\widetilde{f_i}(\mb{x}_i^{(t,j)},\zeta_{i}^{(t,j)})\|\leq \sigma\).

In convergence analyses of our algorithm there are two sources of randomness, one in the sampling schemes for client selection and the other in data sampling at each clients local data to estimate the gradients. In Algorithm 2 there are \(\frac{T}{\tau}\) communications rounds between the server and clients. Define \(\mc{I}_\tau=\{\tau i\mid i =1, 2, 3,\dots\}\) to denote the set of communication rounds with the server. Similar to Lemma 1:

Bounding the variance of \(\langle \widetilde{\Delta}^{(t+\tau)},\nabla\widehat{F}(\bx^{(t)}) \rangle\) is much more delicate than in Lemma 2. The are two main reasons, one is the deviation caused by local steps, second is the deviation from the true \(\nabla\widehat{F}(\mb{x}^{(t)})\) caused by gradient estimations. To handle the deviation cause by local steps we assume all \(\widehat{f}_i\) have \(L\)-Lipschitz continuous gradients i.e., \(\|\nabla\widehat{f}_i(\mb{x})-\nabla\widehat{f}_i(\mb{y})\|\leq L\|\mb{x}-\mb{y}\|\), \(\forall\mb{x},\mb{y}\in\mc{P}\). In fact as shown in Lemma 3 of [52], for each \(\widehat{f}_i\) and local model \(\mb{x}_i^{(t,j+1)}=\bx_i^{(t,j)} + \widetilde{\mb{v}}_i^{(t,j)}/\tau\), it holds that \[\begin{align} \left\| \nabla\widehat{f}_i(\mb{x}_i^{(t,j+1)})-\nabla\widehat{f}_i(\bx_i^{(t,j)}) \right\| & \leq \frac{m_{f_i}\sqrt{r}}{\tau}\left\|\widetilde{\mb{v}}_i^{(t,j)}\right\| \\ & \leq \frac{m_{f_i} r}{\tau} \end{align}\] The factor \(-m_{f_i}\) is in fact a lower bound on the entries of the Hessian matrix. That is \(\frac{\partial \widehat{f}_i}{\partial \mb{x}(i)\partial \mb{x}(j)}\geq -m_{f_i}\) [45].

Let \(Q=\sum_{t\in I_\tau} L_t\) where \(L_t\) is such that for all \(i\in[N]\) and \(j\in[\tau]\) it holds \[\begin{align} \left \| \nabla \widehat{f_i}(\bx_i^{(t,j)}) - \nabla \widehat{f_i}(\bx^{(t)}) \right \| \leq L_t\| \mb{x}_i^{(t,j)} - \mb{x}^{(t)} \| \end{align}\] Observe that \(L_t\) is upper bounded by \(\max_{i} m_{f_i}\sqrt{r}\).

While the variance can be made arbitrary small by sampling more clients, the additive error caused by local steps cannot be controlled by sampling more clients. This shows up in the next theorem.

5 Discrete Algorithm in Federated Setting↩︎

While parallel SGD and continuous methods such as ours in this paper are commonly used as the main tool in federated optimization, we introduce a rather discrete approach to the field and believe it will find further applications. Our approach is inspired by recent works of [54], [55] on a seemingly unrelated topic. [54] introduced a method to sparsify a sum of submodular functions in a centralized setting which was improved by [55]. We tailor their approach to the federated setting and discuss its effectiveness for discrete problems such as Facility Location and Maximum Coverage problems. At the heart of this approach is for clients to know their “importance” without sharing sensitive information. In the monotone case, the importance factor for client \(i\) is defined as: \[w_i = \max_{e\in E} \frac{f_i(\{e\})}{F(\{e\})}.\] In several cases such as Max Facility Location and Maximum Coverage computing the importance factor can be done efficiently and with constant number of communication rounds. For now, let us continue by assuming each client knows its own importance factor.

Let \(\varepsilon\in(0,1)\) and set \(S=\emptyset\). The server gradually adds elements to \(S\) for only \(r\) rounds. At round \(t\) the central server broadcasts the current set \(S\) to all clients (or a subset of active clients). Then each client \(i\) computes the marginal contribution of each element from \(E\setminus S\) to its local function \(f_i\) \[\begin{align} \Delta_i[e]=f_i(S\cup \{e\})-f_i(S); \quad \forall e: S\cup\{e\}\in \mc{I} \end{align}\] Let \(\kappa=\tilde{O}(rn/\varepsilon^2)\). Then each client sends its update in a randomized response manner, that is, the \(i\)-th client with probability \(\kappa_i=\min\{1,\kappa\cdot w_i\}\) sends the scaled vector \((\frac{1}{\kappa_i})\Delta_i\) to the secure aggregator, and with the complement probability does not send anything. The secure aggregator computes \(\Delta^{(t)}\); the sum of the update vectors it has received. The server updates \(S\gets S\cup \{\argmax_{e:S\cup\{e\}\in \mc{M}}\Delta^{(t)}[e]\}\). The following theorem follows from the sparsification results in [54], [55] and approximation guarantees of the greedy algorithm [38].

Let \(\mc{C}\) be a set of \(N\) clients and \(E\) be a set of facilities with \(|E|=n\). For \(c:\mc{C}\times E\to \zR\) let the \(i\)-th client’s score function over a subset of facilities be \(f_i(A)=\max_{j\in A} c(i,j)\). The objective for Max Facility Location is \(\max_{S\subseteq E,|S|\leq k} \sum_{i=1}^N \max_{j\in S} c(i,j)\). For each client \(i\) the importance factor is \(w_i = \max_{j\in E}\frac{c(i,j)}{ F(\{j\})}\).

In several situations computing the importance factors is straightforward. For instance, in movie recommendation systems where a facility location objective is used (see 10), the average rating i.e., \(F(\{j\})\), for all movies are publicly available. Hence, each client knows its own importance factor. Having \(w_i\), we can apply Algorithm 3. Doing so, note that at each round the expected number of clients participating is \(\tilde{O}(kn^2/\varepsilon^2)\), independent of \(N\).

In other situations, clients can compute their importance factors in a federated setting, using a secure aggregator and without sharing their data with other clients. Further details on this and discussions about the Max Coverage problem are presented in 10.

6 Conclusions and Future Work↩︎

We present FedCG, the first algorithm for decomposable submodular maximization in federated setting under matroid constraints. FedCG is based on the continuous greedy algorithm and achieves the best possible approximation factor i.e., \(1-1/\mathrm{e}\) under mild assumptions even faced with client selection and low communication rounds. Additionally, we introduce a new federated framework for discrete problems. Our work leads to many interesting directions for future work, such as providing stronger privacy guarantee using differentially private methods [39]–[41], finding a lower bound on the bit complexity, and improving the additive errors of our algorithms.

Acknowledgements↩︎

I would like to thank Arya Mazumdar and Barna Saha for their many useful discussions and for reading several drafts of this paper. I would also like to thank Yuichi Yoshida for his valuable discussions and inspiring comments on the paper. Additionally, I am grateful to Nazanin Mehrasa, Wei-Ning Chen, Heng Zhu, and Quanquan C. Liu for insightful comments on this work.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

7 Preliminary Results and Proof of Convergence for Full Participation↩︎

7.0.0.1 Quick overview.

At the heart of the analyses for the approximation ratio of the Centralized Continuous Greedy is to show that at each iteration the algorithm reduces the gap to the optimal solution by a significant amount [17]. We follow the same general idea although there are several subtleties that we should address. Mainly, it is required to compare the improvement we obtain by taking direction \(\mb{v}\) versus the improvement obtained by taking direction \(\sum_{i=1}^N p_i\mb{v}_i\) where \(\mb{v}=\argmax_{\mb{y}\in\mc{P}}\langle \mb{y},\nabla\widehat{F}(\mb{x})\rangle\) and \(\mb{v}_i=\argmax_{\mb{y}\in\mc{P}}\langle \mb{y},\nabla\widehat{f}_i(\mb{x})\rangle\). To establish a comparison between the two, we need several intermediate lemmas.

We start off by focusing on providing an upper bound on \(\texttt{OPT}-\widehat{F}(\mb{x})\).

The following is an immediate consequence of Lemma 5.

Next we use Assumption 3.1 to bound the difference between \(\sum_{i=1}^N p_i\langle \mb{v}_i^{(t)}, \nabla \widehat{f_i}(\mb{x}^{(t)}) \rangle\) and \(\sum_{i=1}^N p_i\langle \mb{v}_i^{(t)}, \nabla \widehat{F}(\mb{x}^{(t)}) \rangle\) at every iteration \(t\).

7.1 Putting Everything Together: Proof of 1↩︎

We now are ready to prove 1.

7.2 Upper Bound for \(\gamma_t\) in 1↩︎

Inequality 3 in 1 can be derived using monotonicity and submodularity as follows. For simplicity we drop \(t\). \[\begin{align} |\nabla \widehat{f}_i(\mathbf{x}) - \nabla \widehat{F}(\mathbf{x})|_\infty & = \max_{e\in E} |[\nabla \widehat{f}_i(\mathbf{x})]_e - [\nabla \widehat{F}(\mathbf{x})]_e| \\ & \leq \max_{e\in E} [\nabla \widehat{f}_i(\mathbf{x})]_e + [\nabla \widehat{F}(\mathbf{x})]_e (\mathbf{x})]_e, [\nabla \widehat{f}_i(\mathbf{x})]_e\geq 0}\\ &\leq \max_{e\in E} \max_{i} [\nabla \widehat{f}_i(\mathbf{x})]_e + [\nabla \widehat{f}_i(\mathbf{x})]_ep_i f_i and \sum_i p_i =1} \\ & = 2 \max_{e\in E} \max_{i} [\nabla \widehat{f}_i(\mathbf{x})]_e\\ & = 2 \max_{i} \max_{e\in E} [\nabla \widehat{f}_i(\mathbf{x})]_e \\ & = 2 \max_{i} m_{f_i} \end{align}\]

8 Proof of Convergence for FedCG (2)↩︎

In order to prove the approximation guarantee of 2, several steps are taken. First we show that our client sampling scheme is unbiased and furthermore we provide an upper bound for the variance.

8.1 Bounding the Variance↩︎

8.1.0.1 Unbiased client selection.

Here we prove that our client selection is unbiased (1).

8.1.0.2 Bounding the variance.

Bounding the variance is at the core of our proof of convergence. Recall the definition of \(\gamma_t\) in 1 which plays a pivotal role in bounding the variance.

8.2 Putting Everything Together: Proof of 2↩︎

We now are ready to prove 2.

9 Proof of Convergence for FedCG+ (3)↩︎

9.1 Bounding the variance↩︎

9.1.0.1 Unbiased client selection.

Here we prove that our client selection is unbiased (3). The proof is almost identical to the one for 1. We present a proof here for the sake of completeness.

9.1.0.2 Bounding the variance.

Bounding the variance is at the core of our proof of convergence. 1 plays a pivotal role in bounding the variance. The main difficulty and difference between this proof and the proof of 2 is that firstly the variance is effected by the divergence caused by local steps, and secondly \(\widetilde{\Delta}_{i}^{(t+\tau)}\) may not be integral vectors and it could potentially have \(O(n)\) nonzero entries.

In order to handle the divergence caused by local steps we assume Lipschitzness. First, let us derive useful inequalities using the Lipschitzness condition.
Consider \(t\)-th iteration and recall the definition of \(L_t\) i.e., \(L_t\) is such that for all \(i\in[N]\) and \(j\in[\tau]\) it holds \[\begin{align} \left \| \nabla \widehat{f_i}(\bx_i^{(t,j)}) - \nabla \widehat{f_i}(\bx^{(t)}) \right \| \leq L_t\| \mb{x}_i^{(t,j)} - \mb{x}^{(t)} \| \end{align}\]

where \(\mb{x}_i^{(t)}=\mb{x}^{(t)}\) and \(\mb{x}_i^{(t,j)}\) are the local models for client \(i\) at time step \(t\) and \(t+j\), respectively. We first bound the divergence of \(\mb{x}_i^{(t,\tau)}\) from \(\mb{x}^{(t)}\). \[\begin{align} \left\| \mb{x}_i^{(t,\tau)} - \mb{x}^{(t)} \right\| = \left\| \frac{1}{\tau} \sum_{j=0}^{\tau-1} \widetilde{\mb{v}}_i^{(t,j)} \right\| \leq \frac{1}{\tau} \sum_{j=0}^{\tau-1} \left\| \widetilde{\mb{v}}_i^{(t,j)} \right\| \leq \sqrt{r} \end{align}\] Since \(\widetilde{\mb{v}}_i^{(t,j)}\in\mc{P}\), the same upper bound holds for every \(0\leq j\leq\tau\); \(\| \mb{x}_i^{(t,j)} - \mb{x}^{(t)} \|\leq \sqrt{r}\). Assuming \(L_t\), for all \(0\leq j\leq \tau\), \[\begin{align} \label{eq:Lipschitz} \left \| \nabla \widehat{f_i}(\bx_i^{(t,j)}) - \nabla \widehat{f_i}(\bx^{(t)}) \right \| \leq L\| \mb{x}_i^{(t,j)} - \mb{x}^{(t)} \| \leq L_t \sqrt{r} \end{align}\tag{11}\] Note \(\zeta_i^{(t,j)}\) are sampled according to \(\bx_i^{(t,j)}\), and \(\nabla\widetilde{f_i}(\mb{x}_i^{(t,j)},\zeta_{i}^{(t,j)})\) estimates \(\nabla\widehat{f_i}(\mb{x}_i^{(t,j)})\) within factor \(\sigma\) i.e., \(\|\nabla\widehat{f_i}(\mb{x}_i^{(t,j)}) -\nabla\widetilde{f_i}(\mb{x}_i^{(t,j)},\zeta_{i}^{(t,j)})\|\leq \sigma\). Hence, given this estimation and equation 11 , for every \(0\leq j\leq\tau\) it holds that \[\begin{align} \label{eq:Lipschitz-estimate} \left \| \nabla\widetilde{f_i}(\mb{x}_i^{(t,j)},\zeta_{i}^{(t,j)}) - \nabla \widehat{f_i}(\bx^{(t)}) \right \| \leq \sigma+L_t \sqrt{r} \end{align}\tag{12}\]

9.2 Proof of 3↩︎

9.2.0.1 Convergence of FedCG+.

While at the high level this proof is similar to the previous convergence proofs in Theorems 3.2, 3.5, it still requires taking care of the error caused due to the local steps. (This is an additive error term that cannot be controlled by sampling more clients at each round.)

9.2.0.2 Proof of Claim 7

9.3 Gradient Estimation↩︎

In terms of computation cost on clients’ devices, we point out that the definition of multilinear extension involves summing over all subsets \(S\) of \(E\). There are \(2^{|E|}\) such subsets, thus even computing \(\widehat{g}(\mb{x})\) for a single \(\mb{x}\) could take exponential time. However, we can randomly sample \(m\) subsets \(R_1,\dots,R_m\) of \(E\) according to \(\mb{x}\). Then a simple application of Chernoff’s bound shows for any multilinear extension \(\widehat{g}\) and \(\mb{x}\), \(\left| \frac{1}{m}\sum_{i=1}^m g(R_i) - \widehat{g}(\mb{x})\right|\leq \sigma\max_{S}g(S)\) [10], [17] with probability at least \(1-\mathrm{e}^{-m\sigma^2/4}\). Observe that \(\frac{\partial \widehat{g}}{\partial \mb{x}(e)}=\E[g(R\cup\{e\})]-\E[g(R)]\) where \(R\) is a random subset of \(E\setminus\{e\}\) sampled according to \(\mb{x}\). Hence, by a similar argument, with \(m\) random samples, we can compute an \(\sigma\)-approximation of \(\nabla\widehat{g}(\mb{x})\) with \(1-\mathrm{e}^{-m\sigma^2/4}\) probability. By suitably choosing \(m\) as in Algorithm 2, we can assume the gradients are estimated within \((1\pm\sigma)\) accuracy with high probability.

The above discussion yields:

10 Discrete Algorithm in Federated Setting: Examples↩︎

We consider two well-studied problems, namely Facility Location and Maximum Coverage problems and discuss the details of how to compute importance factors in federated setting efficiently and prove that the expected number of clients participating in each round is small for these two problems.

10.1 Facility Location Problem↩︎

Let \(\mc{C}\) be a set of \(N\) clients and \(E\) be a set of facilities with \(|E|=n\). For \(c:\mc{C}\times E\to \zR\) let the \(i\)-th client’s score function over a subset of facilities be \(f_i(A)=\max_{j\in A} c(i,j)\). The objective for Max Facility Location is \[\begin{align} \max_{S\subseteq E,|S|\leq k} \left\{ F(A)=\sum_{i=1}^N \max_{j\in A} c(i,j)\right\} \end{align}\]

For each client \(i\) the importance factor is \(\max\limits_{j\in E}\frac{c(i,j)}{ F(\{j\})}\).

In many applications computing importance factors is straightforward. Let us elaborate on this with an real-world application.

10.1.0.1 Movie recommendation system.

Consider a movie recommendation application [56] where each client \(i\) has a user-specific utility function \(f_i\) to evaluate sets of movies. The global task is to find a set of \(k\) movies that are most satisfactory to all the clients. An example is the MovieLens dataset consisting of 1 million ratings by \(N=6041\) clients for \(|E|=n=4000\) movies. It is in the interest of clients that we respect their privacy and they are reluctant to share their rating with a central server and other clients. We consider a well motivated objective function. Let \(r_{i,j}\) denote the rating of client \(i\) for movie \(j\) (if such a rating does not exist set \(r_{i,j}=0\)). We associate to each client \(i\) a facility location objective function \(f_i(S)=\max_{j\in S} r(i,j)\) where \(S\subseteq E\) is a subset of movies. The servers objective is \(\max_{S\subseteq E,|S|\leq k} \frac{1}{N}\sum f_i(S)\). In this example, the average rating of each movie is publicly available. That is \(F(\{j\})=1/N\sum_{i=1}^N f_i(\{j\})\) for each movie \(j\) is publicly available. Hence, it is straightforward for each client to compute its own importance factor.

10.1.0.2 Computing importance factors in federated setting.

It is straightforward to see each client can compute its corresponding importance factor in a federated setting and using a secure aggregator without sharing its data with other clients. Each client \(i\) sends a vector \((c(i,1),\dots,c(i,n))\) to the server and by simply summing up these vectors the server has a histogram over facilities. This histogram is then broadcasts to the clients where they can compute their own importance factor; see Algorithm 4). Furthermore, Algorithm 4 requires only two communication rounds.

Having \(w_i\) on hand we can execute Algorithm 3 for Max Facility Location problem. Note that, in this problem we are dealing with a uniform matroid of rank \(k\).

10.2 Maximum Coverage Problem↩︎

Let \(\mc{C}=\{C_1,\dots,C_N\}\) be a set of clients and \(E=\{G_1,\dots,G_n\}\) be a family of sets where each \(G_i\subseteq \mc{C}\) is a group of clients. Given a positive integer \(k\), in the Max Coverage problem the objective is to select at most \(k\) groups of clients from \(E\) such that the maximum number of clients are covered, i.e., the union of the selected groups has maximal size. One can formulate this problem as follows. For every \(i\in [N]\) and \(A\subseteq [n]\) define \(f_i(A)\) as \[\begin{align} f_i(A)= \begin{cases} 1 & \text{if there exists a\in A such that C_i\in G_a} ,\\ 0 & \text{otherwise.} \end{cases} \end{align}\] Note that \(f_i\)’s are monotone and submodular. Furthermore, define \(F(A)=\sum_{i\in [N]}f_i(A)\) which is monotone and submodular as well. Now the Max Coverage problem is equivalent to \[\begin{align} \max_{A\subseteq [n],|A|\leq k} \left\{F(A)=\sum_{i\in [N]}f_i(A)\right\} \end{align}\] For each client \(C_i\), its importance factor \(w_i\) is \(\max\limits_{\substack{G_a\in E, C_i\in G_a}}\frac{1}{|G_a|}\).

10.2.0.1 Computing importance factors in federated setting.

Having a histogram over the group sizes suffices for computing the importance factors. Similar to Facility Location the importance factors can be computed in federated setting by having the membership histograms over the groups; see Algorithm 5.

Having \(w_i\), we can execute Algorithm 3 for Max Coverage problem. Note that, in this problem we are dealing with a uniform matroid of rank \(k\).

References↩︎