1 Introduction↩︎

Submodular maximization is a fundamental problem in a broad range of applications such as sensor selection [1], resource allocation [2], and task coordination with multi-agent systems [3]. In its general form, the problem aims to maximize a set function subject to certain combinatorial constraints, such as cardinality or matroid constraints. Despite its applicability, this class of problems is known to be \(\mathrm{NP}\)-hard [4] and hence its exact solutions are computationally intractable in general. As a consequence, a substantial body of research has focused on the development of efficient approximation algorithms with provable performance guarantees. A rich line of such work has established that constant-factor approximation ratios, e.g., \(1/2\) or \(1-1/e\), can be achieved via greedy-based methods or their continuous variants [5]–[7]. Additionally, these guarantees are further shown to be optimal unless \(\mathrm{P}=\mathrm{NP}\) [4]. Such a result has provided a solid theoretical foundation for designing algorithms that achieve near-optimal performance guarantees while remaining computationally tractable.

Beyond the classical centralized problem, there has been a growing interest in studying distributed submodular maximization, see e.g., [8]–[11], motivated by large-scale decision-making scenarios over multi-agent networks. One typical class of distributed problems arises when agents possess distributed action subsets, and feasibility is enforced through combinatorial constraints coupling all agents’ decisions, e.g., [11], [12]. A canonical example is the partition matroid constraint [13], where the ground action set is partitioned over multiple agents and each one is allowed to select one or a few actions only from its local set. To solve the distributed submodular maximization under such constraints, the authors in [12] propose a solution method that combines the classical continuous greedy algorithm (also known as the Frank-Wolfe algorithm) with the consensus-based coordination scheme. However, this method relies on the exact gradient evaluation of the multi-linear extension of the submodular objective function, leading to computational complexity that grows exponentially with the size of the action set. To address this issue, the authors in [13] develop a distributed algorithm by following the same Frank-Wolfe framework but leveraging the empirical estimate of the gradient information. It is shown that the approximation ratio can be arbitrarily close to the optimal \(1-1/e\) as the number of samples for the gradient estimation increases. Besides, our previous work [11] proposes a stochastic gradient-based distributed algorithm which also considerably reduces the computational complexity of gradient evaluation. However, since the algorithm in [11] is developed completely in a discrete domain, its approximation ratio is only guaranteed to be \(1/2\) which is suboptimal compared to algorithms developed in the continuous domain.

Another rich line of work on submodular maximization has focused on the online setting, where a sequence of submodular objective functions is revealed over time and decisions must be made sequentially without access to future information. In this setting, the goal is to design an online algorithm that generates a sequence of decisions which maximizes the cumulative value of the time-varying objective functions. Specifically, the notion of cumulative \(\alpha\)-regret, e.g., \(\alpha = 1/2\) or \(1-1/e\), is utilized to characterize the performance of such online algorithms. If the cumulative \(\alpha\)-regret grows sublinearly with respect to the time horizon \(T\), then the time-averaged performance of the algorithm asymptotically matches that of the \(\alpha\)-suboptimal solution chosen in hindsight. To this end, the authors in [14] propose the first online submodular maximization algorithm by using the meta-action technique in the discrete domain. It is shown that the algorithm achieves \(\mathcal{O}(\sqrt{T})\) \((1-1/e)\)-regret under the cardinality constraint. This result is further extended in [15] to the problem with partition matroid constraints. By employing a standard lifting technique, i.e., lifting the discrete problem into the continuous domain followed by a proper rounding scheme, the same regret guarantee is established.

In fact, the meta-action idea introduced in [14] has also been applied to online continuous submodular maximization problems; see e.g., [16]–[18]. In particular, the Meta-Frank-Wolfe algorithm is first proposed in [16] and shown to reproduce the \(\mathcal{O}(\sqrt{T})\) \((1-1/e)\)-regret under general convex set constraints. However, a critical limitation of this approach is that it requires \(\sqrt{T}\) evaluations of the exact gradient at each time \(t\), which can be prohibitively expensive in practical scenarios. To alleviate this issue, the authors in [17] enhance the Meta-Frank-Wolfe algorithm by using stochastic gradient estimates and prove that the same regret result can be achieved under mild conditions. Nevertheless, the number of gradient evaluations remains on the order of \(\sqrt{T}\), which may still be expensive for large-scale problems. Motivated by such a challenge, a one-shot version of the online algorithm, termed Mono-Frank-Wolfe, is developed in [18]. It is shown that this algorithm reduces the number of per-function gradient evaluations from \(\sqrt{T}\) to one and achieves an \(\mathcal{O}({T}^{4/5})\) \((1-1/e)\)-regret. In addition, by applying the one-point gradient estimator [19], the authors in [18] further adapt the algorithm development with a bandit feedback model and propose the first bandit submodular maximization method that achieves an \(\mathcal{O}({T}^{8/9})\) \((1-1/e)\)-regret. Additional related works can also be found in [20]–[22].

It is noteworthy that, by using the standard lifting technique, the aforementioned continuous algorithms can all be adopted to solve the discrete online submodular maximization problem. However, a critical limitation of such approaches is that they may require evaluating function values at sampled points that violate the original set constraints, such as (partition) matroid or cardinality constraints. Indeed, [18] shows that there is no proper rounding scheme that can simultaneously guarantee the unbiased gradient estimation and the feasibility of the resulting discrete samples. As a result, the responsive bandit algorithm is proposed in [18] which assigns zero rewards to the infeasible samples but still requires querying the function values at such violating points. In this paper, we aim to resolve the sampling violation issue.

More recently, a few attempts have been made to study submodular maximization problems in both distributed and online settings, see e.g., [23]–[25]. The authors in [23] consider the distributed online continuous submodular maximization problem in which each agent observes a local sequence of objective functions and all agents are subject to a common convex set constraint. Two distributed online algorithms are then presented, and their \((1-1/e)\)-regrets are shown to be upper bounded by \(\mathcal{O}({T}^{4/5})\) and \(\mathcal{O}(\sqrt{T})\), respectively. To address the distributed setting with separate action subsets across agents, our previous work [25] develops an online distributed greedy algorithm in the purely discrete domain, which is shown to inherently achieve an \(\mathcal{O}(\sqrt{T})\) \(1/2\)-regret. To the best of the authors’ knowledge, no existing work addresses distributed online submodular maximization under partition matroid constraints while achieving the optimal \((1-1/e)\)-regret. Closing this gap, as we detail below, requires more than assembling existing techniques.

The contributions of this paper are summarized below:

(i) We first formulate a distributed online submodular maximization problem under partition matroid constraints, and then propose a unified algorithmic framework that combines the lifting technique with the Meta-Frank-Wolfe algorithm, accommodating both full-information and bandit feedback models. To the best of the authors’ knowledge, this is the first framework to achieve the optimal \((1-1/e)\)-regret for this problem.

(ii) For the full-information and bandit models, we establish the \(\mathcal{O}({T}^{4/5})\) and \(\mathcal{O}({T}^{8/9})\) \((1-1/e)\)-regret bounds, respectively, which match the known centralized rates while operating in a fully distributed manner over the network.

(iii) To address the sampling violations inherent to online rounding under set constraints, we introduce bounded stochastic pipage rounding (B-SPR), which generalizes pipage rounding to arbitrary fractional bounds while retaining its sum and monotonicity guarantees. Embedding B-SPR into a progressively bounded scheme (PB-SPR) then drives the iterates toward a matroid vertex. We prove that per-step violation probability vanishes as \(\mathcal{O}(T^{-1/9})\), so the cumulative violation grows only sublinearly as \(\mathcal{O}(T^{7/9})\). A matching \(\Omega(T^{7/9})\) lower bound certifies that this rate is not improvable under certain conditions.

Notations: The sets of integers and real numbers are denoted as \(\mathbb{Z}\) and \(\mathbb{R}\), respectively. For any given integer \(n\in\mathbb{Z}_{\ge1}\), let \([n]:=\{1,2,\cdots,n\}\) and \(\mathbf{1}_n\) denote the \(n\)-dimensional one vector. For a set \(S\), let \(|S|\) be the cardinality of the set. For two vectors \(\mathbf{x},\mathbf{y} \in \mathbb{R}^n\), the inequality \(\mathbf{x} \preceq \mathbf{y}\) is defined element-wise. \(\mathbb{1}\{\cdot\}\) denotes the indicator function.

2 Problem Statement and Preliminaries↩︎

2.1 Distributed Online Submodular Maximization↩︎

Consider a network of \(I\) agents, where each agent \(i\in [I]\) maintains a local action subset \(\mathcal{A}_i \subseteq \mathcal{A} := \cup_{i=1}^I\mathcal{A}_i\) with \(|\mathcal{A}_i| = N_i\) and \(|\mathcal{A}| = N\). The objective of each agent is to select at most \(\kappa_i \in \mathbb{Z}_{\ge 1}\) actions from \(\mathcal{A}_i\), such that a sequence of time-varying or even adversarial objective functions \(f^1(\mathcal{S})\), \(f^2(\mathcal{S}), \cdots, f^T(\mathcal{S})\) is cooperatively maximized over the time horizon \(T \in \mathbb{Z}_{\ge 1}\). Such a problem can be formulated as the distributed maximization, \[\tag{1} \begin{align} \text{maximize}\;\;\, &f^t(\mathcal{S})\tag{2}\\ \text{subject to}\;\;\, & \mathcal{S} \in \mathcal{I} :=\{ \mathcal{S} \,\big\vert\, |\mathcal{S} \cap \mathcal{A}_i |\le \kappa_i, \;i \in [I] \}.\tag{3} \end{align}\] Notice that, by assuming \(\mathcal{A}_i \cap \mathcal{A}_j =\emptyset,\,\forall i\neq j\), the set \(\mathcal{I}\) in 3 is known as a partition matroid [12]. Moreover, we assume that each function \(f^t(\cdot): 2^\mathcal{A} \to \mathbb{R}_{\ge0}\) is monotone, submodular, and normalized, whose definitions are provided as follows.

In addition to the properties of monotonicity and submodularity, it is often useful if the set function is also normalized, i.e., \(f(\emptyset) = 0\). Without loss of generality, this property can be enforced by adding an appropriate constant to the function [1].

In this work, we focus on an online setting of the submodular maximization problem where the agents have no a priori knowledge of the objective functions. Specifically, at each time \(t \in [T]\), each agent selects a subset of actions \(\mathcal{S}^t_i \subseteq \mathcal{A}_i\) such that \(|\mathcal{S}^t_i| \le \kappa_i\). After all agents commit to their decisions \(\mathcal{S}^t_i\)’s, a potential adversary selects an objective function \(f^t(\cdot)\) and certain information regarding the function is revealed to the agents. In the full-information feedback model, the agents have access to the full knowledge of \(f^t(\cdot)\) and thus can evaluate the function value for any selections of actions. By contrast, in the bandit feedback model, only the function value of selected decisions, i.e., \(f^t(\cup_{i=1}^I \mathcal{S}_i^t)\), can be observed, leading to a more challenging setup for the decision-making of agents. Although the agents have no knowledge of \(f^t(\cdot)\) when selecting \(\mathcal{S}_i^t\), they may exploit previously revealed functions to guide their decisions. The problem where the sequence \(\{f^t(\cdot)\}_{1\le t\le T}\) is arbitrary is often referred to as an adversarial online setting [17]. In this setting, the goal of agents is to cooperatively minimize the adversarial cumulative regret given by \[\begin{align} \label{eq:regret} \mathcal{R}_T := (1-1/e)\cdot \max_{\mathcal{S} \in \mathcal{I}} \;\sum_{t=1}^Tf^t(\mathcal{S}) - \sum_{t=1}^T f^t(\cup_{i=1}^I \mathcal{S}_i^t). \end{align}\tag{4}\] The notion of regret in 4 is defined with respect to a joint reward \(f^t(\cup_{i=1}^I \mathcal{S}_i^t)\) received by all agents. Such a reward model has been widely used by many works on the distributed submodular maximization problem, see e.g., [8], [11], [13]. In addition, the factor \(1\!-\!1/e\) in 4 is due to the \(\mathrm{NP}\)-hardness of the standard submodular maximization problem and therefore only approximate solutions can be expected in general by algorithms running in reasonable time [4].

Moreover, we consider that the communication topology of the \(I\)-agent network is modeled by a time-invariant undirected graph \(\mathcal{G}:=\{\mathcal{N}, \mathcal{E}\}\) where \(\mathcal{N} := [I]\) and \(\mathcal{E} \subset \mathcal{N} \times \mathcal{N}\) denote the sets of nodes and edges, respectively. The agent \(i\) receives information from the agent \(j\) if \((i,j) \in \mathcal{E}\). Particularly, we let \(\mathcal{N}_i:=\{j \in [I] \;\vert\; (i,j) \in \mathcal{E}\}\) represent the (in-)neighborhood of the agent \(i\), i.e., the set of agents that can send information to the \(i\)-th agent directly. In addition, it is also assumed that the undirected graph \(\mathcal{G}\) is connected, i.e., every agent \(i\) can receive information from all others through a path. We denote by \(d(\mathcal{G})\) the diameter of \(\mathcal{G}\), i.e., the greatest shortest-path distance over all pairs of agents \((i,j)\). Due to the connectedness of \(\mathcal{G}\), it is easy to verify that \(d(\mathcal{G}) \le I\).

2.2 Multi-Linear Extension↩︎

To achieve the tightest approximation bound for solving the classical submodular maximization problems, a suite of well-studied methods uses the notion of multi-linear extension [26]. To provide a formal definition of the multi-linear extension of a submodular set function, let us assume without loss of any generality that the ground set is given by \(\mathcal{A}=\{1,2,\cdots, N\}\) and the local subsets \(\mathcal{A}_i\)’s contain consecutive integers and are ordered such that, if \(\mathcal{A}_i = \{p,p+1,\cdots, q\}\), then one can have \(p-1 \in \mathcal{A}_{i-1}\) and \(q+1 \in \mathcal{A}_{i+1}\). Associated with \(\mathcal{A}\), we define a continuous variable \(\mathbf{x} = [x(1),x(2),\cdots, x(N)]^\top \in [0,1]^N\). Further, we let the \(i\)-th block of the vector \(\mathbf{x}\) be \([\mathbf{x}]_i \in [0,1]^{N_i}\) whose entries are associated with the local subset \(\mathcal{A}_i\). Using the notations defined above, we can express the multi-linear extension of each function \(f^t(\cdot)\) as \[\begin{align} F^t(\mathbf{x}):=\sum_{\mathcal{S} \subseteq \mathcal{A}} f^t(\mathcal{S}) \cdot\prod_{n \in \mathcal{S}}x(n)\cdot\prod_{n \notin \mathcal{S}}\big(1-x(n)\big). \end{align}\] Corresponding to the partition matroid constraint 1 , we introduce the matroid polytope \(\mathcal{M} \subseteq [0,1]^N\) where \[\begin{align} \label{eq:def-M} \mathcal{M} := \{ \mathbf{x} \in [0,1]^N \,\vert\, \mathbf{1}_{N_i}^\top[\mathbf{x}]_i \le \kappa_i, \; \forall i \in [I]\}. \end{align}\tag{5}\] Similarly, we define the local polytope \(\mathcal{M}_i \subseteq [0,1]^{N_i}\) for each agent \(i\in[I]\) as \[\begin{align} \label{eq:def-Mi} \mathcal{M}_i := \{ \mathbf{x} \in [0,1]^{N_i} \,\vert\, \mathbf{1}_{N_i}^\top \mathbf{x} \le \kappa_i \}. \end{align}\tag{6}\] It is straightforward to have that \(\mathcal{M} = \prod_{i \in[I]} \mathcal{M}_i\).

The above notion of multi-linear extension transfers the classical submodular maximization problem from the discrete domain to the continuous domain. Precisely, the solution to \(\max_{\mathcal{S} \in \mathcal{I}} f(\mathcal{S})\) is equivalent to solving the following continuous optimization [27], \[\begin{align} \label{submodularMax-continuous} \mathop{\text{maximize} }\limits_{\mathbf{x} \in \mathcal{M}} \;\;F(\mathbf{x}). \end{align}\tag{7}\] In addition, even if the suboptimal solution \(\widetilde{\mathbf{x}}\) to 7 is obtained, one can adopt various rounding schemes to recover an approximate discrete solution \(\widetilde{\mathcal{S}}\) that ensures \(f(\widetilde{\mathcal{S}}) \ge F(\widetilde{\mathbf{x}})\). Instances of such lossless methods include pipage rounding [28], central rounding [29], etc.

2.3 Frank-Wolfe Algorithm and Tracking the Expert↩︎

To solve the maximization problem 7 in the continuous domain, a well-studied method is Frank-Wolfe [30], which performs \(\mathbf{x}^{k+1} = \mathbf{x}^k + \eta^k \mathbf{v}^k\) where \(\mathbf{x}^0\) is initialized as \(\mathbf{0}\) and \(\eta^k \in \mathbb{R}_{>0}\) is the step-size. Specifically, the updating direction \(\mathbf{v}^k \in \mathbb{R}^N\) can be obtained by maximizing a linear function under constraints, i.e., \[\begin{align} \label{frank-wolfe} \mathbf{v}^k = \arg\max_{\mathbf{v} \in \mathcal{M}}\;\langle \mathbf{v}, \nabla F(\mathbf{x}^k) \rangle. \end{align}\tag{8}\] It has been shown in [31] that the iterates \(\mathbf{x}^k\) produced by Frank-Wolfe can be arbitrarily close to the \((1-1/e)\) approximate solution, i.e., \(F(\mathbf{x}^k) \to (1 - 1/e)F(\mathbf{x}^\star)\) as \(k \to \infty\) where \(\mathbf{x}^\star\) denotes the optimal solution to 7 .

Although the Frank-Wolfe algorithm provides a promising solution method to the continuous optimization 7 , a critical drawback is that it heavily relies on the gradient \(\nabla F(\cdot)\) during the iterations. However, under the adversarial online setting, one can only have access to the knowledge of function \(F^t(\cdot)\) after committing to the decisions at this round. Therefore, to perform the Frank-Wolfe update, it is required to first obtain a sequence of approximate solutions to the maximization problem 8 without knowing the gradient information [18].

To resolve the above issue, a natural idea is to use the technique of tracking the expert which has been widely adopted in solving online optimization problems. The expert problem involves an agent selecting actions \(a_t \in \mathcal{A}\) to maximize the cumulative reward \(\sum_{t =1}^T r_t(a_t)\) over a finite time horizon \(T \in \mathbb{Z}_{\ge 1}\). The main challenge of such a problem lies in the fact that the time-varying reward \(r_t(\cdot)\) can be unknown to the agent before committing to the action \(a_t\), which is analogous to our adversarial online setting. Consequently, to solve this problem, the agent needs to track an expert’s decision, i.e., the action \(a_T^\star \in\) \(\arg\max_{a \in \mathcal{A}}\, \sum_{t=1}^Tr_t(a)\) leading to the highest cumulative reward in hindsight. Indeed, there have been various approaches proposed in the literature, e.g., Regularized Follow the Leader (RFTL) [19], Follow the Perturbed Leader (FPL) [32], and the online gradient descent [33], which all manage to track the expert. In this work, we specifically adopt the RFTL algorithm, whose performance is guaranteed by the following result (see Theorem 5.1 in [19]): there exists a constant \(C_0 >0\) such that the generated sequence of actions \(\{a_t\}_{1\le t\le T}\) has \[\begin{align} \label{ineq:expert-regret} \max_{a\in\mathcal{A}} \;\sum_{t=1}^T r_t(a) - \sum_{t=1}^T \mathbb{E} [r_t(a_t)] \le C_0 \sqrt{T}, \end{align}\tag{9}\] where the expectation is taken with respect to the randomness of the generation of \(a_t\).

3 Algorithm with Full-Information Feedback↩︎

In this section, we first introduce a vanilla version of the distributed online algorithm under the full-information feedback setting, which also establishes analytical tools for the subsequent extensions.

3.1 Distributed Online Algorithm: A Vanilla Version↩︎

The distributed online algorithm with full-information feedback is outlined in Algorithm 1, which consists of two phases. In the distributed Frank-Wolfe phase, each agent performs a local block-coordinate Frank-Wolfe update (see Line 6) and then reaches a maximum consensus on the local variables \(\mathbf{x}_i^q(k)\)’s with its neighbors (see Line 7), thereby building coordination over the network. The online learning phase, inspired by [18], requires only a one-shot gradient per function. Following a random permutation \(\{t_i^{q,1}, \cdots, t_i^{q,K}\}\) of the indices within block \(q\in[Q]\) (see Line 9), each agent applies the lossless rounding on \([\mathbf{x}_{i}^q(K+1)]_i\) to obtain its discrete decision \(\mathcal{S}_i^t\), which is executed for all time-steps within the block \(q\) (see Line 11). With an appropriate lossless rounding, e.g., the stochastic pipage rounding [28], the joint action \(\mathcal{S}^t = \cup_{i\in [I]} \mathcal{S}_i^t\) is always feasible, i.e., \(\mathcal{S}^t \in \mathcal{I}\) for \(\forall t \in [T]\), and the global reward \(f^t(\mathcal{S}^t)\) is received by all agents. The gradients \(\nabla F^{t_i^{q,k}}(\mathbf{x}_i^q(k))\) evaluated along the permutation mimic the stochastic gradient of the block-averaged function \(\bar{F}(\cdot) = 1/K\cdot\sum_{k=1}^K F^{(q-1)K+k} (\cdot)\) (see Line 13), and an averaging technique [34] is adopted to reduce the variance of the gradient estimate \(\mathbf{d}_i^q(k)\) (see Line 15).

We note that the required gradient \(\nabla F^{t_i^{q,k}}(\mathbf{x}_i^q(k))\) can be conceptually obtained under the full-information model, since each agent has full knowledge of \(f^t(\cdot)\) (or \(F^t(\cdot)\)). Nevertheless, by the definition of multi-linear extension, evaluating the exact gradient is combinatorial in nature and thus computationally intractable even for moderately large problems. A standard remedy is Monte Carlo sampling [13], which still requires full-information feedback; we relax this requirement in the next section.

3.2 Regret Analysis↩︎

We first characterize the consensus performance of the distributed Frank-Wolfe phase in the following lemma.

With the aid of Lemma 1, we are now ready to provide the regret bound of Algorithm 1 in the following theorem. Note that we here assume, for simplicity of presentation, that \(K\) is an even number. This condition can be relaxed by more involved algebraic calculations.

4 Algorithm with Bandit Feedback↩︎

In this section, we adapt the algorithm of Sec. 3 to the bandit feedback model and establish its sublinear regret.

4.1 Distributed Online Bandit Algorithm↩︎

Considering that only bandit feedback is available to the agents, a crucial step for the algorithm development here is to provide a proper estimation of the gradient as required by the previous algorithm. Towards this end, we use the classical one-point gradient estimator [18], [19], which is briefly reviewed as follows. For a function \(F(\cdot): \mathbb{R}^{N} \to \mathbb{R}\), its \(\delta\)-smoothed approximation can be defined as \(\widehat{F}_\delta(\mathbf{x}):= \mathbb{E}_{\mathbf{v} \sim \text{Uni}(\mathbb{B}^N)}\big[F(\mathbf{x} + \delta\mathbf{v})\big]\) where \(\mathbf{v} \in \mathbb{R}^N\) is a sample uniformly drawn from the unit ball \(\mathbb{B}^N\). Then, the gradient of the approximation function is shown to be \(\nabla \widehat{F}_\delta(\mathbf{x}):= N/\delta\cdot \mathbb{E}_{\mathbf{u} \sim \text{Uni}(\mathbb{S}^{N-1})}\big[F(\mathbf{x} + \delta\mathbf{u})\mathbf{u}\big]\), where \(\mathbb{S}^{N-1}\) denotes the unit sphere (see Lemma 6.4 in [19]). Therefore, the value of \(N/\delta\cdot F(\mathbf{x} + \delta\mathbf{u})\mathbf{u}\) can be applied as a one-point unbiased stochastic estimate of the gradient \(\nabla F(\mathbf{x})\). It should be noted that, to ensure the feasibility of the sampled point, i.e., \(\mathbf{x} + \delta\mathbf{u} \in \mathcal{M}\), the gradient can only be estimated when \(\mathbf{x}\) is taken from the interior of \(\mathcal{M}\). Specifically, a notion of \(\delta\)-interior of \(\mathcal{M}\) is defined in [18], i.e., \(\widetilde{\mathcal{M}} := \alpha \mathcal{M} + \delta \cdot \mathbf{1}_N\). It is shown (see Lemma 1 in [18]) that \(\mathbf{x} + \delta \mathbf{u} \in \mathcal{M}\) holds for \(\forall \mathbf{x} \in \widetilde{\mathcal{M}}\) and \(\mathbf{u} \in \mathbb{S}^{N-1}\), if \(\alpha\) is chosen as \(\alpha = 1- (\sqrt{N}+1)\delta/\gamma\) where \(\gamma>0\) denotes the radius of a ball whose positive orthant is contained in \(\mathcal{M}\). Thus, to validate the stochastic gradient estimation, we next restrict \(\mathbf{x}\) to be in the \(\delta\)-interior set \(\widetilde{\mathcal{M}}\).

Applying the above one-point gradient estimator, the distributed online algorithm with bandit feedback is outlined in Algorithm 2. The distributed Frank-Wolfe phase follows that of Algorithm 1, except that the local variable is restricted to the \(\delta\)-interior \(\widetilde{\mathcal{M}}_i := \alpha \mathcal{M}_i + \delta \cdot \mathbf{1}_{N_i}\) of \(\mathcal{M}_i\). In the online learning phase, each block \(q\) has length \(L\), and while the global reward \(f^t(\mathcal{S}^t)\) is received at every time-step (see Line 11), the one-point gradient estimation is performed only at \(K\) (out of \(L\)) steps (see Lines 13 and 14). The discrete variable \(\mathcal{X}^q_i(k)\) is generated by applying the random rounding on the sample \(\mathbf{x}_{i}^q(k) + \delta\mathbf{u}_{i}^q(k)\), which ensures the unbiasedness \(\mathbb{E}[f^t(\mathcal{X}^q_i(k))]=\) \(F(\mathbf{x}_{i}^q(k) + \delta\mathbf{u}_{i}^q(k))\). As before, an averaging technique is applied to \(\mathbf{d}_i^q(k)\) for variance reduction (see Line 17).

4.2 Regret Analysis↩︎

Similar to the analysis of Algorithm 1, we here first show the consensus result obtained by the distributed Frank-Wolfe phase in Lemma 2, and then provide the regret bound of Algorithm 2 in Theorem 2. Note that the following Lemma 2 is analogous to Lemma 1 in Sec. 3.2, while the only difference is that the iterates \(\mathbf{x}_i^q(k)\) are shown to be in the \(\delta\)-interior set \(\widetilde{\mathcal{M}}:=\alpha \mathcal{M} + \delta\cdot\mathbf{1}_N\).

Theorem 2 shows that Algorithm 2 also achieves sublinear expected regret. Compared to Theorem 1, however, the rate degrades to \(\mathcal{O}(T^{8/9})\) as only bandit feedback is available. Before the end of this section, we would also like to add a few remarks regarding the algorithm and its regret analysis.

5 Bounding the Sampling Violation↩︎

In this section, we extend the previous algorithm development by incorporating a bounded stochastic pipage rounding (B-SPR) technique. By designing a sequence of progressively relaxed bounds, we show that the probability of occurrence of violating samples vanishes as \(T\to \infty\), and furthermore, the cumulative sampling violation is sublinear in \(T\).

5.1 Bounded Stochastic Pipage Rounding↩︎

The B-SPR scheme, as outlined in Algorithm 3, is a generalized variant of the stochastic pipage rounding method. Precisely, the standard pipage rounding scheme converts any \(M\)-dimensional continuous vector \(\mathbf{x} \in [0,1]^M\) to a discrete one \(\mathbf{z} \in \{0,1\}^M\) (given that \(\mathbf{1}_M^\top \mathbf{x}\) is an integer). In contrast, our B-SPR scheme, denoted as \(\mathcal{R}_{b_l}^{b_u}(\cdot)\), generalizes the upper and lower bounds to any fractional numbers \(b_l\) and \(b_u\) such that \(0 \le b_l < b_u \le 1\). We show in the following theorem that the promising properties of the stochastic pipage rounding are preserved by the B-SPR procedure.

Theorem 3 establishes a few fundamental properties of the B-SPR procedure. First, statement i) verifies that the procedure terminates in finite time while preserving the sum of the input vector. Second, statement ii) ensures that at most one element of the output vector \(\mathbf{z}\) takes a value other than \(b_l\) and \(b_u\). More importantly, statement iii) shows that, for any multi-linear extension function, the expected function value does not decrease after applying the B-SPR procedure. This property is crucial for the development of algorithms in the sequel. Intuitively, B-SPR mirrors standard stochastic pipage rounding: it repeatedly transfers mass between two fractional coordinates while preserving their sum. The difference is that each coordinate is rounded toward the box \([b_l,b_u]\) rather than \(\{0,1\}\). The swap probabilities are calibrated so that the multi-linear value does not decrease in expectation. This box-valued generalization precisely enables the progressive-bounding mechanism developed next.

5.2 Distributed Online Algorithm with Progressively Bounded Stochastic Pipage Rounding↩︎

Equipped with the above B-SPR technique, we are now able to tackle the issue of sampling violations as noted in Remark 2. The enhanced distributed online algorithm is outlined in Algorithm 4, in which the distributed Frank-Wolfe phase is integrated with a progressively bounded stochastic pipage rounding (PB-SPR) scheme while the online learning phase follows exactly the same steps as in Algorithm 2. The key idea here is to drive the local variable \([\mathbf{x}_i^q (k)]_i\) to be as close as possible to the vertex of \(\widetilde{\mathcal{M}}_i\). To do so, we let the upper bound \(b_u\) of the PB-SPR procedure increase progressively as \(b_u = \delta+\alpha k/K\), while the lower bound remains unchanged as \(b_l = \delta\) (see Line 6). Due to the features of the B-SPR scheme in Theorem 3, it holds that \(\mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k+1)]_i \le \delta N_i + \alpha \kappa_i k/K\). That is, there are at least \(N_i - \kappa_i\) elements of the vector \([\mathbf{x}_i^q (k+1)]_i\) whose values are \(\delta\). Given that \(\delta\) vanishes as the time horizon \(T \to \infty\), it is expected that the probability of generating a violating sample also vanishes accordingly.

Before proceeding to the probability analysis, we should highlight two challenges that need to be addressed. First, due to the PB-SPR procedure, the elementwise monotonicity of the local variables, i.e., \([\mathbf{x}_i^q (k+1)]_i \succeq [\mathbf{x}_i^q (k)]_i\), no longer holds. As a result, the maximum consensus scheme employed in Algorithms 1 and 2 is not applicable in this case. Nevertheless, thanks to the sum-preserving property of B-SPR (see Theorem 3 statement i)), it holds that \(\mathbf{1}_{N_i}^\top[\mathbf{x}_i^q (k+1)]_i \ge \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q (k)]_i\). As such, we adopt a sum-maximum consensus (see Line 7 in Algorithm 4), whereby each local variable \([\mathbf{x}_i^q(k+1)]_{i'}\) is updated by selecting, from its neighbors, the vector with the largest aggregate value.

More importantly, for the same reason, the discrepancy \(\|\bar{\mathbf{x}}^q(k)-\mathbf{x}_i^q(k)\|\) can no longer be bounded as directly as in the previous analysis. Fortunately, we are able to show that the difference between \(\mathbf{x}_i^q(k+1)\) and \(\mathbf{x}_i^q(k)\) is bounded in expectation by the term \(\mathcal{O}(1/K)\). We next establish such a result in Lemma 3, and then use it to show the desired consensus property in Lemma 4.

With the help of the consensus result in Lemma 4, we are now ready to show the cumulative regret bound of Algorithm 4 in the following theorem.

It has been shown by Theorem 4 that Algorithm 4 retains the same \(\mathcal{O}(T^{8/9})\) regret rate as Algorithm 2 in Theorem 2. Compared to ?? , the only difference is the second last term of ?? , which reflects the consensus result of PB-SPR procedure (see Lemma 4 statement ii)). Since this term grows as \(\mathcal{O}(T^{4/9})\), it is non-dominant and the incorporation of PB-SPR does not compromise the regret bound. We next show that, thanks to PB-SPR, the probability of sampling violation vanishes as \(T \to \infty\).

Theorem 5 shows that, for each agent \(i \in [I]\), the probability of generating a violating sample at each step vanishes at the rate \(\mathcal{O}(T^{-1/9})\), so the cumulative sampling violation grows sublinearly as \(\mathcal{O}(T^{7/9})\). Since sampling occurs only at \(K\) out of \(L\) steps per block, with \(K = T^{2/3}\) and \(Q =T^{2/9}\) the cumulative violation would be naturally bounded by \(\mathcal{O}(T^{8/9})\); the vanishing violation probability in ?? improves this to \(\mathcal{O}(T^{7/9})\) as in ?? . Moreover, as shown next, \(T^{7/9}\) also serves as a lower bound in certain scenarios, implying that the bound ?? is nearly optimal and not improvable under certain conditions.

It has been shown in Proposition 1 that, under the condition \(\mathbf{1}_{N_i}^\top \mathbf{v}_i^q(k) = \delta N_i + \alpha\kappa_i\) and for any sum-preserving operator \(\mathcal{P}(\cdot)\) used to replace PB-SPR in Algorithm 4, the cumulative sampling violation is bounded by \(\Omega(T^{7/9})\). It is worth noting that \(\mathbf{1}_{N_i}^\top \mathbf{v}_i^q(k) = \delta N_i + \alpha\kappa_i\) often holds due to the nature of Frank-Wolfe. To elaborate on this, recall in 8 that the vector \(\mathbf{v}_i^q(k)\) is obtained by maximizing a linear function under the polytope constraint. Hence, \(\mathbf{v}_i^q(k)\) typically corresponds to an extreme point of \(\widetilde{\mathcal{M}}_i\), which naturally satisfies the condition as considered in Proposition 1. In fact, when considering the full-information feedback model as discussed in Sec. 3, the gradient \(\nabla F^t(\cdot)\) is componentwise nonnegative, making the resulting vector \(\mathbf{v}_i^q(k)\) readily satisfy the above condition.

6 Numerical Example↩︎

In this section, we evaluate the performance of the proposed distributed online algorithms through numerical examples. We consider the multi-agent information harvesting problem studied in [13]. Specifically, let \(\mathcal{D} \subset \mathbb{R}^2\) denote a set of information sources and \(\mathcal{B} \subset \mathbb{R}^2\) denote a set of information retrieval points. A team of \(I\) agents is deployed, where each agent \(i\) is allowed to install at most \(\kappa_i \in \mathbb{Z}_{>0}\) information harvesting devices at locations selected from its candidate subset \(\mathcal{B}_i \subset \mathcal{B}\). The objective of agents is to determine the device deployment so as to minimize the aggregate distance between all information sources and devices, which is equivalent to maximizing a normalized monotone submodular function [13].

In this simulation, we consider \(|\mathcal{D}| = 1000\) information sources and \(|\mathcal{B}| = 16\) retrieval points. The positions of information sources and retrieval points are spread over a \(10 \times 10\) region, as shown in Fig. 5. To conform with the online problem setting, we allow the configuration of information sources \(\mathcal{D}_t\) to vary randomly over time \(t \in [T]\). More specifically, at each time \(t\), the set \(\mathcal{D}_t\) is generated according to a Gaussian kernel whose mean moves continuously within the region over the time horizon. The knowledge of \(\mathcal{D}_t\) is not revealed to the agents prior to making decisions at the time \(t\). A team of \(I =4\) agents is employed, whose communication network and local candidate set \(\mathcal{B}_i\) are shown in Fig. 5. Note that all online algorithms implemented in this section apply RFTL [19] as the scheme of tracking the expert. In addition, the cumulative regret \(\widetilde{\mathcal{R}}_T\) is computed against the best decision in hindsight⁴, by a brute-force search.

We first examine the performance of Algorithms 1, 2 and 4, whose cumulative regrets and sampling violation behaviors are shown in Fig. 6. By sampling violation, we mean a gradient-estimation query whose sample is infeasible. We note that such infeasible queries are an unavoidable by-product of the one-point gradient estimator [18], and the role of our PB-SPR scheme is precisely to drive their frequency toward zero. In addition, we also compare the performance of our algorithms against two centralized baselines: i) the classical Meta-Frank-Wolfe, i.e., the centralized counterpart of Algorithm 1; and ii) the responsive bandit algorithm in [18], which operates in a bandit feedback setting where an infeasible query is permitted but earns zero reward. It can be observed from Fig. 6 that the cumulative regrets of our algorithms all grow sublinearly with respect to \(T\). As expected, the full-information Algorithm 1 attains the lowest regret, while the bandit Algorithms 2 and 4 incur a moderately larger regret owing to the more restrictive feedback. Importantly, the incorporation of PB-SPR into the bandit algorithm does not compromise the regret performance. In fact, as suggested in Theorem 3, the function value is non-decreasing in expectation after the B-SPR operation, which is reflected by a slight improvement of Algorithm 4 over Algorithm 2. In addition, it is also observed from Fig. 6 that Algorithm 1 and the centralized Meta-FW achieve essentially coincident regret, which implies that operating over the distributed network incurs negligible loss. Moreover, since the responsive bandit algorithm frequently queries and thus is charged for infeasible samples, it incurs a higher regret than our bandit Algorithms 2 and 4. Most importantly, thanks to PB-SPR, the occurrence of sampling violations is substantially reduced, by roughly \(84\%\) on this simulation instance, as shown in Fig. 6. As the experts progressively concentrate the iterates towards a vertex, the per-block number of violating samples grows for the standard bandit algorithm, whereas PB-SPR keeps it consistently and increasingly lower, as shown in Fig. 6.

To further study how the communication graph shapes the behavior of our distributed algorithms, we next vary the number of agents by \(I\in\{4,8,12,16,24,32,40\}\) and consider three different network topologies: i) an Erdős–Rényi random graph, which remains well-connected with small diameter; ii) a two-dimensional grid graph with medium diameter; and iii) a ring graph with the largest diameter, as shown in Fig. 5. We note that for each instance, the ground set scales as \(N = 4I\). Hence, a brute-force search for the optimal solution may be intractable, and thus the regret here is measured against an offline greedy benchmark. Besides the regret performance and sampling-violation behavior, we also track the metric of consensus error, which quantifies how closely the agents agree on the global decision. Precisely, the consensus error \(\mathcal{J}\) is defined by \[\begin{align} \label{eq:consensus-error} \mathcal{J} := \frac{1}{(I-1)N}\sum_{j=1}^{I}\sum_{i\neq j} \big\| [\mathbf{x}_{i}^q(K{+}1)]_j - [\mathbf{x}_{j}^q(K{+}1)]_j\big\|_2, \end{align}\tag{10}\] evaluated at all executed iterates. By the definition, we know that the consensus error \(\mathcal{J}=0\) if and only if all agents hold the same iterate.

The numerical results in Fig. 7 reveal three effects. First, the consensus error is topology-sensitive, and it increases as the diameter of the graph becomes large. Second, the regret is remarkably robust to the topology. Specifically, the per-round regret of the three topologies differs by less than \(1\%\) at every instance. This is mainly due to the fact that each agent’s executed reward is dominated by its own block, which it knows exactly, while the topology only delays its estimate of the others’ blocks. Third, the sampling-violation rate is driven by problem scale rather than topology. It rises with \(I\), consistent with the \((N-\kappa)\) dependence in Theorem 5, with only a mild secondary topology effect. The price of this robustness is that PB-SPR incurs a larger consensus error than the standard bandit method, consistent with the \(\mathcal{O}(N^2/K)\) consensus-error term in the analysis.

7 Conclusion↩︎

This paper studied the distributed submodular maximization problem in the online setting. An algorithmic framework was proposed which accommodates both full-information and bandit feedback models. Sublinear \((1-1/e)\)-regret was established in both settings, matching the state-of-the-art centralized rates. To address the sampling violation issue which is inherent to bandit feedback with continuous relaxation, we further developed the B-SPR scheme and proved that the probability of sampling violation vanishes asymptotically. Numerical results validated the effectiveness of our algorithms. Future work will be devoted to developing distributed online algorithms that ensure hard per-round feasibility, as demanded by safety-critical applications. It would be of interest to extend the present framework beyond the partition matroid to more general constraints.

Appendix↩︎

Appendix I: Proofs Pertaining to Algorithm 1↩︎

7.1 Proof of Lemma 1↩︎

By the initialization \(\mathbf{x}_i^q(1) = \mathbf{0}\) and \(\mathbf{v}_i^q(k) \in \mathcal{M}_i\), it is easy to see that \([\mathbf{x}_i^q(k)]_i \in \mathcal{M}_i\) for \(\forall i \in [I]\), and thus \(\bar{\mathbf{x}}^q(k) \in \mathcal{M}\) by the definition of \(\bar{\mathbf{x}}^q(k)\). In addition, due to the updating rule of \([\mathbf{x}_i^q(k)]_{i'}\) for \(\forall i' \neq i\) (see Line 7 in Algorithm 1), we can have that \(\mathbf{0} \preceq [\mathbf{x}_i^q(k)]_{i'} \preceq [\mathbf{x}_{i'}^q(k)]_{i'}\). As a result, \([\mathbf{x}_i^q(k)]_{i'} \in \mathcal{M}_{i'}\) holds for \(\forall i' \neq i\) and thus \(\mathbf{x}_i^q(k) \in \mathcal{M}\) for \(\forall i \in [I]\).

Notice that \(\mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k)]_i \le \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k-1)]_i + \kappa_i/K\). Hence, applying the inequality for consecutive \(d(\mathcal{G})\) steps yields, \[\begin{align} \label{ineq:proof-lemma-1-1} \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k)]_i \le \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k-d(\mathcal{G}))]_i + \kappa_id(\mathcal{G})/K. \end{align}\tag{11}\] Recall that \(d(\mathcal{G})\) denotes the diameter of the graph \(\mathcal{G}\), meaning that every agent \(i' \neq i\) can be reached from the agent \(i\) by at most \(d(\mathcal{G})\)-hop communications. Thus, it holds for \(\forall i' \neq i\) that \(\mathbf{1}_{N_i}^\top[\mathbf{x}_{i'}^q(k)]_{i} \ge \mathbf{1}_{N_i}^\top[\mathbf{x}_{i}^q(k -d(\mathcal{G}))]_{i}\). Combining this inequality together with 11 gives \[\begin{align} \label{ineq:proof-lemma-1-2} \mathbf{1}_{N_i}^\top[\mathbf{x}_{i'}^q(k)]_{i} \ge \mathbf{1}_{N_i}^\top[\mathbf{x}_{i}^q(k)]_{i} - \kappa_id(\mathcal{G})/K. \end{align}\tag{12}\] Therefore, it follows that \[\begin{align} \|\bar{\mathbf{x}}^q(k) - \mathbf{x}_i^q(k)\|\le\mathbf{1}_{N}^\top\big(\bar{\mathbf{x}}^q(k) - \mathbf{x}_i^q(k)\big) \le \kappa d(\mathcal{G})/K, \end{align}\] where the first inequality is due to the facts that \(\|\mathbf{x}\| \le \|\mathbf{x}\|_1\) and \([\mathbf{x}_i^q(k)]_{i'} \preceq [\mathbf{x}_{i'}^q(k)]_{i'}\) holds for \(\forall i' \neq i\), and the second one follows by summing 12 for \(\forall i \in [I]\) and \(\kappa = \sum_{i \in [I]} \kappa_i\). The proof of Lemma 1 is completed.

7.2 Proof of Theorem 1↩︎

To facilitate the subsequent proofs, let us first notice by the definitions in 5 and 6 that, the diameters of polytopes \(\mathcal{M}_i\) and \(\mathcal{M}\) have \(D_i = \max_{\mathbf{x}, \mathbf{y} \in \mathcal{M}_i} \|\mathbf{x} - \mathbf{y}\| =\sqrt{ \min\{2\kappa_i, N_i\}}\) and \(D = \max_{\mathbf{x}, \mathbf{y} \in \mathcal{M}} \|\mathbf{x} - \mathbf{y}\| = \sqrt{\sum_{i=1}^I \min\{2\kappa_i, N_i\}}\), respectively. In addition, recall that \(f^t(\cdot)\) is monotone and submodular with \(\max_{\mathcal{S} \in \mathcal{I}} f^t (\mathcal{S}) \le f^\text{max}\), it can be shown (see Lemma 3 in [35]) that its multi-linear extension \(F^t(\cdot)\) is \(L_1\)-Lipschtiz and \(L_2\)-smooth with \(L_1 = 2 \sqrt{N}f^\text{max}\) and \(L_2 = 4Nf^\text{max}\).

Let \(\mathcal{S}^\star \in \arg\max_{\mathcal{S} \in \mathcal{I}} \sum_{t=1}^T f^t(\mathcal{S})\) and \(\widetilde{\mathbf{x}}^\star \in \mathcal{M}\) be the continuous variable so that \(\sum_{t=1}^T F^t(\widetilde{\mathbf{x}}^\star)=\sum_{t=1}^T f^t(\mathcal{S}^\star)\). Likewise, let \(\mathbf{x}^\star \in \arg\max_{\mathbf{x} \in \mathcal{M}} \sum_{t=1}^T F^t(\mathbf{x})\), it is clear that \(\sum_{t=1}^T F^t({\mathbf{x}}^\star) \ge \sum_{t=1}^T F^t(\widetilde{\mathbf{x}}^\star)\). Considering that each discrete decision \(\mathcal{S}^t\) is obtained by lossless rounding on \(\bar{\mathbf{s}}^t= [\mathbf{s}_1(t)^\top,\cdots,\mathbf{s}_I(t)^\top]^\top\), i.e., \(\mathbb{E}[f^t(\mathcal{S}^t)] \ge F^t(\bar{\mathbf{s}}^t)\), it has \[\label{eq:regret-1-continous-regret} \begin{align} \mathcal{R}^c_T &:= (1-1/e)\cdot \sum_{t=1}^TF^t(\mathbf{x}^\star) - \sum_{t=1}^T F^t( \bar{\mathbf{s}}^t) \\ &\ge\mathbb{E}\Big[(1-1/e)\cdot \sum_{t=1}^Tf^t(\mathcal{S}^\star) - \sum_{t=1}^T f^t( \mathcal{S}^t)\Big]. \end{align}\tag{13}\] Therefore, to prove the regret bound in Theorem 1, it suffices to next show that \(\mathcal{R}_T^c\) is no larger than the same bound.

Recall the definition of \(\bar{\mathbf{x}}^q(k)\) in Lemma 1 and let \(\bar{\mathbf{v}}^q(k) := [\mathbf{v}_1^q(k)^\top,\cdots,\mathbf{v}_I^q(k)^\top]^\top \in \mathcal{M}\), it is straightforward to verify that \(\bar{\mathbf{x}}^q(k+1) = \bar{\mathbf{x}}^q(k) + \bar{\mathbf{v}}^q(k) /K, \forall k \in [K]\). Now, define a new vector \(\bar{\mathbf{d}}_i^q(k) \in \mathbb{R}^N\) for every \(i\in[I]\) which is generated by the following recursion with \(\bar{\mathbf{d}}_i^q(0) = \mathbf{0}\), \[\begin{align} \label{eq:d-bar} \bar{\mathbf{d}}_i^q(k) = (1-\rho_k)\bar{\mathbf{d}}_i^q(k-1) + \rho_k \nabla F^{t_i^{q,k}}\big(\bar{\mathbf{x}}^q(k)\big). \end{align}\tag{14}\] Furthermore, let \(\widetilde{\mathbf{d}}^q(k) := 1/I\cdot\sum_{i=1}^I\bar{\mathbf{d}}_i^q(k)\). Then, by the facts that \(\{t_i^{q,1}, t_i^{q,2}, \cdots, t_i^{q,K}\}\) is a uniformly random permutation of \(\{1,2,\cdots, K\}\) and is independent for \(\forall i\in[I]\), we can have \[\begin{align} \label{eq:independent-gradient} \mathbb{E}\Big[\widetilde{\mathbf{d}}^q(k) - \bar{\mathbf{d}}_i^q(k) \Big] = 0. \end{align}\tag{15}\] Next, by the same steps in the proof of Lemma 4 in [18], we can obtain the following result.

Now, with the aid of the above Lemma 5, we can show an intermediate result for the upper bound of \(\mathbb{E}[\mathcal{R}_T^c]\).

Subsequently, we turn to bound the two key terms in ?? , i.e., the stochastic gradient error \(\Delta_i^1(k)\) and the consensus error \(\Delta_i^2(k)\). First, by the same steps in the proof of Lemma 6 in [18], we can have the following result.

In addition, using the result in Lemma 1, we can also bound the consensus error \(\Delta_i^2(k)\) as the following Lemma 8.

With the help of Lemmas 7 and 8, we are now able to prove the statement in Theorem 1. Let \(\{\beta(k)\}_{k\in [K]}\) in Lemma 5 be \[\begin{align} \label{eq:beta} \beta(k) = \begin{cases} (k+4)^{-1/3},\; &\text{when}\;\; 1\le k\le K/2;\\ (K-k+1)^{-1/3},\; &\text{when}\;\;K/2+1\le k\le K, \end{cases} \end{align}\tag{19}\] it holds that \(\sum_{k=1}^{K/2} \beta(k) \le K^{2/3}\) and \(\sum_{k=K/2+1}^{K} \beta(k) \le K^{2/3}\). Further, by Lemma 7, we have \[\begin{align} \sum_{k=1}^{K} \frac{\mathbb{E}\big[\Delta_i^1(k)\big]}{\beta(k)} &= \sum_{k=1}^{K/2} \frac{C_1}{(k+4)^{1/3}} + \sum_{k=K/2+1}^{K} \frac{C_1}{(K-k+1)^{1/3}} \le 2C_1 K^{2/3}. \end{align}\] Therefore, it follows from Lemmas 6 and 8 that \[\begin{align} \mathbb{E}[\mathcal{R}^c_T] &\le Q C_1 K^{2/3} + Q L_2\kappa d(\mathcal{G})\sum_{i=1}^I D_i + K\sum_{i=1}^I\mathcal{R}_Q^{\mathcal{E}_i} + QD^2K^{2/3} + L_2QD^2/2\\ &\le \big(C_1 + C_0I+ D^2\big) \cdot T^{4/5} + \big(L_2D^2/2 + L_2\kappa d(\mathcal{G})\sum_{i=1}^I D_i\big)\cdot T^{2/5}, \end{align}\] where the last inequality is due to \(Q = T^{2/5}\), \(K = T^{3/5}\), and also the regret bound of experts, i.e., \(\mathcal{R}_Q^{\mathcal{E}_i} \le C_0 \sqrt{Q}\) (see 9 in Sec. 2.3). Finally, combining the fact that \(\mathbb{E} [\mathcal{R}_T] \le \mathbb{E} [\mathcal{R}^c_T]\) in 13 , Theorem 1 has been proved.

Appendix II: Proofs Pertaining to Algorithm 2↩︎

7.3 Proof of Lemma 2↩︎

Due to the initialization of \(\mathbf{x}_i^q(1)\) and the update of \([\mathbf{x}_i^q(k)]_i\) (see Lines 3 and 6 in Algorithm 2), it is straightforward to have that \([\mathbf{x}_i^q(k+1)]_i = \sum_{l=1}^k \mathbf{v}_i^q(l)/K + (1-k/K) [\mathbf{x}_i^q(1)]_i\), which is convex combination of \([\mathbf{x}_i(1)]_i, \mathbf{v}_i^q(1), \cdots, \mathbf{v}_i^q(k)\). Provided that \([\mathbf{x}_i(1)]_i \in \widetilde{\mathcal{M}}_i\) and \(\mathbf{v}_i^q(k) \in \widetilde{\mathcal{M}}_i ,\forall k\in[K]\), it follows by the convexity of set \(\widetilde{\mathcal{M}}_i\) that \([\mathbf{x}_i^q(k+1)]_i \in \widetilde{\mathcal{M}}_i ,\forall k\in[K]\) and \(i \in [I]\). The rest of this proof can be completed by following the same steps as the proof of Lemma 1 in Appendix I-A.

7.4 Proof of Theorem 2↩︎

Similar to the previous proof, we first note that the diameters of the polytopes \(\widetilde{\mathcal{M}}_i\) and \(\widetilde{\mathcal{M}}\) are \(\alpha D_i\) and \(\alpha D\), respectively. Given that \(\alpha < 1\), \(D_i\) and \(D\) are always valid upper bounds of the diameters, and thus we directly use \(D_i\) and \(D\) in the following proofs for simplicity. Furthermore, let us recall that \(\gamma = \min_{i \in [I]}\big\{\min\{1, \kappa_i / \sqrt{N_i}\}\big\}\) and the definition of \(\mathcal{M}\), it can be verified that \(\gamma \mathbb{B}^N_{\ge 0} \subseteq \mathcal{M}\). Therefore, according to Lemma 1 in [18], with the parameters \(\alpha\) and \(\delta\) specified as in Theorem 2, the distance between the two sets \(\mathcal{M}\) and \(\widetilde{\mathcal{M}}\) has \[\begin{align} \label{ineq:distance-between-two-sets} \text{dist}(\mathcal{M}, \widetilde{\mathcal{M}}) := \max_{\mathbf{x} \in \mathcal{M}, \mathbf{y} \in \widetilde{\mathcal{M}}} \;\|\mathbf{x} - \mathbf{y}\| \le C_\mathcal{M} \delta, \end{align}\tag{20}\] where \(C_\mathcal{M} = (\sqrt{\kappa}/\gamma + 1)\sqrt{N} + \sqrt{\kappa}/\gamma\).

Next, we define a \(\delta\)-smoothed version of the function \(F^t(\cdot)\), i.e., \(\widehat{F}^t(\mathbf{x}):=\mathbb{E}_{\mathbf{v} \sim \text{Uni}(\mathbb{B}^N)} [F^t(\mathbf{x} + \delta \mathbf{v})]\), and based on Lemma 1 in [35], we have the following general result regarding \(\widehat{F}^t(\cdot)\).

With the help of the above Lemma 9, we are now ready to analyze the regret in Theorem 2. Let \(\mathcal{S}^\star\) and \(\mathbf{x}^\star\) be defined as same as before and \(\mathbf{x}_\delta^\star \in \arg\max_{\mathbf{x} \in \widetilde{\mathcal{M}}} \sum_{t=1}^T F^t(\mathbf{x})\), then by the same reasons behind the inequality 13 , we have \[\label{ineq:eq:regret-2-continuous-regret-decomp} \begin{align} \mathbb{E}[\mathcal{R}_T] &\le \mathbb{E}\Big[(1-1/e) \sum_{t=1}^T F^t (\mathbf{x}^\star) - \sum_{t=1}^T F^t\big(\bar{\mathbf{s}}^t\big)\Big] \\ & =\mathbb{E}\Big[(1-1/e) \sum_{t=1}^T \big(F^t(\mathbf{x}^\star) \pm F^t(\mathbf{x}_\delta^\star) \pm \widehat{F}^t(\mathbf{x}_\delta^\star)\big) - \sum_{t=1}^T \big(F^t(\bar{\mathbf{s}}^t) \pm \widehat{F}^t(\bar{\mathbf{s}}^t)\big) \Big]\\ &\le \mathbb{E}\Big[(1-1/e) \sum_{t=1}^T \big(F^t(\mathbf{x}^\star) - F^t(\mathbf{x}_\delta^\star)\big) + \sum_{t=1}^T\big((1-1/e) \widehat{F}^t(\mathbf{x}_\delta^\star) - \widehat{F}^t(\bar{\mathbf{s}}^t)\big) \Big] + (2-1/e)TL_1\delta\\ & \le \mathbb{E}\Big[\sum_{t=1}^T\big((1-1/e) \widehat{F}^t(\mathbf{x}_\delta^\star) - \widehat{F}^t(\bar{\mathbf{s}}^t)\big) \Big] + (1-1/e)TL_1 C_\mathcal{M} \delta + (2-1/e)TL_1\delta, \end{align}\tag{21}\] where the second inequality follows from Lemma 9 and the last one follows from the facts that each \(F^t(\cdot)\) is \(L_1\)-Lipschitz and \(\|\mathbf{x}^\star - \mathbf{x}_\delta^\star\| \le \text{dist}(\mathcal{M}, \widetilde{\mathcal{M}}) \le C_\mathcal{M}\delta\).

Subsequently, let \(\widehat{\mathcal{R}}^c_T: = \sum_{t=1}^T \big((1-1/e)\widehat{F}^{t}(\mathbf{x}_\delta^\star) - \widehat{F}^{t}(\bar{\mathbf{s}}^t)\big)\) and following the same analysis in the proof of Theorem 1 in Appendix I-B, we provide the result analogous to Lemma 6. To proceed, we first define \(\bar{F}_i^{q,k}(\mathbf{x}): = \sum_{l=k+1}^L \widehat{F}^{t_i^{q,l}}(\mathbf{x})/(L-k)\) for \(\forall k = 0,1,\cdots K-1\). In addition, we overload the vector \(\bar{\mathbf{d}}_i^q(k) \in \mathbb{R}^N\) which is given by the following recursion with initialization \(\bar{\mathbf{d}}_i^q(0) = \mathbf{0}\), \[\label{eq:d-bar-2} \begin{align} \bar{\mathbf{d}}_i^q(k) &= (1-\rho_k)\bar{\mathbf{d}}_i^q(k-1) + \rho_k \cdot N/\delta \cdot F^{t^i_{q,k}}\big(\bar{\mathbf{x}}^q(k) + \delta\mathbf{u}_i^q(k)\big) \cdot\mathbf{u}_i^q(k). \end{align}\tag{22}\] Note that the randomness of \(\bar{\mathbf{d}}_i^q(k)\) defined in 22 comes from the random permutation \(\{t_{q,1}^i, t_{q,2}^i, \cdots, t_{q,L}^i\}\) and the uniform sample \(\mathbf{u}_i^q(k)\) from the sphere \(\mathbb{S}^{N-1}\). However, both samples are independent across all agents and iterations, and therefore, the equality 15 still holds in this case. Now, we are ready to show the intermediate result for the upper bound of \(\mathbb{E}[\widehat{\mathcal{R}}_T^c]\), whose proof can be completed by the same steps as the one for Lemma 6 and thus is omitted for simplicity.

Similarly, we now turn to bound the two terms in ?? , i.e., the stochastic gradient error \(\Delta_i^1(k)\) and consensus error \(\Delta_i^2(k)\).

At last, we prove the statement in Theorem 2. Here, we let \(\beta(k) = (k+3)^{-1/3}/\delta\), then it has \(\sum_{k=1}^K \beta(k) \le 1.5 K^{2/3} /\delta\). In addition, by Lemma 11, it holds that \[\begin{align} \sum_{k=1}^K \frac{\mathbb{E}[\Delta_i^1(k)]}{\beta(k)} &\le (C_2\delta^{-2} + C_3)\delta \cdot \sum_{k=1}^K \frac{1}{(k+3)^{1/3}} \le \frac{3(C_2\delta^{-1} + C_3\delta) K^{2/3}}{2}. \end{align}\] Therefore, by 21 and Lemmas 10–12, we can have that \[\begin{align} \mathbb{E}[\mathcal{R}_T] &\le \mathbb{E}[\widehat{\mathcal{R}}^c_T]+ (1-1/e)TL_1 C_\mathcal{M} \delta + (2-1/e)TL_1\delta\\ &\le (1-1/e)TL_1 C_\mathcal{M} \delta + (2-1/e)TL_1\delta + {3}/{4}\cdot C_2\delta^{-1}L Q K^{-1/3} + {3}/{4}\cdot C_3\delta L Q K^{-1/3} \\ &+ \frac{LQ L_1 \kappa d(\mathcal{G}) N \sum_{i=1}^I D_i}{\delta K}+L\sum_{i=1}^I\mathcal{R}_Q^{\mathcal{E}_i}+ \frac{3}{4\delta}\cdot{LQD^2}K^{-1/3}+ \frac{LQD^2L_2}{2K}\\ & \le \Big((1-1/e)L_1C_\mathcal{M}C_\delta + (2-1/e)L_1 C_\delta + 3/4\cdot C_2/C_\delta + C_0 I + 3/4\cdot D^2/C_\delta\Big)\cdot T^{8/9}\\ & +3/4\cdot C_3C_\delta\cdot T^{2/3} + L_1 \kappa d(\mathcal{G})N \sum_{i=1}^I D_i/C_\delta \cdot T^{4/9}+L_2D^2 /2 \cdot T^{1/3}, \end{align}\] where the last inequality follows from \(L = T^{7/9}\), \(K = T^{2/3}\), \(\delta = C_\delta T^{-1/9}\) and \(\mathcal{R}_Q^{\mathcal{E}_i} \le C_0 \sqrt{Q}\). The proof of Theorem 2 is completed.

Appendix III: Proofs Pertaining to Algorithm 4↩︎

7.5 Proof of Theorem 3↩︎

According to Algorithm 3, the B-SPR procedure can be represented by \(\mathbf{y}^0 = \mathbf{x} \to \mathbf{y}^1 \to \cdots \to \mathbf{y}^\mathcal{T} = \mathbf{z}\). Then, by the randomized swapping operation in Algorithm 3, it holds that \(\mathbf{1}_M^\top\mathbf{y}^{\tau -1} = \mathbf{1}_M^\top\mathbf{y}^\tau\), \(\tau \in [\mathcal{T}]\), which proves the statement i) in Theorem 3. Also, it is clear that, for each \(\mathbf{y}^{\tau -1} \to \mathbf{y}^\tau, \tau \in [\mathcal{T}]\), there is at least one more element becoming either \(b_l\) or \(b_u\). Since there are totally \(M\) elements in the vector, the procedure must terminate in finite time \(\mathcal{T} \le M-1\), and there is at most one element in the output vector \(\mathbf{z} = \mathbf{y}^\mathcal{T}\) that is neither \(b_l\) nor \(b_u\). Thus, the statement ii) in Theorem 3 is proved.

Subsequently, to prove the statement iii), let us first notice the following directional convexity property of the multi-linear extension \(F(\cdot)\) of any monotone submodular function [13]: let \(\mathbf{e}_n, \mathbf{e}_m \in \mathbb{R}^M\) be two basis vectors, then \(F\big(\mathbf{x} + t(\mathbf{e}_n - \mathbf{e}_m)\big)\) is convex with respect to the variable \(t\). As a result of the above convexity property and the randomized swapping, we can have \[\begin{align} &\mathbb{E}\big[F(\mathbf{y}^{\tau+1}) | \mathbf{y}^\tau\big] \\ &= \frac{\Delta^\tau(n)}{\Delta^\tau(m)+\Delta^\tau(n)} F\Big(\mathbf{y}^\tau + \Delta^\tau(m)(\mathbf{e}_n - \mathbf{e}_m)\Big) + \frac{\Delta^\tau(m)}{\Delta^\tau(m)+\Delta^\tau(n)} F\Big(\mathbf{y}^\tau - \Delta^\tau(n)(\mathbf{e}_n - \mathbf{e}_m)\Big) \\ & \ge F(\mathbf{y}^\tau). \end{align}\] It follows by the law of iterated expectations that \(\mathbb{E}\big[F(\mathbf{y}^{\tau})] \ge \mathbb{E}\big[F(\mathbf{y}^{\tau-1})], \forall \tau \in [\mathcal{T}]\), which proves the statement iii).

7.6 Proof of Lemma 3↩︎

We begin the proof by introducing more notations. Denote \(b_l = \delta\) and \(b_u(k) =\delta + \alpha (k-1)/K\), \(\forall 1\le k\le K\). Similar to the previous proof of Theorem 3, we let the B-SPR procedure executed by \(\mathcal{R}_{\delta}^{\delta+\alpha k/K }(\cdot)\) be represented by \(\mathbf{y}^0 = \widetilde{\mathbf{z}}(k+1) \to \mathbf{y}^1 \to \cdots \to \mathbf{y}^\mathcal{T} = \mathbf{z}(k+1)\) with \(\mathcal{T} \le M-1\) (by Theorem 3). Since \(\mathbf{z}(k)\) is the output of \(\mathcal{R}_{b_l}^{b_u(k)}(\cdot)\), it is clear that \(b_l \mathbf{1}_M\preceq \mathbf{z}(k) \preceq b_u(k) \mathbf{1}_M\) and by Theorem 3 statement ii), there is at most one element in \(\mathbf{z}(k)\) that is neither \(b_l\) nor \(b_u(k)\). Let us denote the index of such an element in \(\mathbf{z}(k)\) as \(c \in [M]\), i.e., \(z_c(k) \in \big(b_l ,b_u(k)\big)\) (if not exist, take arbitrary \(c \in [M]\)). Recall that \(\widetilde{\mathbf{z}}(k+1) = \mathbf{z}(k) + \mathbf{v}(k)/K\), and during the B-SPR procedure, let \(c_\tau\) track the position of such an element in \(\mathbf{y}^\tau\) (this will be clearer in the sequel).

To prove the statement in Lemma 3, let us first consider the case when \(k \le M\). By the fact that \(b_l \mathbf{1}_M\le \mathbf{z}(k) \le b_u(k) \mathbf{1}_M\) holds for \(\forall k \in [K+1]\), it follows that \[\begin{align} \label{eq:proof-diff-bound-1} \|\mathbf{z}(k+1) - \mathbf{z}(k)\|_1 \le M \big(b_u(k+1) - b_l\big) \le \alpha M^2 /K. \end{align}\tag{24}\]

Subsequently, we turn to the case when \(k > M\). To facilitate the proof, we define the following three intervals, i.e., \(\mathcal{A}^\tau: = \big[ \delta + \alpha (k-1-\tau) /K, \delta + \alpha k/K\big]\), \(\mathcal{B}^\tau:= \big[\delta, \delta + \alpha(\tau+1) /K\big]\), and \(\mathcal{C}^\tau:=\big(\delta + \alpha(\tau+1) /K, \delta + \alpha (k-1-\tau) /K\big).\) Note that \(\mathcal{A}^\tau\cup \mathcal{B}^\tau \cup \mathcal{C}^\tau =\big[b_l , b_u(k+1)\big]\) holds for \(\forall 0 \le \tau \le \mathcal{T}\), and since \(k > M \ge \tau +1\), all the three intervals are well-defined. Associated with the intervals, we define three additional sets: \[\begin{align} \mathcal{Y}_\mathcal{A}^\tau: &= \Big\{y^\tau(m) \vert y^\tau(m) \in \mathcal{A}^\tau, m \in [M]\Big\} \setminus \big\{y^\tau (c_\tau)\big\};\\ \mathcal{Y}_\mathcal{B}^\tau: &= \Big\{y^\tau(m) \vert y^\tau(m) \in \mathcal{B}^\tau, m \in [M]\Big\} \setminus \big\{y^\tau (c_\tau)\big\};\\ \mathcal{Y}_\mathcal{C}^\tau: &= \Big\{y^\tau(m) \vert y^\tau(m) \in \mathcal{C}^\tau, m \in [M]\Big\} \cup \big\{y^\tau (c_\tau)\big\}. \end{align}\] Then, we show the following intermediate result.

With the aid of Lemma 13, we are now ready to prove the result in Lemma 3. To proceed, let us first show that, according to the randomized swapping operation, the distance between \(\mathbf{y}^{\tau+1}\) and \(\mathbf{y}^{\tau}\) at each step \(0\le \tau \le \mathcal{T}-1\) has \[\begin{align} \mathbb{E}\Big[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau}\|_1\Big] = \frac{4}{ 1/{\Delta}^\tau(m) + 1/\Delta^\tau(n) }. \end{align}\] Therefore, one can conclude that \(\mathbb{E}\big[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau}\|_1\big]\) achieves its upper bound when \(\Delta^\tau(m)\) and \(\Delta^\tau(n)\) take their maximum values. Note that Lemma 13 confirms that the random selection of \(y^\tau(m)\) and \(y^\tau(n)\) at each step \(\tau\) occurs in one of the five cases above. Subsequently, we upper bound \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1]\) by analyzing \(\Delta^\tau(m)\) and \(\Delta^\tau(n)\) in each of the five cases.

Case i): Considering \(y^\tau(m) \in \mathcal{A}^\tau\) and \(y^\tau(n) \in \mathcal{A}^\tau\), one can confirm that \({\Delta^\tau(m)} \le b_u(k+1) - y^{\tau}(n)\le \alpha(\tau+1) /K\) and \({\Delta^\tau(n)} \le b_u(k+1) - y^{\tau}(m)\le \alpha(\tau+1) /K\). As a consequence, it holds that \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1] \le 2\alpha(\tau+1)/K\).

Case ii): Similarly, one can confirm that \({\Delta^\tau(m)} \le y^{\tau}(m) - b_l \le\alpha(\tau+1) /K\) and \({\Delta^\tau(n)} \le y^{\tau}(n) - b_l\le \alpha(\tau+1) /K\). Therefore, \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1] \le2\alpha(\tau+1)/K\).

Case iii): Since \(y^\tau(m) \in \mathcal{A}^\tau\) and \(y^\tau(n) \in \mathcal{B}^\tau\), we can have that \(\Delta^\tau(m) \le y^\tau(m)-b_l \le \alpha k/K\) and \(\Delta^\tau(n) \le y^\tau(n)-b_l \le \alpha(\tau+1)/K\). Therefore, \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1] \le 4\alpha(\tau+1)/K\).

Case iv): Since \(y^\tau(m) \in \mathcal{A}^\tau\), \(y^\tau(n) \in \mathcal{C}^\tau\), we can have that \({\Delta^\tau(m)} \le y^{\tau}(m) - b_l \le\alpha k/K\) and \({\Delta^\tau(n)} \le b_u(k+1) - y^{\tau}(m)\le \alpha(\tau+1) /K\). Thus, it holds that \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1] \le 4\alpha(\tau+1)/K\).

Case v): Similarly, one can confirm that \({\Delta^\tau(m)} \le y^{\tau}(m) -b_l\le \alpha(\tau+1)/K\) and \({\Delta^\tau(n)} \le b_u(k+1) - y^{\tau}(m)\le \alpha k/K\). Therefore, it holds that \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1] \le 4\alpha(\tau+1)/K\).

Now, combining the above cases i) – v), we can obtain that \(\mathbb{E}[\|\mathbf{y}^{\tau+1} -\mathbf{y}^{\tau} \|_1] \le 4\alpha(\tau+1)/K\), which further implies that \[\begin{align} &\mathbb{E}\Big[\|\mathbf{z}(k+1) - \widetilde{\mathbf{z}}(k+1)\|_1\Big] = \mathbb{E}\Big[\|\mathbf{y}^\mathcal{T} - \mathbf{y}^0\|_1\Big] \le \mathbb{E}\Big[\sum_{\tau = 0}^{\mathcal{T}-1}\|\mathbf{y}^{\tau+1}- \mathbf{y}^\tau\|_1\Big] \le 2M(M-1)\alpha/ K, \end{align}\] where last inequality is due to the fact that \(\mathcal{T} \le M-1\). Further, by triangle inequality, it holds that \[\begin{align} \mathbb{E}\Big[\|\mathbf{z}(k+1) - {\mathbf{z}}(k)\|_1\Big] &\le \mathbb{E}\Big[\|\mathbf{z}(k+1) - \widetilde{\mathbf{z}}(k+1)\|_1\Big] + \| \mathbf{v}(k)\|_1/K\\ &\le 2M(M-1)\alpha/ K + \alpha M /K\le 2\alpha M^2 /K, \end{align}\] which, together with the result in 24 , completes the proof of Lemma 3.

7.7 Proof of Lemma 4↩︎

Similar to the proofs of Lemmas 1 and 2, we first show that \([\mathbf{x}_i^q(k+1)]_i \in \widetilde{\mathcal{M}}_i ,\forall k\in[K]\) and \(i \in [I]\). Recall the definition of \(\widetilde{\mathcal{M}}_i = \alpha \widetilde{\mathcal{M}}_i + \delta\cdot \mathbf{1}_{N_i}\), to prove \([\mathbf{x}_i^q(k+1)]_i \in \widetilde{\mathcal{M}}_i\), it is equivalent to show \(\big([\mathbf{x}_i^q(k+1)]_i - \delta \cdot\mathbf{1}_{N_i}\big)/\alpha \in \mathcal{M}_i\), i.e., to prove the following: i) \(\delta \cdot \mathbf{1}_{N_i} \preceq [\mathbf{x}_i^q(k+1)]_i \preceq (\alpha + \delta)\cdot \mathbf{1}_{N_i}\); and ii) \(0 \le \big(\mathbf{1}_{N_i}^\top [\mathbf{x}_i^q(k+1)]_i - \delta N_i\big)/\alpha \le \kappa_i\). The inequalities in i) are easily verified by the reason that \([\mathbf{x}_i^q(k+1)]_i\) is the output of \(\mathcal{R}_{\delta}^{\delta + \alpha k/K}(\cdot)\). In addition, by the statement i) in Theorem 3, it holds that \[\label{eq:summation-recursion} \begin{align} \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k+1)]_i &= \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k )]_i + (\mathbf{1}_{N_i}^\top \mathbf{v}_i^q(k) - \delta N_i)/K= \sum_{l=1}^k \mathbf{1}_{N_i}^\top \mathbf{v}_i^q(l)/K + \delta N_i (1-k/K). \end{align}\tag{26}\] Since \(\mathbf{v}_i^q(l) \in \widetilde{\mathcal{M}}_i\), we have that \(\delta N_i \le \mathbf{1}_{N_i}^\top \mathbf{v}_i^q(l) \le \alpha \kappa_i + \delta N_i\) and thus the inequalities in ii) are proved.

Next, due to the updating rule of \([\mathbf{x}_i^q(k)]_{i'}\) for \(\forall i' \neq i\) (see Line 7 in Algorithm 3), it holds that \([\mathbf{x}_i^q(k)]_{i'} = [\mathbf{x}_{i'}^q(k- t)]_{i'}\) for some \(1 \le t \le d(\mathcal{G})\). As a consequence, one can also have that \([\mathbf{x}_i^q(k)]_{i'} \in \mathcal{M}_{i'}\) for \(\forall i' \neq i\). The proof of statement i) in Lemma 4 is completed.

By Lemma 3, it has been shown that for \(\forall i\in [I],k \in [K]\), \[\begin{align} \mathbb{E}\big[\big\| [{\mathbf{x}}_i^q(k+1)]_i - [{\mathbf{x}}_i^q(k)]_i\big \|_1 \big] \le 2\alpha N_i^2/K. \end{align}\] Recall that \(d(\mathcal{G})\) represents the diameter of the graph, meaning that every agent \(j \neq i\) can be reached from the agent \(i\) at most in \(d(\mathcal{G})\)-hop communications, thus it follows from the triangle inequality that for \(\forall j \neq i, k\in[K]\) \[\begin{align} \mathbb{E}\Big[\big\| [{\mathbf{x}}_j^q(k)]_i - [{\mathbf{x}}_i^q(k)]_i\big \|_1 \Big] \le 2\alpha N_i^2d(\mathcal{G})/K. \end{align}\] As a result, it holds for \(\forall i\in [n]\) that \[\begin{align} &\mathbb{E}\Big[\big\| \bar{\mathbf{x}}^q(k) - {\mathbf{x}}_i^q(k)\big \| \Big] \le \mathbb{E}\Big[\big\| \bar{\mathbf{x}}^q(k) - {\mathbf{x}}_i^q(k)\big \|_1 \Big] = \sum_{j\neq i} \mathbb{E}\Big[\big\| [{\mathbf{x}}_j^q(k)]_j - [{\mathbf{x}}_i^q(k)]_j\big \|_1 \Big] \le 2\alpha N^2d(\mathcal{G})/K. \end{align}\] Therefore, the proof of Lemma 4 is completed.

7.8 Proof of Theorem 4↩︎

This proof can be completed by repeating the proof in Appendix II-B. The only two differences are noted as follows.

First, due to the incorporation of the PB-SPR procedure (see Line 6 in Algorithm 4), the update of \([{\mathbf{x}}_i^q(k)]_i\) is different from the one in Algorithm 2. Specifically, we let \(\widetilde{\mathbf{x}}_i^q(k+1) := [\mathbf{x}_i^q (k)]_i + (\mathbf{v}_i^q(k) - \delta\cdot\mathbf{1}_{N_i})/K\), which is corresponding to the updating step in Algorithm 2, while Algorithm 4 imposes an additional operation by \([{\mathbf{x}}_i^q(k+1)]_i = \mathcal{R}_\delta^{\delta+\alpha k/K} (\widetilde{\mathbf{x}}_i^q(k+1))\). However, according to statement iii) in Theorem 3, it has \[\begin{align} \mathbb{E}\Big[F\big(\bar{\mathbf{x}}^q(k+1)\big)\Big] \ge F\big(\widetilde{\mathbf{x}}^q(k+1)\big),\; \forall k \in[K], \end{align}\] where \(\widetilde{\mathbf{x}}^q(k+1) := [\widetilde{\mathbf{x}}_1^q(k+1)^\top,\cdots,\widetilde{\mathbf{x}}_I^q(k+1)^\top]^\top\). Therefore, all arguments in the proof of Theorem 2 naturally follows by taking additional expectation with respect to the randomness in the PB-SPR procedure.

Second, in the previous proof, when bounding the consensus error term \(\Delta_i^2(k)\) (see Lemma 12), the \(L_1\)-Lipschitz continuity of \(F^t(\cdot)\) and the fact \(\|\bar{\mathbf{x}}^q(k) - \mathbf{x}_i^q(k)\| \le \kappa d(\mathcal{G})/K\) are used. However, since the PB-SPR procedure is now involved, the bound of difference between \(\bar{\mathbf{x}}^q(k)\) and \(\mathbf{x}_i^q(k)\) becomes that \(\mathbb{E}\big[\|\bar{\mathbf{x}}^q(k) - \mathbf{x}_i^q(k)\|\big] \le 2\alpha N^2 d(\mathcal{G})/K\) (see the statement ii) in Lemma 4). As a consequence, the constant \(N^2 d(\mathcal{G})\) appears in the second last term of the regret bound in Theorem 4.

7.9 Proof of Theorem 5↩︎

By the equality 26 and the fact that \(\mathbf{1}_{N_i}^\top \mathbf{v}_i^q(l) \le \alpha \kappa_i + \delta N_i\), \(\forall l\in[K]\), it follows that \[\begin{align} \mathbf{1}_{N_i}^\top[\mathbf{x}_i^q(k)]_i \le \delta N_i + \alpha\kappa_i (k-1) /K. \end{align}\] Moreover, given that \([\mathbf{x}_i^q(k)]_i\) is the output of \(\mathcal{R}_\delta^{\delta+\alpha (k-1)/K}(\cdot)\), there are at least \(N_i - \kappa_i\) components of the vector \([\mathbf{x}_i^q(k)]_i\) equal to \(\delta\). In addition, since it has been shown in Lemma 4 that \([\mathbf{x}_i^q(k)]_{i'} = [\mathbf{x}_{i'}^q(k- t)]_{i'}\) holds for some \(1 \le t \le d(\mathcal{G})\), the above statement is also true for \([\mathbf{x}_i^q(k)]_{i'},\forall i' \neq i\).

Let \(\mathbf{p}_i^q(k) = \mathbf{x}_{i}^q(k) + \delta\mathbf{u}_{i}^q(k)\), based upon which the discrete decision \(\mathcal{X}^q_i(k)\) is randomly generated. Then, it holds that \[\label{ineq:prob-bound} \begin{align} \mathbb{P} \big(\mathcal{X}_i^q(k) \notin \mathcal{I}\big) &= \mathbb{P} \Big(\bigcup_{i'=1}^I \big|[\mathcal{X}_i^q(k)]_{i'} \big| > \kappa_{i'} \Big)\\ & \le \sum_{i'=1}^I\mathbb{P} \Big( \big|[\mathcal{X}_i^q(k)]_{i'} \big| > \kappa_{i'} \Big ) \le \sum_{i'=1}^I 1- (1-2\delta)^{N_{i'} - \kappa_{i'}} \\ & \le 2 \delta(N - \kappa). \end{align}\tag{27}\] Note that in 27 , we use \([\mathcal{X}_i^q(k)]_{i'}\) to denote the discrete decision generated by \([\mathbf{p}_i^q(k)]_{i'}\), the first inequality is due to the union bound, the second inequality follows from the fact that there are at least \(N_{i'} - \kappa_{i'}\) components of each block \([\mathbf{p}_i^q(k)]_{i'}\) less than or equal to \(2\delta\), and the last one is by the Bernoulli inequality. Hence, the inequality ?? in Theorem 5 is proved by \(\delta=C_\delta T^{-1/9}\) and ?? simply follows from the facts that \(\mathbb{E}\big[\mathbb{1}\{\mathcal{X}^q_i(k) \notin \mathcal{I}\}\big] = \mathbb{P}\big(\mathcal{X}^q_i(k) \notin \mathcal{I}\big)\), \(Q = T^{2/9}\), \(K = T^{2/3}\).

7.10 Proof of Proposition 1↩︎

Using the same notations as in Appendix III-E, we can have \[\begin{align} \mathbb{P} \big(\mathcal{X}_i^q(k) \notin \mathcal{I}\big) &= \mathbb{P} \Big(\bigcup_{i'=1}^I \big|[\mathcal{X}_i^q(k)]_{i'} \big| > \kappa_{i'} \Big) \ge \mathbb{P} \big( \big|[\mathcal{X}_i^q(k)]_{i} \big| > \kappa_{i} \big). \end{align}\] Therefore, to prove the statement in Proposition 1, it suffices to show that \[\begin{align} \sum_{q=1}^Q \sum_{k=1}^K \mathbb{P} \big( \big|[\mathcal{X}_i^q(k)]_{i} \big| > \kappa_{i} \big) \ge \Omega(T^{7/9}). \end{align}\]

By the sum-preserving property of \(\mathcal{P}(\cdot)\) and the condition that \(\mathbf{1}_{N_i}^\top \mathbf{v}_i^q(k) = \delta N_i + \alpha\kappa_i\), it is straightforward to have that \(\mathbf{1}_{N_i}^\top [\mathbf{x}_i^q(k)]_i = \delta N_i + \alpha \kappa_i k/K\). Note that the discrete decision \([\mathcal{X}_i^q(k)]_{i}\) is generated by applying the random rounding on the variable \(\mathbf{g}_i^q(k): = [\mathbf{x}_i^q(k)]_i + \delta [\mathbf{u}_i]_i\), then one can have that \(\mathbf{1}_{N_i}^\top \mathbf{g}_i^q(k) \le \delta N_i + \delta \sqrt{N_i} + \alpha \kappa_i k/K\). Next, we show an intermediate result in the following lemma, which verifies that the probability \(\mathbb{P} ( |[\mathcal{X}_i^q(k)]_{i} | > \kappa_{i} )\) is minimized when the vector \(\mathbf{g}_i^q(k)\) is most majorized.

Due to the definitions of \(\alpha\) and \(\delta\) (see conditions in Theorem 2), one can have that \(\delta N_i + \delta \sqrt{N_i} + \alpha \kappa_i k/K < \kappa_i\) \(,\forall k \in [K]\). Moreover, let us denote \(s_k = (\delta \sqrt{N_i} + \alpha \kappa_i k/K)/(1-\delta)\) and \(\sigma_k = \lfloor s_k \rfloor\), i.e., one can assign at most \(\sigma_k\) one’s in the vector \(\mathbf{g}_i^q(k)\) to minimize the probability \(\mathbb{P} ( |[\mathcal{X}_i^q(k)]_{i} | > \kappa_{i} )\). Now, let \(K_s= \min_{k \in [K]} \{k \,\vert\, \sigma_k = \kappa_i -1\}\), and as a result of Lemma 14, we can have that \[\begin{align} &\sum_{k=1}^K \mathbb{P} \big( \big|[\mathcal{X}_i^q(k)]_{i} \big| > \kappa_{i} \big) \ge \sum_{k=K_s}^K \Big((1-\delta)(s_k -\sigma_k) + \delta \Big)\Big(1-(1-\delta)^{N_i -\kappa_i}\Big). \end{align}\] Notice that \[\begin{align} &\sum_{k=K_s}^K \Big((1-\delta)(s_k -\sigma_k) + \delta \Big) \ge \sum_{k=K_s}^K \Big(s_k -\sigma_k \Big) \ge \frac{\alpha\kappa_i /K}{1-\delta} \frac{(K- K_s +1)(K- K_s)}{2} \ge \Omega(K), \end{align}\] where the first inequality follows from \(s_k - \sigma_k < 1\), the second inequality is due to \(s_{k+1} - s_k = {\alpha\kappa_i}/(K(1-\delta))\), and the last inequality is due to the definition of \(K_s\). In addition, provided that \(1-(1-\delta)^{N_i -\kappa_i} \ge (N_i -\kappa_i) \delta - (N_i -\kappa_i)^2\delta^2/2\) and also \(\delta = \Omega(T^{-1/9})\), it follows that \[\begin{align} \sum_{q=1}^Q \sum_{k=1}^K \mathbb{P} \big( \big|[\mathcal{X}_i^q(k)]_{i} \big| > \kappa_{i} \big) \ge \Omega(QK\delta) = \Omega(T^{7/9}). \end{align}\] The proof of Proposition 1 is completed.

References↩︎

---

1. College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China; {iniesdu, liuch, zdq.bpz}@nuaa.edu.cn↩︎

2. School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China; yelintao93@hust.edu.cn↩︎

3. School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA; dsun@purdue.edu↩︎

4. The results obtained in this example consistently outperform the \((1-1/e)\)-approximate solution. Hence, for a clearer empirical comparison, we compute regret w.r.t. the optimal solution, rather than the \((1-1/e)\)-approximate one.↩︎

5. We denote \([y(m), y(n)] \in \{a, b\}\) to include both cases \([y(m), y(n)] = [a, b]\) and \([y(m), y(n)] = [b, a]\).↩︎