Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency
Authors: Qixin Zhang
Zongqi Wan
Yu Yang
Li Shen
Dacheng Tao
Venue: ICLR 2025 Spotlight (2025)
Keywords: Online Learning
Submodular Maximization
Surrogate Gradient
Multi-Agent
Primary area: reinforcement learning

Abstract: Coordinating multiple agents to collaboratively maximize submodular functions in unpredictable environments is a critical task with numerous applications in machine learning, robot planning and control. The existing approaches, such as the OSG algorithm,  are often hindered by their poor approximation guarantees and the rigid requirement for a fully connected communication graph. To address these challenges, we firstly present a $\textbf{MA-OSMA}$ algorithm, which employs the multi-linear extension to transfer the discrete submodular maximization problem into a continuous optimization, thereby allowing us to reduce the strict dependence on a complete graph through consensus techniques. Moreover, $\textbf{MA-OSMA}$ leverages a novel surrogate gradient to avoid sub-optimal stationary points. To eliminate the computationally intensive projection operations in $\textbf{MA-OSMA}$, we also introduce a projection-free $\textbf{MA-OSEA}$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Theoretically, we confirm that both algorithms achieve a regret bound of $\widetilde{O}(\sqrt{\frac{C_{T}T}{1-\beta}})$ against a  $(\frac{1-e^{-c}}{c})$-approximation to the best comparator in hindsight, where $C_{T}$ is the deviation of maximizer sequence, $\beta$ is the spectral gap of the network and $c$ is the joint curvature of submodular objectives. This result significantly improves the $(\frac{1}{1+c})$-approximation provided by the state-of-the-art OSG algorithm. Finally, we demonstrate the effectiveness of our proposed algorithms through simulation-based multi-target tracking.

Published as a conference paper at ICLR 2025
NEAR-OPTIMAL ONLINE LEARNING FOR MULTI- AGENT SUBMODULAR COORDINATION: TIGHT AP- PROXIMATION AND COMMUNICATION EFFICIENCY
Qixin Zhang' Zongqi Wan' Yu Yang" Li Shen Dacheng Tao
NNayynng Technological University, 639798, Singapore City University of Hong Kong, 518057, China SSnn Yat-sen University, Shenzhen 518107, China 'Chinese Academy of Sciences, Beijing 100190, China qxzhang4-c@my cityu. aethshenli@@malle com; dacheng. maoogmmill com
wanzengqi wwe.2s0eesstticccccmoomcmme...se
yuyangecityu.co edu.. edu.hk
ABSTRACT
Coordinating multiple agents to collaboratively maximize submodular functions in unpredictable environments is a critical task with numerous applications machine learning, robot planning and control. The existing approaches, such as the OSG algorithm, are often hindered by their poor approximation guarantees and the rigid requirement for fully connected communication graph. To address these challenges, we firstly present a MA-OSMA algorithm, which employs the multi- linear extension transfer the discrete submodular maximization problem into a continuous optimization, thereby allowing us to reduce the strict dependence on a complete graph through consensus techniques. Moreover, MA-OSMA leverages a novel surrogate gradient to avoid sub-optimal stationary points. To eliminate the computationally intensive projection operations MA-OSMA we also introduce a projection-free frree MA-OSEA algorithm, which effectively utilizes the KI. divergence by mixing a uniform distribution. Theoretically, we confirm that both algorithms
achieve a regret bound of Ö( Cr.
T-B against a (L approximation the
best comparator in hindsight, where CT is the deviation of maximizer sequence, 3 is the spectral gap of the network and is the joint curvature of submodular objectives. This result significantly improves the (T++ aapproximmaiinnn provided by the ofate-of-the-ar OSG algorithm. Finally, we demonstrate the effectiveness of our proposed algorithms through simulation-basee multi-target tracking.
INTRODUCTION
Recent years have witnessed an upsurge in research focused on leveraging submodular functions to coordinate the actions of multiple agents in accomplishing tasks that are spatially distributed. A compelling example is the dynamic deployment of mobile sensors, particularly unmanned aerial vehicles (UAVs), for multi-target tracking (Zhou et al., 2018; Corah & Michael, 2021) as depicted in Figure 1. In this scenario, each critical moment of decision, every mobile sensor needs to determine its trajectory and velocity through interactions with others to effectively track all moving points of interest. The primary challenges of this tracking challenge lie in the unpredictability of the targets' movements and the limited sensing capabilities of agents. To address these issues, various modeling techniques have been developed, including one based on dynamically maximizing a sequence of submodular functions that capture the spatial relationship between sensors and moving targets (Xu al., 2023: Rezazadeh & Kia, 2023; Robey et al., 2021). As result, the problem of target tracking can be cast into a specific instance of multi-agent online submodular maximization(MA. OSM) problem. Besides target tracking, the MA-OSM problem also offers a versatile framework for a variety of complex tasks such as area monitoring (Schlotfeldt et al., 2021; Li et al., 2023), environmental mapping (Atanasov et al., 2015: Liu et al., 2021), data summarization (Mirzasoleiman et al., 201 6a;b) and task assignment (Qu et al., 2019). Motivated by these practical use cases, this paper delves into the multi-agent online submodular maximization problem.
"Corresponding Authors

---

Published as a conference paper at ICLR 2025
Senser
Senning Pons
Prin trtarar.
Undiowaied Frigo
Figure I: Left: Malti-target tracking with 4 mobile sensors over complete directed acyclic commu- nication network. Right: Multi-target tracking with 4 sensors over a connected undirected graph.
To tackle the aforementioned MA-OSM problem, Xu et al. (2023) have recently proposed an online sequential greedy (OSG) algorithm, building upon the foundations of the classical greedy method (Fisher et al., 1978). Nevertheless, this online algorithm suffers from two notable limitations: Sub-optimal Approximation: In contrast with the tight ) 2010; Bian et al., 2017a), OSG only can guarantee sub-optimal (Ite) -approximation where E [0, 1] is the joint curvature of submodular objectives; ii) Requirement of Fully Connected Communication Network: OSG begins by assigning a unique order to each agent and then requires every agent have full access the decisions made by all predecessors, which leads complete directed acyclic communication graph (Refer to the left side of Figure 1). As the number of agents grows, the communication overheads associated with this operation may become prohibitively high. Furthermore, Grimsman et al. (2018) have pointed out that the approximation guarantee of OSG continuously degrades as the communication graph becomes less dense. This highlights the necessity of a complete communication graph for maintaining the effectiveness of OSG. Given these disadvantages of OSG algorithm, the objective of this paper is address the following question:
>apppoximmttinn ratio (Vondrák,
Is it possible to devise an online algorithm with tight (²- >approxximation for MA-OSM problem over a connected and sparse communication network?
In this paper, we provide an affirmative answer to this question by presenting two online algo- rithms, i.e., MA-OSMA and MA-OSEA, both of which not only can achieve the optimal ( (L e approximation guarantee but also reduce the strict requirement for complete communication graph.
Specifically, our proposed algorithms incorporate three key innovations. First, we utilize the multi- linear extension to convert the discrete submodular maximization into a continuous optimization problem, which enables us to reduce the rigid requirement for complete communication graph via the well-established consensus techniques in the field of decentralized optimization. Second, we develop a surrogate function for the multi-linear extension of submodular functions with curvature c, which empowers us to move beyond the sub-optimal (T-z)) aaprroxmaitii stationary points. Last but not least, for each agent, we implement a distinct strategy to update the selected probabilities associated with its own actions and those of other agents, which only requires agents to assess the marginal gains of actions within their own action sets, thereby reducing the practical requirement on the observational scope of each agent. To summarize, we make the following contributions.
We construct a surrogate function for the multi-linear extension of submodular functions with curvature E [o, 1]. The stationary points of this surrogate can guarantee a tight ( (-==")- approximation the maximum value of the multi-linear extension, significantly outperforming the 1 approximation provided by the stationary points of the original multi-linear extension itself.
We propose a new algorithm MA-OSMA, which seamlessly integrates consensus techniques, lossless rounding and the surrogate function previously discussed. Moreover, prove that
MA-OSMA enjoys regret bound of O CTT against (Lا approximation to the best
comparator in hindsight, where Cr is the deviation of maximizer sequence and | is the spectral gap of the communication network. Subsequently, present a projection-free variant of MA-OSMA, titled MA-OSEA, which effectively utilizes the KL divergence by mixing uniform distribution.
We also prove that MA-OSEA can attain ( (=rer)) -eegrett bound of Ō
CrT
A detailed
comparison of our MA-OSMA and MA-OSEA with existing studies is presented in Table 1.
2

---

Published as a conference paper at ICLR 2025
Method
Approx.Ratio Graph(()
Regret
Projection- free?
Reference
OSG
complete
VCT
Xu et al. (2023)
OSG
connected
δ
VCTT
Grimsman al. (2018); Xu al. (2023)
MA-OSMA
connected
0
C 1-
x
Theorem & Remark 8
MA-OSEA
connected
δ
Theorem & Rernark
Table 1: Comparison with prior works. T' is the horizon length, E. [O, 1] is the joint curvature of submodular objectives, Or the deviation of maximizer sequence, |8 is the second largest magnitude of the eigenvalues of the weight matrix, aGG) is the number of nodes in the largest independent set in communication graph G where ((G) and O()) hides log(T)) term.
We conduct simulation- evaluation of our proposed algorithms within a multi- tracking scenario. Our experiments demonstrate the effectiveness of our MA-OSMA and MA-OSEA.
Related Work. Due space limits, we only focus on the most relevant studies. more compre- hensive discussion is provided in Appendix A. Multi-agent submodular maximization (MA-SM) problem involves coordinating multiple agents to collahoratively maximize submodular utility function, with numerous applications in sensor coverage (Krause et al., 2008; Prajapat et al., 2022) and multi-robot planning (Singh et al., 2009; Zhou & Tokekar, 2022). A commonly used solution for MA-SM problem heavily depends the distributed implementation of the classic sequential greedy method (Fisher et al., 1978), which can ensure a ( (1t aapproximaao (Conforti & Cornuéjols, 1984). However, this distributed algorithm requires each agent to have full access to the decisions of all previous agents, thereby forming a complete directed communication graph. Subsequently, several studies (Grimsman et al., 2018; Gharesifard & Smith, 2017: Marden, 2016) have investigated how the topology of the communication network affects the performance of the distributed greedy method. Particularly, Grimsman et al. (2018) pointed out that the worst-case performance of the distributed greedy algorithm will deteriorate in proportion to the size of the largest independent group of agents in the communication graph. Given that the majority of applications occur in time-varying environments, Xu al. (2023) proposed the online sequence greedy(OSG) algorithm for online MA-SM problem, which also ensures a sub-optimal
appprxximation over complete communication graph.
PRELIMINARIES AND PROBLEM FORMULATION
Notations. Throughout this paper, I and R,, denote the set of real numbers and non-negative real numbers, respectively. For any positive integer K, [K] stands for the set (1.... K). Let represent norm for vectors and its dual norm be denoted by || II Specially, 11 and || ll2 denote the norm and la norm for vectors, respectively. (.-)) denotes the inner product. The lowercase boldface (e.g. x) denotes a column vector with suitable dimension and the uppercase boldface (c.g. W) for a matrix. The i-th component of a vector x will be denoted x; and the element the i-th row of the j-th column of a matrix W will be denoted by Wyy. Moreover, (W) denotes the i-th largest cigenvalue of matrix W. I, and 1, represent the identity matrix and the n-dimensional vector whose all entries are 1, respectively. Additionally, for any vector E 1 and S C [n.]. the [x]s denotes the projection of x onto the set S, i.e., [x]s
Fiss) E R for any S = (1 (.. .
S [n].
Submodularity and curvature. Let V be finite set and f : 2 + R,, be set function mapping subsets of V to the non-negative real line. The function f said to be submodular iff f(S (e)) f(S) 2 f(T U {e)) - fT") for any 5 C T S V and e E V \ T. In this paper, we will consider submodular functions that are monotone, meaning that for any S C T V. J(S) S S(T), and normalized, that is. f(0) = 0. To better reflect the diminishing returns property of submodular functions, Conforti Cornuéjols (1984) introduced the concept of curvature, which is defined as
c:= 1 minscvvees [(SU(e))-(($) Moreover, we can infer c E [0, 1] for submodular functions. f((e))
2.1 PROBLEM FORMULATION
In this subsection, we introduce the multi-agent online submodular maximization problem, commonly abbreviated multi-agent submodular coordination.
3

---

Published as a conference paper at ICLR 2025
In MA-OSM, we generally consider group of N different agents denoted = 21, NY, interacting over a connected communication graph G(N, .). In addition, each agent i within N is equipped with unique and discrete set of actions, denoted by V,- This implies that these action sets are mutually disjoint, i.e., VinV = 0 for any two distinct agentss agents i E N and E W. At each time step every agent i E A separately selects an action at, from the individual action set V, After
(T), e committing to these choices, the environment reveals a monotone submodular function ft defined over the aggregated action space V := Vi Then, the agents receive the utility fa(UieN' (a),))) As result, the objective of agents at any given moment is to maximize their collective gains as much as possible, that to say, we need to solve the following submodular maximization problem in a multi-agent manner at each round:
max (A(),, s.t. [A S E
Compared to the standard centralized submodular maximization problem, this MA-OSM problem brings additional challenges: 1) Unpredictable Objectives and Actions: Agents must make decisions each moment without prior knowledge of future submodular utility functions and the insight into other agents' actions; 2) Limited Feedback: In many real-world scenarios, each agent is typically endowed with narrow perceptual or detection scope, which only allows to sense the environmental changes within its surroundings. For instance, in the target tracking problem of Figure I, every sensor usually overlooks these targets beyond its sensing circle. Broadly speaking, the local information observed by one agent is inadequate for precisely assessing the actions of most other agents who are not in close vicinity. To capture this, various studies (Xu al., 2023; Rezazadeh & Kia, 2023; Robey et al., 2021; Qu et al., 2019) related to MA-OSM problem commonly confine each agent E .' to a local marginal gain oracle O : V; x 2 + RR after Je is revealed, where (a, := fAA {a}) - (AA) for any E V; and A C V. This restriction means that, at each time t E [T], agents only can receive the limited feedback about the marginal evaluations of actions within their own action set, rather than the full information of ft. In this paper, we also impose this restriction on each agent.
Given the NP- IP-hardness of maximizing a submodular function subject to a general constraint ( (Vondrák, 2013; Bian et al., 201 7b), we adopt the dynamic a-regret to evaluate the algorithm performance for MA-OSM problem in this paper, which is defined as follows (Kakade al., 2007; Streeter & Golovin, 2008; Chen et al., 2018):
T
Reg.. d (T) = a Σ f((A)) - - f(lsiEN(aa.))
where AZ is the maximizer of (1) and 04,; is the action taken via the agent E N at time / [7]-
MULTI-LINEAR EXTENSION AND ITS PROPERTIES
Compared discrete optimization, continuous optimization has plethora of efficient tools and algorithmic frameworks. As a result, common approach in discrete optimization is based on a continuous relaxation to embed the corresponding discrete problem into a solvable continuous opti- mization. In the subsequent section,we we will present canonical relaxation technique for submodular functions, known as multi-linear extension (Calinescu et al., 2011: I; Chekuri et al., 2014). To better illustrate this extension, we suppose | n and set V == [m]] = (1...., n) throughout this paper.
Definition 1. For a set function f 2 + IR,, we define its multi-linear extension as
F(x)= = Σ (F(A) (((A))
II Ja II (1)=a))
ER- = (F(R)).
(2)
ACV
aEA
a
where x x= - tx) E 1]" and R C V is a random set that contains each element a E V independently with probability Va and excludes it with probability Fa. We write R X to denote that R C V is a random set sampled according to x.
From the (2), we can view multi-linear extension at any point x E [0, 1|"d as the expected utility of independently selecting each action a E V with probability Ie- With this tool, we can cast the previous discrete problem E1) into a continuous maximization which learns the selected probability for each action E V, that is, for any t E (T), we consider the following continuous optimization:
max Fx(),, s.t. Σ La S LL,Vi, xE|O,1]
V
4

---

Published as a conference paper at ICLR 2025
where (x) is the multi-linear extension of ft. When fo is submodular, the maximization problem Eq.(3) is both non-convex and non-concave (Bian et al., 2020). Thanks to recent advancements in optimizing complex neural networks, large body of empirical and theoretical evidence has shown that numerous gradient-based algorithms, such as projected gradient methods and Frank Wolfe, can efficiently address the general non-convex non-concave problem. Specifically, under certain mild assumptions, many first-order gradient algorithms can converge to a stationary point of the corresponding non-convex or non-concave objective (Nesterov, 2013; Lacoste-Julien, 2016; Jin et al., 2017; Agarwal et al., 2017; Hassani et al., 2017). Motivated by these findings, we proceed to investigate the stationary points of the multi-linear extension of submodular functions.
3.1 CHARACTERIZING STATIONARY POINTS
We begin with the definition of a stationary point for maximization problems.
Definition 2. A vector x E C is called stationary point for the difserentiable function G [0, 1]m
funcciioonnn
R. over the domain _ [0, 1]" if maxyec (y x, VG(x)) S O.
Stationary points are of great interest as they characterize the fixed points of a multitude of gradient- based methods. Next, we quantify the performance of the stationary points of multi-linear extension relative to the maximum value, i.e.,
Theorem 1 (Proof is deferred to Appendix B). If 2 + =R_ is monotone submodular sibnodularfuunctionn with curvature c, then for any stationary point x of its multi-linear extension F: :0 domain C S [0, 1J", we have
[0, 1]" - RR over
F(x)
max F (
yEC
Remark 1. The ratio 1 is tight for the stationary points of the multi-linear extension of submodular 14c
function with curvature c, because there exists a special instance of multi-linear extension with a (5) apprrxximmtionn stationary point when e (Hassani et al., 2017).
Theorem suggests that applying various gradient based methods directly to multi-linear extension only can ensure a I+c
_ approoxixiii guarantee. However, the best-known approximation ratio for maximizing a monotone submodular function with curvature is I-c (Vondrák, 2010; Bian et al., 2017 As depicted in Figure 2, there exists a negnnggli gap between I+c and 1- The question arises: Is it feasible to bridge this significant gap? Recently numerous studies have successfully leveraged a classic technique named Con-Oblivious Search (Alimonti, 1994; Khanna et al.. 1998; Filmus& & Ward, 2012; 2014) to output superior solutions by constructing an effective surrogate function. Inspired by this idea, we also
Awee
0.9
Figure
TTe
aspire to devise surrogate function that can enhance the approximation guarantees for the stationary points of multi-linear extension. In line with the works (Zhang et al., 2022; 2024; Wan et al., 2023), we consider type of surrogate function F* (x) whose gradient at point assigns varying weights
to the gradient of multi-linear extension at * x, given by F F*)(x) = fo V= a æ)dz where wx2) is the positive weight function over [0, 1] and x denotes the multiplication of scalars and vectors.
After carefully selecting the weight function w(2), we can have that:
Theorem 2 (Proof deferred to Appendix C). the weight function w=()) = cl(s-1) and the function F: [0, 1]" + R, is the multi-linear extension of a monotone submodular function f 24 - R. with curvature c, we have, any x, [0,1]"
(y x, (x) -
((0s)))(x)))) (y-
ccl=-1) x)dz )
(4)
Remark 2. Theorem 2 illustrate that the stationary points of surrogate furntiatefuucctin F*(x) can provide better 1-e_0 -approximation than the stationary points of the original multi-linear extension F. Remark 3. Unlike prior work on surrogate functions regarding the multi-linear extension of sub- modular functions (Zhang et al., 2022; 2024), Theorem 2 takes into account the impact of curvature. 1, our result E4.(4) is consistent with those of Zhang al. (2022; 2024). To the best of our knowledge, we are the first to explore the stationary points of the multi-linear extension of submodular functions with different curvatures.
Specifically, when the curvature
5

---

Published as a conference paper at ICLR 2025
3.2 CONSTRUCTING AN UNBIASED GRADIENT FOR SURROGATE FUNCTION
In this subsection, we present how to estimate the gradient (x) = fg e<(3-1) F(z * æ)dz using the function values of f. Given that F is the multi-linear extension of set function f. we can show 2f(x) ER~x [(R U {i}) ((R {ii)) (Calinescu al., 2011). That is to say. the partial derivative of multi-linear extension F at each variable I; equals the expected marginal contribution for the action {z}. Consequently, after sampling random number 2 from the probability distribution
of r.v. 2 where P(Z I b) = (--س-e) Jo co(s-1) =
<(b-1)- for any E [0, 1] and then l-e- generating random set R according to 2 x, we can estimate (x) by the following equation:
Fx) ) (I(RU S(R) ..........RRUUURR....... I(RU ((( J(R
\ \fn)))
(5)
4 METHODOLOGY
The mirror method, a sophisticated optimization framework, utilizes the notion of Bregman divergence in lieu of Euclidean distance for the projection step. thereby unifying spectrum of first-order algorithms (Nemirovsky & Yudin, 1983). In this section, we present two multi-agent variants of the online mirror ascent (Hazan et al., 2016; Jadbabaie et al., 2015; Shahrampour & Jadbabaie, 2017), which is specifically crafted to tackle the MA-OSM problem introduced in Section 2.1.
4.1 MULTI-AGENT ONLINE SURROGATE MIRROR ASCENT
Given the role of Bregman divergence in the mirror ascent method, begin with an in-depth review of this concept, that is,
Definition 3 (Bregman Divergence). Let Φ Ω + I is a continoustydiiffeeettbbl 1-strongly
convex function defined on a convex set Ω C [0, 1]". Then the Bregman divergence with respect to ø defined as:
Dx(x.y) = (xx) - (yy) xV
(6)
Two well-known examples of Bregman divergence include the Euclidean distance, which arises
from the choice of o(x) ||x| and the Kullback-Leibler (KI.) divergence, associated with o(x) Er Iy log(x;). Note that both forms of é(x) allow for coordinate-wise decomposition. Without
loss of generality, we make the following assumption.
Assumption 6(x) is dominated by a one-dimensional strongly convex differentiable function g: [0, + R, that is, <(x) > g(x.) where x = (æ),..... In).
Under this assumption, we can re-define the Bregman divergence between two n-dimensional vectors b and as: Dg. (b,, c) Σi= (1(()()))) g((;) ((()) cs) where g' denotes the derivative of g. Specially, also have (x(x,y) Dg. (x.,) from (6) Building these foundations, we now introduce the Aggett Online Boosting Mirror Ascent (MA-OSMA) algorithm for MA-OSM problem, as detailed in Algorithm 1.
In Algorithm 1, at every time step t E [T). each agent E N maintains local variable x E [o. 1]|V| which, to some extent, reflects agent i's current beliefs regarding all actions V. The core of MA- OSMA algorithm is primarily composed of four interleaved components: Rounding, Information aggregation, Surrogate gradient estimation and Probabilities update. Specifically, at every iteration t [T]. each agent first seleets action a,, from V, based on its current preferences X1, Subsequently, agent i receives Xt.j from all neighboring agents and then computes the aggregated beliefs Yt, as the weighted average of xt, for j NN where N, denotes the neighbors of agent i. Next, agent i estimates the gradient of the surrogate function of the multi-linea extension of fe at each coordinate
V, by employing the methods outlined in Section 3.2. That is, agent i initially 1-e-c
samples a random number ž₁,; from the random variable 2, where P(Z S b) (00-1) for any E [0. 1), and then approximates [ (x),)) as 1-e (fe(R., U {a}) Si (a))) for any a V; where R, is a random set according to 2,,i Xt,i. Finally, each agent adjusts the probabilities actions in V; through a mirror ascent along the direction Fx,, As for other actions not in V,, their probabilities are straightforwardly updated using the aggregated beliefs yt,i-

---

Published as a conference paper at ICLR 2025
Algorithm 1 Multi-Agent Online Surrogate Mirror Ascent (MA-OSMA)
1: Input: Number of iterations T, the set of agents N, communication graph G(N, E), weight
matrix W = [w)k]] E R RN 1-sttrongly decomposable convex function ((x) = >i=1 ((ri), the curvature E (0, 1), step size Y for E [T];
2: Initialized: for any agent E EN, let [x1,]] = M Vj E V. and [x1,]] = 0, Vj $ VV
3: for t [T] do
4: for E do
5: Compute SUM :- E.ev, (xr,]a Rounding (Lines 5-6)
6:
Select action or, from the V; with probability SSM
[xcill
7:
Exchange X,,i with each neighboring node j E Nr b. Information aggregation (Lines 7-8)
8:
Aggregate the information by setting Ye.i ΣjeNsu(i) Wyyx,
9:
Sampling a random number Z4, from r.v. Z Surrogate gradient estimation (Lines 9-11) Sampling random set R4 1-e- (fe(Re, (a)) fe(R1, / \ fa))) for any a E V;
10:
21,5 Xt.5
Compute [V Update [x = [yr,ala Va & Vi Update the probabilities of actions (Lines 12-13)
13:
Update the probabilities of actions of agent itself by
( ([V F3. (xe,))y b) + ?
Dons (b, bo.ddve))
[x++1aly == arg min
(7)
Em bi
where = [R1] and b (b.....,buy bn;) ) [0.
The key novelty of Algorithm is twofold: first, integrates a surrogate gradient estimation for the multi-linear extension of ft, ensuring tight approximation guarantee; second, it adopts a divide- and-conquer strategy to update the probabilities of all actions in Lines 12-13, which only requires agents evaluate the marginal benefits of actions within their own action sets. These tactics not only effectively reduce the computational burden for each agent but also partially offset the practical errors caused by the limited observational capabilities of each agent.
4.1.1 REGRET ANALYSIS FOR ALGORITHM
In this subsection, we present theoretical results for the proposed method MA-OSMA. We begin by introducing some standard assumptions about the communication graph G(V, weight matrix W E N Bregman divergence D and the surrogate gradient estimation F
Assumption 2. The graph G is connected, i.e., there exists path from any agent i E N to any other agent j E N. Moreover, the weight matrix W [w:yy] E N N is symmetric and doubly stochastic with positive diagonal. iee. W W and WIN 1N, where N is the number of agents.
Remark The connectivity of communication gruph G implies the uniqueness of X (W) =1 and also warrants that other eigenvalues of W are strictly less than one in magnitude (Nedic & Ordaglar, 2009 Horn Johnson, 2012; Yuan et al., 2016). In detail, regarding the eigenvalue of Wiiee, 1 = (W) 2 >2( ... > AN(W) > -1, then 3 < L.where is the second largest magnitude of the eigenvalues of W.
max([>a (W))))))))))))) [xx()))
Assumption 3. Let x and [y:j be vectors in 1]", the Bregman divergence satisfies the separate
convexity in the following sense De (x ( s =NN Do(x, o:y;), where Σ 0: 1.
Remark 5. The separate convexity (Bauschke & Borwein, 2001) is commonly satisfied for most used cases of Bregman divergence. For example, the Euclidean distance and KL--divergence.
Assumption 4. The Bregman divergence satisfies a Lipschitz condition, i.e., there exists a constant K. such that for any x, x,y, E [0, 1]", we have [D,(x. z) -Do(y, z)1 < K||x-
Remark 6. When the function & is Lipschitz with respect to || II. the Lipschitz condition on the Bregman divergence is automatically satisfie.. Thus, this assumption evidently holds for Euclidean distance. However, KL divergence is not satisfied with Assumption 4, as its gradient will approach infinity on the boundary.
7

---

Published as a conference paper at ICLR 2025
Assumption 5. For any t [T] and x [0, the stochastic gradient Fx)(x) is bounded and unbiased, i.e., E(VE, (x) = (x) and E(IV (X)VF? (x)]l²) < G2. Here, || 1|+ the dual norm of the general norm
Moreover, Fj is also L-smooth, i... (x) F (y) II- S L|xx yll-
A detailed discussion regarding Assumption will be presented in the Appendix A.2. Now we are ready to show the main theoretical result about Algorithm 1.
Theorem (Proof is deferred to Appendix D). Consider our proposed Algorithm 1, if Assumption 1-5 hold and each set function ft is monotone submodular with curvature for any & E [T], then we can conclude that, when a T
NR
T
A4 71-1
NG
T
E Reg (T) SC
117)
+ KNC₂
Σ
nt (8)
1r+1
2 [=1
where A is any maximizer of El,(1), A is the symmetric difference of two sets, C1 = (4G +
LDG)N |x|| S C211x|1a for x E [0, 1)", , D suex.yee ||x - yll, R² = supx,ye Do (x, and
is the constraint set of E3)
Remark 7. According to the definition of symmetric difference, i.e., SAT = (S (T) S), we can know that the value |Ai+1AA) quantifies the deviation between the optimal strategy set at time ++ 1 and the one at time i, which, to certain extent, reflects the environmental fluctuations.
where CT = - |Ai A the Remark 8. From Eq.(8), if we set q) =0 -VV B
deviation of maximizer sequence, we have that DT. TH (F.(AA) 2 (L ( E. Sc(At)
o (V
CrT ). which means that Algorithm I can attain a dynamic regret bound of O 1-8
CCTT) 1-3
against (2-6")) >approximaation to the best comparator in hindsight.
4.2
PROJECTION-FREE MULTI-AGENT ONLINE SURROGATE ENTROPIC ASCENT
The primary computational burden of Algorithm 1 lies in Line 13, where each agent is tasked with single constrained mirror projection. Despite that this projection can be done very efficiently in linear time using standard methods described in (Pardalos & Kovoor, 1990; Brucker, 1984), the optimal solution to (7) admits an analytical expression when KL-divergence is selected as the metric. That is, we have the following theorem, whose proof is deferred to Appendix E.
Theorem 4. Let m be a positive integer and g(x) = x log(z). Then, the optimal solution x ((z. b) + D (b.m(bby)) satisfies the following conditions: if to the problem minl (.
EmH yi exp(pxp) < 1, x; = YA (x)( otherwise, Ij 31 exp(-2() 3: exp
Vi E [m]]
However, KL divergence does not meet with the Lipschitz condition in Assumption 4, as its gradient approaches infinity on the boundary. Fortunately, this drawback can be circumvented by mixing a uniform distribution. As result, we get the projection-free Multi-Agent Online Surrogate Entropic Ascent (MA-OSEA) algorithm for the MA-OSM problem, as shown in Algorithm 2. Similarly, we also can verify the following regret bound for MA-OSEA algorithm.
Theorem 5 (Proof deferred to Appendix F). Consider our proposed Algorithm 2, if Assumption 1,2,3 and 5 hold, || I| is l norm and each set function is monotone submodular with curvature c, then we can conclude that, when a -e
NC₂
AAH
NG
Ca
E (T) S SC sci( (EE (8- (B-BA)--Th))
+C2
Σ
Σ
7)-
Σ
+GDY
11
M++1
2
T
t=1
t=1
(9)
where A is any maximizer of (1), Ci = (4G² + LDG)NE, C2 = Nlog(()) C3 = 2N27,
D = supxyec ||x -Yll and C is the constraint set of (3).
Remark 9. From (9) if we set To 0 (V (1-8)C
and ? =O(T-2) where Cr
It Ait) we have that It 16 (F((A))) 2 (Le
Σt f((A;) -ō (0V (/==T)
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 Multi-Agent Online Surrogate Entropic Ascent (MA-OSEA)
1: Input: Number of iterations T, the set of agents N,, communication graph G(V, E), weight ma-
trix W = [wiyg] E IR N 1-strongly decomposable convex function x(x) = -i=1 Ty log(z;),
the curvature E [0, 1], step size Vi for E [m)xixiing parameter 7;
2: Initialized: for any agent E NV let [x1,]] = [ Vj E V, and [x1,]] = 0, Vj VV
3: for t [T] do
4: for E do
5: Compute SUM Eoev, (x,e]a Rounding (Lines 5-6)
Select action or,: from the set V; with probability [xc,i]=
6:
SUM
7:
Compute &t, (1 - >))x 11. Mixing (Line 7)
8:
Exchange Xt,; with each neighboring node j E Ni >> Information aggregation (Lines 8-9)
9:
Aggregate the information by setting Ye,a ZeenURg WiyXt,
10:
Sampling a random number Ze,i from r.v. 2
Surrogate gradient estimation (Lines 10-12)
11:
Sampling a random set Re, Z1,1 Xt.i
12:
Compute (x+,))) - (fa(Re, - \ {a})) for any a E V; Update [x [yt,e]a Va Vi Update the probabilities of actions (Lines 13-18)
I-c
13:
Compute SUM; == Ener, (Ivi,ll exp(n[VVF)
14:
15:
if SUM, < then
16:
X iy, exp(m) [V (xx,))))) for any Vi
17:
else
N+tidl [yr,dla exp(m (V ( for any a V.
NUMERICAL EXPERIMENTS
In this section, we evaluate our proposed Algorithm 1 and Algorithm 2 in simulated nulti-target tracking tasks (Corah & Michael, 2021; Xu et al., 2023) with multiple agents.
Experiment Setup. We consider a 2D scenario where 20 agents are pursuing 30 moving targets with T 2500 iterations from "up". "down", "left", "right", or "diagonally". Concurrently, agents also adjust their speeds from set of 10, or 15 units/s. As for targets, we categorize them into three distinct types: the unpredictable 'Random', the structured 'Polyline', and the challenging 'Adversarial'. Specifically, at each iteration, 'Random' target randomly changes its movement angle from [0, 2n] and moves at random speed between 5 and 10 units/s. A 'Polyline' target generally maintains its trajectory and only behaves like the 'Random' target {0, k. predefined total iterations and A a random number from (1,2, 4). As for the 'Adversarial' target, acts like 'Random' target when all agents are beyond 20 units. However, if any agent is within 20-unit range, the 'Adversarial' target escapes at speed of 15 units/s for one second, pointing to the direction that maximizes the average distance from all agents. In addition, we initialize the starting positions of all agents and targets randomly within 20-unit radius circle centered at the origin.
50 seconds. At every iteration, each agent selects its direction of movement
2T ..... (k-1)T 1-th iteration where T is the
Objective Function. We begin by defining the ground set (0,,,, [20].0 0 E { 2: of agents, respectively. Moreover, the symbol o, (j) denotes the 2D location of target j E [30] at time t [T] and of (0, s, i) stands for the new position of agent after moving from its location at time t the direction of a speed of s. order keep up with all targets, we naturally consider the fol-
s, i) : {5, 10, 15 15 Junits/s, i E where 0, 8, represent the movement angle, speed and the identifier
x 3r .....,
2T}} ,
lowing submodular objective function for each time t: fe( = " j=1 max(0.s.))e. (1)
where d(., -) is the distance between two locations and A C V.
Analysis. In Figure 3, we assess our proposed MA-OSMA and MA-OSEA against OSG (Xu et al., 2023) across scenarios with different proportions of 'Random', 'Polyline,, and 'Adversarial' targets. The ratios are setting as 'R'''A':''''SSS in Figure 3(g)-3(i). The suffixes in MA-OSMA and MA-OSEA represent two different choices for communication graphs: 'c" for a complete graph and 'r' for an Frdos-Renyl random graph with average degree 4. From Figure 3(d).3(d) and 3(g), we can find that the running average utility
in Figure 3(a)-3(c), 6:3:1 in Figure 3(d)-3(f) and 4:5:1

---

Published as a conference paper at ICLR 2025
120
Ave. cunulative unllay.
1.00
20
Ave. mamber
60-
0.3
Ave.
40
0.2
20
0.1
500
1000
1530
2000
2530
1000
1500
2000
2500
500
1000
3500
2000
2500
Beration index
(a) Average Utility
(b) Average Number
(c) Average Distance
Ave. cumulativv unilsy
1.00
0.3
80-
Ave number
60
10
Ave.
10
20-
0.1
500
50000
1530
2000
2520
5.0
1.000
1520
2000
2500
500
1000
1500
2000
2500
lteration index
lieration index
llerationn indox
(d) Average Utility
(c) Average Number
(f) Average Distance
Ave asmmlavvv uillit
355
40)
Avee mumber
Ave. distamoe
-30
2.4
0.2
500
1000
1505
2000 2500
500
1005
1500
2000
2500
500
1000
1500
2000
2500
lieration index
lieration index
Eleration index
(g) Average Utility
(h) Average Number
(i) Average Distance
Figure 3: Comparison of average cumulative utility, average number of targets within 5 units, average distance of Top-5 nearest targets of AAA-OSAAA.MM--OSSAA MAAAAAA--,M--SSAAA MA-OSEA-CCC and MA-OSEA-C with OSG on different multi-target tracking scenarios(averaged over 5 runs).
سا (Usewv of our proposed MA-OSMA and MA-OSEA significantly outperforms the
OSG algorithm, which is in accord with our theoretical analysis. Similarly, the average number of targets within units for MA-OSMA and MA-OSEA greatly exceeds that of the OSG, as depicted in Figure 3(b),3(e) and 3(h). Note that, due 'Adversarial' targets, all curves for the average number exhibit a downward trend. Furthermore, our proposed MA-OSMA and MA-OSEA also can effectively reduce the average distance shown in Figure 3(c), 3(), and 3(). Note that the algorithms over random graph perform comparably to those on complete graph in all figures, which, some extent, reflects the communication efficiency of our proposed algorithms.
CONCLUSIONS
This paper presents two efficient algorithms for the multi-agent online submodular maximization problem. In sharp contrast with the previous OSG method, our proposed algorithms not only enjoy tight( (-==") ( )appproximttion but also reduce the need for complete communication graph. Finally, extensive empirical evaluations are performed to validate the effectiveness of our algorithms.
In many real-world scenarios, the local information gathered by one agent is often contaminated with noise, thereby leading to imperfect assessments of the marginal gains of its own actions. To tackle this challenge, a compelling strategy is to extend our regret analysis to accommodate the estimation errors inherent in marginal evaluations, as exemplified by the work of Corah & Michael (2021). Furthermore, another innovative direction is to generalize Algorithms and 2 to adapt to time-varying and directed network topology (Nedić & Olshevsky, 2014; Nedić et al., 2017), as opposed to the static and undirected structure that is assumed. Lastly, the most promising direction is to design a parameter-free algorithm that eliminates the dependency curvature of Algorithms and 2.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This research is supported by STI 2030-Major Projects (No. 2021ZD0201405) Shen- zhen Basic Research Project (Natural Science Foundation) Basic Research Key Project (NO. JCYJ2024120211 10212443004) and the RIE2025 Industry Alignment Fund Industry Collaboration Projects (IAF-ICP) (Award 12301)0026), administered by A*STAR, as well as supported by Alibaba Group and NTU Singapore through Alibaba-NTU Global e- SSustainabilityy CorpLab (ANGEL).
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. Proceedings of the 49th Anmual ACM SIGACT Symposium Theory of Computing, pp. 1195-1199, 2017.
Paola Alimonti. New local search approximation techniques for maximum generalized satisfiability problems. In Itulian Conference Algorithms and Complexity, pp. 40-53. Springer, 1994.
Nikolay Atanasov, Jerome Le Ny, Kostas Daniilidis, and George J Pappas. Decentralized active information acquisition: Theory and application to multi-robot slam. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 4775-4782. IEEE, 2015.
Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning via submodular maximization. In International Conference on Learning Representations, 2022.
Heinz H Bauschke and Jonathan M Borwein. Joint and separate convexity of the bregman distance. In Suudies Computational Mathematics, volume pp. 23-36. Elsevier, 2001.
Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In International conference on machine learning, pp.
PMLR, 2017a.
Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed non- convex optimization: Submodular maximization over continuous domains. In Artificial Intelligence and Statistics, pp. 120. PMLR, 2017b.
Yatao Bian, Joachim M Buhmann, and Andreas Krause. Continuous submodular function maximiza- tion. arXiv preprint arXiv:2006. 33474, 2020.
Peter Brucker. An (n) algorithm for quadratic knapsack problems. Operations Research Letters, (3):163-166, 1984.
Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6): 201
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43(6): 1831-1879, 2014.
Gong Chen and Marc Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):338-553 543, 1993.
Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In International Conference on Artificial Intelligence and Statistics, pp. 1896-1905. PMLR, 2018.
Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations the rado-edmonds theorem. Discrete applied mathematics, 733):251-274, 1984.
Micah Corah and Nathan Michael. Scalable distributed planning for multi-robot, multi-target tracking. In 2021 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 437 4444444 IEEE, 2021.
11

---

Published as a conference paper at ICLR 2025
Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19(3): 1-34, 2018.
Bin Du, Kun Qian, Christian Claudel, and Dengfeng Sun. Jacobi-style iteration for distributed submodular maximization. IEEE transactions automatic control, 67(9):4687-4702, 2022.
Khalid El-Arini, Gaurav Veda, Dafna Shahaf, and Carlos Guestrin. Turning down the noise in the blogosphere. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 289-298, 2009.
Ziqing Fan, Siyuan Du, Shengchao Hu, Pingjie Wang, Li Shen, Zhang Ya, Dacheng Tao, and Yanfeng Wang. Combatting dimensional collapse Ilm pre-training data via diversified file selection. In The Thirteenth International Conference on Learning Representations, 2025.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integnnn integrated differential estimator. Advances in neural information processing systems, 31, 2018.
Yuval Filmus and Justin Ward. The power of local search: Maximum coverage over a matroid. In 29th Symposium Theoretical Aspects of Computer Science, volume 14, pp. 601-612. LIPIcs, 2012.
Yuval Filmus and Justin Ward. Monotone submodular maximization over matroid via non-oblivious local search. SIAM Journal on Computing, (3(2):514-542 2014.
Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey. An analysis of approximations for maximizing submodular set functions -i.. In Polyhedral Combinatorics, pp. 73-87. Springer, 1978.
Hongchang Gao, Bin Gu, and My T Thai. On the convergence of distributed stochastic bilevel optimization algorithms over a network. In International Conference on Artificial Intelligence and Statistics, pp. 9238 92818 PMLR, 2023.
Bahman Gharesifard and Stephen Smith. Distributed submodular maximization with limited information. IEEE transactions on control of network systems, 5(4): 1645, 2017.
Michael Grant and Stephen Boyd. Cvx: Matlab software for disciplined convex programming. version 2.1, 2014.
David Grimsman, Mohd Shabbir Ali, Joao P Hespanha, and Jason R Marden. The impact of information in distributed submodular maximization. IEEE Transactions on Control of Network Systems, 6(4)) 1343, 2018.
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pp. 5841-5851, 2017.
Flad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-325, 2016.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pp. 398 406. PMLR, 2015.
Can Jin, Tong Che, Hongwu Peng, Yiyuan Li, Dimitris N. Metaxas, and Marco Pavone. Learning from teaching regularization: Generalizable correlations should be easy imitate. In The Thirth-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Can Jin, Tianjin Huang, Yihua Zhang, Mykola Pechenizkiy, Sijia Liu, Shiwei Liu, and Tianlong Chen. Visual prompting upgrades neural network sparsification: A data-model perspective. In The 39th Annual AAAI Conference Artificial Intelligence, 2024b.
12

---

Published as a conference paper at ICLR 2025
Can Jin, Hongwu Peng, Shiyu Zhao, Zhenting Wang, Wujiang Xu, Ligong Han, Jiahui Zhao, Kai Zhong. Sanguthevar Rajasekaran, and Dimitris N Metaxas. Apeer: Automatic prompt engineering enhances large language model reranking. arXiv preprint arXiv:2406. 14449, 2024c.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International conference on machine learning, pp. 1724-1732. PMLR, 2017.
Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pp. 546-555, 2007.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146, 2003.
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computa- tional views of approximability. SIAM Journal on Computing, 28(1):164-191, 1998.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008
Lilly Kumari, Shengjie Wang, Arna Das, Tianyi Zhou, and Jeff Bilmes. An end-to-end submodular framework for data-efficient in-context learning. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 3293-3308, 2024.
Simon Jullste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv preprint arXiv:1607.00345. 2016.
Peter D Lax. Functional analysis. John Wiley & Sons, 2014.
Ruolin Li, Negar Mehr, and Roberto Horowitz. Submodularity of optimal sensor placement for traffic networks. Transportation research part B: methodological, 171:29-43, 2023.
Yucheng Liao, Yuanyu Wan, Chang Yao, and Mingli Song. Improved projection-free online continu- ous submodular maximization. arXiv preprint arXiv:2305. 18442, 2023.
Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 912-920, 2010.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Pro- ceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 510-520, 2011.
Jun Liu, Lifeng Zhou, Pratap Tokekar, and Ryan K Williams. Distributed resilient submodular action selection adversarial environments. IEEE Robotics and Automation Letters, 6(3):5332-5839, 2021.
Jason Marden. The role of information in distributed resource allocation. IEEE Transactions on Control of Network Systems, 4(3):654-66) 664, 2016.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submod- ular maximization: Personalized data summarization. In International Conference Machine Learning, pp. 1358-1367. PMLR, 2016a.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization. The Journal of Machine Learning Research, 17(1):8330-837 2016b.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference on machine learning, pp. 3616-3625. PMLR, 2018
13

---

Published as a conference paper at ICLR 2025
Angelia Nedié and Alex Olshevsky. Distributed optimization over time- time-ngrying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-615) 2014.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48 61, 2009.
Angelia Nedić, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-narying graphs. STAM Journal Optimization, 27(4):2597-2333, 2017.
George Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical Programming, 14(1):265-294, 1978.
A.S. Nemirovsky and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interseiene series in discrete mathematics. Wiley, 1983.
Nesterov. Introductory Lectures on Convex Optimization: Basic Course, volume 87. Springer Science & Business Media, 2013.
Panos M Pardalos and Naina Kovoor. An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds. Mathemutical Programming, 46:321-328, 1990.
Mohammad Pedramfar, Christopher Quinn, and Vaneet Aggarwal. A unified approach for maximizing continuous dr-submodular functions. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 61 61114, 2023.
Mohammad Pedramfar, Yididiya Y. Nadew, Christopher John Quinn, and Vaneet Aggarwal. Unified projection-free algorithms for adversarial dr-submodular optimization. In The Twelfth International Conference Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, 2024.
Manish Prajapat, Matteo Turchetta, Melanie Zeilinger, and Andreas Krause. Near-optimal multi- agent learning for safe coverage control. Advances in Neural Information Processing Systems, 35:
2022.
Shi Pu and Angelia Nedic. Distributed stochastic gradient tracking methods. Mathematical Program- ming, 187(1):409-457 2021.
Guannan Qu, Dave Brown, and Na Li. Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica, 105:206-215, 2019.
Akbar Rafiey. Decomposable submodular maximization in federated setting. In Forty-first Interna- tional Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024.
Navid Rezazadeh and Solmaz S Kia. Distributed strategy selection: A submodular set function maximization approach. Automatica, 153:1 10000, 2023.
Alexander Robey, Arman Adibi, Brent Schlotfeldt, Hamed Hassani, and George Pappas. Optimal algorithms for submodular maximization with distributed constraints. In Learning for Dynamics and Control, pp. 150-162. PMLR, 2021.
Brent Schlotfeldt, Vasileios Tzoumas, and George J Pappas. Resilient active information acquisition with teams of robots. IEEE Transactions on Robotics, 38(1):244-261, 2021.
Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control, 63(3):714-725, 2017.
Amarjeet Singh, Andreas Krause, Carlos Guestrin, and William J Kaiser. Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, 34:707-755, 2009.
Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Advances in Neural Information Processing Systems, pp. 1577-1584, 2008
Jan Vondrák. Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms).. RIMS Kokyuroku Bessatsu B, 23:253 23:253-266, 23:253-266, 2010.
14

---

Published as a conference paper at ICLR 2025
Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265- 304, 2013.
Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi-linear dr- submodular maximization and its applications adversarial submodular bandits. In International Conference on Machine Learning, pp. 35491-35524. PMLR, 2023.
Jun Wang. Yu Yang, Qi Liu, Zheng Fang, Shujuan Sun, and Yabo Xu. An empirical study of user engagement in influencer marketing on weibo and wechat. IEEE Transactions on Computational Social Systems, (166)3222-32400 2022.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Using document summarization techniques for speech data subset selection. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 721-726, 2013.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pp. 1954 1963. PMLR, 2015.
Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, and Hui Qian. Decentralized gradient tracking for continuous dr-submodular maximization. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 2897-2906. PMLR, 2019.
Zirui Xu, Hongyu Zhou, and Vasileios Tzoumas. Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters, 8(4):226112268 2023.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1844 2016.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodu- lar maximization: Boosting via non-oblivious function. In International Conference Machine Learning, pp. 26116-26134, PMLR, 2022.
Qixin Zhang, Zengde Deng, Xiangru Jian, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Communication- efficient decentralized online continuous dr-submodular maximization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3330-3339, 2023.
Qixin Zhang, Zongqi Wan, Zengde Deng, Zaiyi Chen, Xiaoming Sun, Jialin Zhang, and Yu Yang. Boosting gradient ascent for continuous dr-submodular maximization. arXiv preprint arXiv:2401.08330. 2024.
Puning Zhao and Lifeng Lai. Minimax optimal learning with nearest neighbors. IEEE Transactions on Information Theory, 2024.
Puning Zhao, Lifeng Lai, Li Shen, Qingming Li, Jiafei Wu, and Zhe Liu. A huber loss minimization approach to mean estimation under user-level differential privacy. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Puning Zhao, Fei Yu, and Zhiguo Wan. A huber loss minimization approach to byzantine robust federated learning. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 21806- 21814, 2024b.
Lifeng Zhou and Pratap Tokekar. Risk-aware submodular optimization for multirobot coordination. IEEE Transactions on Robotics, 3865):0044-308, 2022.
Lifeng Zhou, Vasileios Tzoumas, George Pappas, and Pratap Tokekar. Resilient active target tracking with multiple robots. JEEE Robotics and Automation Letters, 4(1):129-136, 2018
Junlong Zhu, Qingtao Wu, Mingchuan Zhang, Ruijuan Zheng, and Keqin Li. Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 22(51):1-44 2021.
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL DISCUSSIONS
A.1 MORE DETAILS ON RELATED WORKS
Single-Agent Submodular Maximization, Maximization of submodular functions has recently found numerous applications in machine learning, operations research and economics, including data summarization (Lin & Bilmes, 2010; 2011; Wei et al., 2013; 2015), dictionary learning (Das Kempe, 2018), product recommendation (Kempe et al., 2003; El-Arini et al., 2009; Mirzasoleiman et al., 2016;; Wang et al., 2022). federated learning (Balakrishnan et al., 2022; Rafiey, 2024; Zhao et al., 2024a;b) and in-context learning (Kumari et al., 2024; Fan et al., 2025; Jin et al., 2024a;b;c). When considering the simple cardinality constraint, the classical works(Fisher et al., 1978; Nemhauser al., 1978) show that the greedy algorithm can achieve a tight (1 approxxapooiiiitiinn guarantee for monotone submodular maximization problem. As for the general matroid constraint, a continuous greedy algorithm with (1 1/e)--ppeppppaae-- -aprroxxxiaioonnnn guarantee is presented in (Calinescu et al., 201 I; Chekuri et al., 2014). Especially when the submodular function has curvature E [0, 1]. Vondrák (2010) pointed out that the continuous greedy algorithm also can achieve an improved (2 approximation guarantee.
Multi-Agent Submodular Maxinization. Multi-agent submodular maximization(MA-SM problem involves coordinating multiple agents to collaboratively maximize a submodular utility function. commonly used solution for MA-SM problem heavily depends on the distributed implemen- tation of the classic sequential greedy method (Fisher et al., 1978). which can ensure a (T+c)
approximation (Conforti & Cornuéjols, 1984) when the submodular function has curvature E [0, 1]. However, this distributed algorithm requires each agent to have full access to the decisions of all previous agents, thereby forming a complete directed communication graph. Subsequently, several studies (Grimsman et al., 2018; Gharesifard & Smith, 2017; Marden, 2016) have investigated how the topology of the communication network affects the performance of the distributed greedy method. Particularly, Grimsman et al. (2018) pointed out that the worst-case performance of the distributed greedy algorithm will deteriorate in proportion to the size of the largest independent group of agents in the communication graph. In order to overcome these challenges, various studies (Rezazadeh & Kia, 2023; Robey al., 2021; Du et al., 2022) utilized the multi-linear extension to design algorithms for solving MA-SM problem. Specifically, Du et al. (2022) devised a multi-agent variant of gradient ascent for MA-SM problem, which can attain OPPT c over connected communication graph at the cost of ( value queries to the submodular function where OPT is the optimal value. After that, to improve the -appproximation Robey et al. (2021) developed multi-agent variant of continuous greedy method(Calineseu et al., 2011; Chekuri et al., 2014) with tight (1 - 1 1/e)-app approxxiiiin However, this multi-agent continuous greedy(Robey et al., 2021) requires the exact knowledge of the multi-linear extension function, which will lead to the exponential query complexity. To tackle this drawback, Rezazadeh & Kia (2023) also proposed stochastic variant of continuous greedy method((allnnsee et al., 2011; Chekuri et al., 2014), which considers the curvature e of (og(()) value queries to the submodular function. In our Algoriúhm 1 and Algorithm 2, if any incoming objective function fi corresponds to some submodular function f and we return the set Usev s.. Vt E [T' with guarantee 2 + value queries in (Rezazadeh & Kia, 2023), the aforementioned variants of Algorithm and Algorithm 2 only require inquiring the
submodular objectives and can enjoy (T= (1==-)0Pp OOPTT - at the expense O(" e
probability 7 also can obtain two methods with the tight
for MA-SM problem. Notably, in sharp contrast with O logg() m(llo(())
submodular objective O and O log(t) times to attain (L OOPT - e, respectively. We present a detailed comparison of our proposed MA-OSMA and MÁ-OSEA with previous studies for MA-SM problem in Table 2.
Because the multi-linear extension of submodular set function belongs to the general continuous DR- submodular functions, we also review related works about decentralized continuous DR Dussubmodular maximization. As for more detailed content continuous Sussuunod maximization, please refer to Pedramfar et al. (2023; 2024).
Decentralized Continuous DR-submodular Maximization. A differentiable function F |0, 1]m - R. is ousbubood if V Fx) < VF(y) for any x 2 y. Mokhtari et al. (2018) is the first to study the decentralized continuous DR-submodular maximization problem, which showed an algorithm
16

---

Published as a conference paper at ICLR 2025
titled DeCG achieving (1-1/e) - for monotone and deterministic continuous DR-submodular maximization after O iterations and O 2 communications. When only an unbiased estimate of gradient is available, Mokhtari al. (2018) also presented decentralized method named DeSCG for monotone cases, which attains (1 1 1/ee PT - e with O communications after O iterations. Next, Xie et al. (2019) presented deterministic DeGT and stochastic DeSGTFW by applying the gradient tracking techniques(Pu & Nedić, 2021) to DeCG and DeSCG respectively. both of which achieve the (1 laprroxaiiin with faster O convergence rate and a lower O communications. After that, Gao et al. (2023) utilized the variance reduction technique(Fang et al., 2018) to propose two sample-efficint algorithms, namely, DeSVRFW-gp and DeSVRFW-ge both of which can reduce the sample complexity of DeSGTFW from O + to ( Lastly, several studies(Zhu et al., 2021; Zhang et al., 2023; Liao et al., 2023) extended these aforementioned offline decentralized frameworks to time-varying ORssubmodular objectives. It's important to note that the decentralized submodular maximization problem significantly differs from the multi-agent scenario emphasized in this paper. In the context of decentralized optimization, we typically assume that each local node maintains its own local utility function and the collective goal is optimize the sum of these local functions. In contrast, within the scope of this paper, we assume that all agents share a common submodular function but each agent restricted accessing a unique set of actions.
Method
Utlity
Gruph
Query Complexity
Reference
Greedy Method
(PP)
complete
Conforti & Cornuéjols (1984)
Greedy Method
Sidaa)OPP 1OPT -e
connected
Grimsman et al. (2018)
Projected Gradient Method
connected
Du et al. (2022)
CDCG
(1 -1-
connected
Robey et al. (2021)
Distribute--CG
1=pPTPPTT c connected
Rezazadeh & Kia (2023)
Algorithm
[ JOPT connected
+ Blogt
Theorem 3 & Remark 8
Algorithm 2
JOPT connected
Theorem 5 & Remark 9
Table 2: Comparison with prior works for Multi-Agent Submodular Maximization Problem. OPT the optimal value, e is the curvature of submodular objective, n := |V| the total number of all available actions, (G)) is the number of nodes in the largest independent set in communication graph G where (G) 2 1. Note that the column of Query Complexity only considers the setting that each agent selects one action.
A.2 MORE DISCUSSIONS ON ASSUMPTION 5
In this subsection, we show the Assumption 5 is well-established in both I norm and la norm. At first, we review that, in Section 3.2, we define that:
(x) ( (F(R f(R) \ ......... f(R) f(RU
e
\ {m))): f(R
(10)
c
where: 2 is sampled from the probability distribution of the random variable Z where P(z s b) =
(1-e-) So ez==-1) 1e for any b [0, 1] and R x.
I-e-0
From (10) and the submodularity of set function f. we can know that E(FF = F and E(I[F*(xx]l>>) < I-c c my where my max.ev f((a)) denotes maximum singleton value.
Moreover, Hassani et al. (2017) recently have shown that the multi-linear extension F of a submodular function f is mm-smooth under norm, that is, [VF(() - VF(y))loo I mnl|x yllı. From the
definition of surrogate function, we also know that F = fo' c1(==-1)V F(z ar)dz such that
(x) - (y)(l) $ L' ( VVF xx) VF
26 2c 20 - y112d
- + m - y
c²
17

---

Published as a conference paper at ICLR 2025
Therefore, we conclude that the surrogate function F of the multi-linear extension of sub- modular function f with curvature e E [0, 1] is ( (=
- -smooth under 4 norm. Due to -I lla I vall Il and || lla S Vvll lll. we also can show that B(I[FF(xx)ll)) & vn my
and |VF (y)(y))2 - n - my m ||x
yl12-
With the previous results, in Assumption 5, we can set G = I-me -1 maxeev (Ii(fa)))
540-1 max (filla))) under 4 norm. As for l norm, we consider G maXAEV.NE(T) (filta)) and I, = m ---+--1 max (fi(fa)).
and L =
1-
A.3 MORE DISCUSSIONS ON EXPERIMENTS
In this subsection, we highlight some additional details about the experiments.
At first, all experiments are performed in Python 3.6.5 using CVX optimization tool (Grant Boyd, 2014) on MacBook Pro with Apple MI Pro and 16GB RAM. Then, when considering the random graph, we set the weight matrix W as follow: if the edge (i. j) is an edge of the graph, let Wij = 1/(1 (1 max(d;, dz)) where d, and dj the degree of agent and j. respectively. If (i,j) is not an edge of the graph and + j. then Wij 0. Finally, we set W/ = 1 ΣjEN, Wij-
As for the complete graph, we set Waj where N is the number of agents. In MA-OSMA and MA-OSEA algorithms, set 1 and n7 7
B PROOF OF THEOREM
We begin by reviewing some basic properties about the multi-linear extension of a submodular function.
Lemma 1 (Calinescu et al. (2011); Bian et al. (2020)). When f - R4 is monotone submod-
ular function, its multi-linear extension F(x) = EAsy (IEAA ta Ioaga(1 xr,)) has the following properties:
1. F is monotone, that is, Oz: 2 for any E [n] and x E 1]";
aF(x)
2. F concave along any non-negative direction d E RT;
3. 01s
0F(x)
ERAX (f(RU ERRXX(F(RUU
f(R ( (i1)).
4. VF(x) 2 VF(y) for any S and x, E 1]".
With this lemma, we can show the following lemma.
Lemma 2 (Calinescu et al. (201 1); Bian et al. (2020)). when is the multi-linead extension of a monotone submodular function f. we can conclude that
y FF(x)) 2 F(xVy) F(x -FAA))2FF(xX 2F(x),
where x Ay == min(x, y) and V y max(x, y) are component-wise minimum and component- wise maximum, respectively.
Proof. From the second property about the concavity in Lemma 1 and y V and XA S first have that
(y V x Vx(x)) 2 Fly V x) F(x),
(11)
A M VF())) P(xAN) F(x).
Due to x + +y= = + x X y. we therefore that that (y (y-x. VF(x)) = -( Vx-xxx((xx))
+
(x VF())) F(x F(xAy) 2x)).. -F
18

---

Published as a conference paper at ICLR 2025
From the third property in Lemma and the definition of curvature [0, 1]. that is, c 1 mins ((Su(e))-ft ((S) we can conclude that, when f is monotone submodular, f(S {e})
(((t))
f(S) (1-c) for any $ S e.e & S such that, for any x E [0, 1|",
0F(x) ER~x (f(RU EEEEXEEXXXRRUU F(R (R)) (1- (1-c)(((()) = c) dr. Ōr:
aF().)
f(R
where O2 is n-ddimensional zero vector and we general suppose f(0) O. As result, we can show that
Lemma 3. when F is the qullti-inear extension of monotone submodular function f with curvature C, we have
F(xVy) 2 (1 -1==)(F())-F - + F(y).
Proof.
/' +7 -1). .VVy - -y)dz
- F(xVy)
==
2 (1 XV-))VV()
2 (1 XVV
= (1 (VF(xx))) x- -xAy)
2 (1 o) [((x) - P(xAy))
where the first inequality follows from VF + = - y)) (1 -01--)0 (O,)): the second
inequality comes from the fourth property in Lemma i.e., (F(..) V A y). The second equality is due to x +y VVy++ + +xAy and the final inequality from the concavity along non-negative
direction.
Merging Lemma 3 into Lemma 2, we finally have that (y X, VF(x)) 2 F(y) - - (1+)) such that if is stationary point for F over the domain F(y) (1 + e) Fxx) for any E C, so F(x) 2 Itc maxyec Fly).
1 [0, 1]", have that 0 2 (y xx VF())) 2
C PROOF OF THEOREM 2
In this section, we show the proof of Theorem 2. Before going into the details, we firstly prove the following lemma.
Lemma 4. when F is the multi-lineat extension of monotone submodular function with curvature
we have, for any y, X E [0,1]"
(v, VF(x)) 2 F(y) - cF(x).
Proof.
Due x xx=xxVy++ x A y, we have that
(y, (F(x)) = (xVy x, VF(x)) + (x VF(x))
F(XVy) F(x) + (1-c)(xAA,, VF(O.))
2 F(xVy) - F(x) ((1cc)F(xAy)
F(y) -cF(x),
where the first inequality follows from VF(x) 2 (1 (F-c))F(O.) and the concavity along non- negative direction, i.c., (x Vy xx VF(x)) 2 F(x Vy) F(x);; the final inequality comes from Lemma 3.
Next, verify Theorem 2.
19

---

Published as a conference paper at ICLR 2025
Proof. Firstly, prove that
c 1) V F2 x())x))d2)
0
ex==1)) (x, VF(z * x))dd
cde-liid (Fll)(F((3xx)) ((= F((=x))
(12)
d==1) F(z x -/6 (((+)))(((==1))
= F(x) - (((=-1) x(2xx)dz.
Then, we show an upper bound for (v ca(z-1) x)d2),
y, c(2 VVF x)d22 = =100 ol ly, (F(xx)) 2 / (F)
(13)
where the inequality follows from Lemma 4. Combining Eq.(12) with (13), we have
x, L'' ca(=-1) (F x))z 2 (f, e(=- F(y)) = (Lo cllz- ) FFx))F(x))
Note the So eo(s-1) = 1-
D PROOF OF THEOREM
In this section, we show the proof of Theorem 3. Before going into the details, we firstly review standard lemma for the mirror projection.
Lemma 5 (Chen & Teboulle (1993); Jadbabaie et al. (2015)). Let Φ 0, 1] - IR be 1-strongly convex function functiinn with respect to the norm || and (x(x,y) represent the Bregman divergence with respect to o, respectively. Then, any update the form
min (b. y) Do(y, yec
satisfies the following inequality
(xt z, < (z - -Dx(zx))DDxxxxx' Dx(xt,x)
for any E C where C is convex domain in [0,
Next, we verify that each local variable X1, of Algorithm 1 is included in the constraint of continuous problem (3) for any E [T] and i E N. Lemma 6. In Algorithm 1, if we set the constraint C = {x E [0, Enev, To S 1, Assumption 2 holds, we have that, for any I. E (7] and E N, we have that, for any E [T] and i E N, X1,5 E C and y1, E C.
1, Vi E NN3 and
know that X1.5 E for any E N.. Moreover, due to Assumption 2 and Line 8, we also can infer Yı,i = EjEMU WijXi,
Proof. We prove this lemma by induction. At first, from the Line 2 in Algorithm
for any i N. For any 1 < T. we assume x E C and y1, E C for any E N. Then from the Line 12 Algorithm we know Eaev, [x++1,]e = Eoev, [Yr,sa < for any j * and i E N₁. Furthermore, Line 13 implies that [x+t1s]y, is the projection over the constraint nh by S so Eaey, [x I we can conclude that X E C. Due to Assumption 2, we can further show Yt+1,i E C.
L
With Lemma 6, we integrate the probability update procedures for actions i E V, and those not in V, within Algorithm 1, i.e, Lines 12-13.
20

---

Published as a conference paper at ICLR 2025
Lemma 7. In Algorithm 1, if we set the constraint C = fx [0.1]" Exen, to I 1, E M2 and Assumption 1 and 2 hold,we we have that, for any E [T] and N,
Xt+1. arg min
(- O lv, x) + T
D
xEC
where @ denotes the coordinate-wist multiplication, te i-th element of vector x S is 3e and 1y, denotes a n-dimensional vector where the entries at V; is equal to and all others are
Proof. Firstly, we define the solution of the problem minxed (- (VPFF(( 2 Iv,x)
- L (x,, as o" E [0, 1] Due to Assumption 1,
- (- (V (xx,)) (x.,)) O 1n, x) + -DD (x, vt.))
o" arg min xEC
arg min
(- ([V /2 bv. (xlv,)
1
D s.n. (xx2u (xsddve + 1 DD (vddmr)))dd
XEC
T)e
As result, we can conclude that
1 (- (IVFFF b) + Do.ni (yaulv)):
lo'lv.-
arg min Exev, $1
m
(Pamile (Mnlmr))) (Yaluwe (Note that Ye, C (See lemma 6))
[o']vrn arg min Eocy, S.IIEENN
(14)
where b E 1) and z E [0, 1|m-", From the (q.(14) and Lines 12-13 in Algorithm 1, we get the o" =X+11;-
In the following part, define some commonly used symbols for the proof of Theorem 3:
x, EN
Xt,
X xcate
= (x, :x,N]] E TR
N
EM Nt,
Y: =
yeate
Vy R
N
Fri X Vt,i
rt reate
= Fe.
R
With these symbols, we can verify that Lemma 8. If we set the constraint C = {x E [0, 1] Enev, 2n S 1, e N) and Assumption and 5 hold, have that
B( = B(11xe+1, - yr.il) < Gmn-
Proof. According Lemma we have that
Xt+ arg min (- (VF)(xx)) O 1v,,) 1 Do(x. xEC
1
where C = (x E [0, 1|": Eney, Ha S1,ViEN).
From the Lemma 5, we have
(x - X, VF (xx.)) @ 1x) S Po(xxyr.d Dx x(+1,) -D -Do(x (15)
for any x E C. If we set x = yt.! ! in (15), we have that
7c( Vt., &ET (xx1) @ 1v:) 2 Do X1+1.)) + (x 2 || yeall where the final inequality follows from the 1-strongly convex of d.
From the Young inequality, we have that (e(x111 - Yt. V (x).) @ 1y S [xtty-yaall
Il FF 101v such that [[|xx41, ye,ill) < B([ VF (x.)) ① 1v)ll)) S n. from the
2 Assumption 5.
Note that prove yt,, C in Lemma
21

---

Published as a conference paper at ICLR 2025
With this Lemma 8, we next derive upper bound about the deviation between X V4+1, and the average Xt+1- Lemma 9. Under the Assumption 2 and 5, we have that, for any E [T'] and E N,
B([ x++1ll)
3 G
B(1 & Σ VN
where (axx()>(W))lIAA is the second largest magnitude of the eigenvalues of the weight matrix W.
Proof. From the definition of re,s we can conclude that
X Ft.i + Yr,i
Fr, +
WiyXt.ji
(16)
jEACU()]
where the final equality follows from Line 8 in Algorithm 1. As result, from the Eq,(16), we can show that
cate
+ (W & 1n)xxate
x+1
W In) cate
(17)
( @ In ratte
where the symbol & denotes the Kronecker product.
we also define xpnte
[xe; Ny.
:.: E R and from the (q.( we also have that
1
1
x
=
IN
xi+1
cole
N
(18)
IN
Σ
3 I,
peate
N
Then, from the (1.(17) and (18)) we have that, for any i EN
X 8,+1
Σ jENiU()
(W' N rz.j-
(19)
(19) indicates that
E (1|x++1,5
8(+1l1) =E
Σ
Σ
([W
1is
1 Fr.j
N
JEAUUE
< E
Σ Σ
(
N |KTTT
r= JEACU((
W by
N G < Σ VN3
JEAGU(}
where the second inequality comes from Lemma 8 and the final inequality follows from EjeNuug [[W - + 3 (See Proposition I in (Nedic & Ozdaglar, 2009)), Due to Vet1.* EjeMurg W1yX+115 we also can have B(Ily - ()+ S EjeNuur ([Ix([]
x441l) < Σt= VN3--T
22

---

Published as a conference paper at ICLR 2025
Lemma 10. Consider our proposed Algorithm 1, if Assumption 1,2.3,5 hold and each set function fi is monotone submodular with curvature for any E [T], then we can conclude that,
(i 1=1
Σ B ((((X))
t MT)
- R. (DD( - (x x(110) NG U
(3G + LDG)
ΣΣ 1=1==
NàB
MEN
where x is the optimal solution of (3.(3) and D = supx.yec ||x x- yll where C = {x E 10,
Eaer, Ta I 1, Vi EV).
Proof. From the (4) in Theorem 2, we have that
1 e-e
Fi(xt) (x())) - (VF) (x) x - xx1)
(VF7(X)) Σ (FF)()) 3 lv.)). xx))
iEN
VP. (x,,)) 3 1y - x1,i)
(20)
EN
Σ (VF (x+,) @ Iy. X1,3 x1),
EN
where O denotes the coordinate- wise multiplication, the i-th element of vector x @ y is a.y, and 1y denotes a n-dimensional vector where the entries at V; is equal to and all others are 0.
For I. have
(F)((x)) - v (x,,)) 3 1v, xi :xi x1)
SEN
V17 Σ (x 3 1v:) |xt xell
<
iEN
$ ||x x Σ
[I[VF] )x, - (x
< ||] x
Σ
(IVF
(x(()))))..
(21)
IEN
$ |
x Σ
[L||x,- -xxol)
VEN
LDD Σ
|| xx,iil)
iEN
< LDG Σ
N B Dr
where the fourth inequality follows from Assumption 5; the fifth comes from supx |x - y/l and the final inequality from Lemma 9,
For c from Assumption and Lemma 9, we have,
E
(x,,) @ Iy, X1, xz) SG IEN
Σ E
[|xx0
x11ss
x11)
>>
GN -t nT. (22)
iEN
23

---

Published as a conference paper at ICLR 2025
As for ② we have,
E
(X..))
1x - xxx1))
EN
E
(x(((x)))) C 1, - xx,)) (xx,))
EN
E
E
( - xx,)) 1x4.))
EN
(x(,)) @ x x++1,))
(23)
EN
(VF, (x - ya.))
IEN
(VP, o 11. xx.)) -x.))
iN
For ④ from Lemma 7, we know that
- D (- (VFF( 1v; x)
Xt+1, arg min
XEC
11t
So, from the Lemma 5, we can show that Me (x x, V (x..) @ ly;) S (x,x, - x(+1,)))) Do(x)t1as (24)
for any E If we set x x (24(2 we have
+ S Σ
vts. Do(x xL+1,) (o(xEt1.))).))
SEN
(25)
Σ
E
(xx(t)) - (x xe+1.))
- ΣE E
[x++1 - ycall
21
AEN
iEN
For 2 by Young's 's inequality, we have that
Σ
E
[x++1J - Ncall
+
Σ
T1
V
P. (x..) 8 1vill)).
21).
2
iEN
iEN
(26)
X
Yeall
N..
<
Σ
E
+
21le
VEV
For ④ we have that,
V @ 11.11_1xx,. yr,il Xt.i Xx.., Vi Nr)
SEN
(E(IIVE (xx.)))))
Σ E([|x X + E(Ile,. x(ll) -x(l))
(27)
2
GN 3 nr-
Merging
and (27) into (2.), we have that
(x(x)) - Fx(x)) S (VF)((x)) x3
x,)
Do.)) - (x( x(41,)) + N.
I (3G LD)
Σ N イ +
2
iEN
As result, get the result in Lemma 10.
24

---

Published as a conference paper at ICLR 2025
Next, we prove an upper bound of Ei= Eien 1 (D(
Dx( x(+1,)) that is,
Lemma 11. Assumption 1-5 hold, we have that
T EE
- Do (xi (x1xx)
NR
Σ
T
KN
xi+1
xi lls
1=1 -ENEN! th
1/T+1
11++1
1=1
where xi is the optimal solution of (q, R2= = supxyyEC Do((, y), and C is the constraint set in (3)
Proof.
T ΣΣ
B(Do(x), - Do(x), x(11.))
EEN
((Do(x))
E(Do(x(+1)
m++1
T
D Do(xi - Ne.1.)))))))
1h+1
1=1
IEN
( J441,)
Po(xi,xx1111)
M1+1
1=1 iEA
T
1 E Dis (xt,, (x (xt,xi))))
(D&(
M1+1
1=1 IEN
Firstly, we have Os
N
and 2 E 7:11
xit1 xill from Assumption 4.
Then, from the separate convexity, we have
LE(D (C(DD(xi - Pa(xxxxxx1.))
Th+1
IEN
(DDolxi, E
wifXe+1.)) D Do(xt, Dolxi.x)41i)) JEN(UH)
1/++1
1=1 iEN
E
Σ
E
(WID)(((, - E DD(xx,
1=1
11t11
iEN VENjENiu
jENiUfi)
iEN
E
Σ
(xx - Σ (D(oss)(4H1i))
M1+1
iEN
;ENiU())
SEN
0,
where the first inequality follows from Assumption 3, and the third inequality is due to waj Wii.
Moreover, we have 4 < NR --1)) 4 We finally get
NR
T
KN M
E (Doo st.s) - Dxx ,x+1,))) 5
- x;
7/+11
VEN
25

---

Published as a conference paper at ICLR 2025
As result, prove the following Lemma:
Lemma 12. If Assumption 1-5 hold and each set function ft is monotone submodular with curvature for any E [T), then
F((x))
F
B
Σ
Xt,
Iv:)
[m
IEN
t
NR
T
KN
NG T 2
S (4G+LDG
Σ
Σ
N
3
17
[x
x;1l
+ Σ
7h
+++1
7t+1
Proof. From the Lemma 10 and Lemma 11, we have that
T
T
1 1-e
Fx(x))
Σ
E
(F((())))
-
1=1
NR
T KN
NG T
S (3G + LDG)
Σ
N 3 )m
+ Σ X x +
Σ 1/-
1I+1
1=1 M|++1
2
(=1==1
1=1
From the Assumption 5, we also can show that [F((x)- Fy(y) S G for any 1. E [T] such that
we have |Fe( EiEN X1,5 @ Iv.) Fx(x,)) S G|) Σ EiEN Xt,i ① 1v. xxll S S ||x,, x |l S
G Σ 1
N Br mn)) Thus, we have that
F((x))
Σ
Fi Σ
X1,i 1v:)
iEN
T
F((x7)
Σ
13 (((()))
+ +1>+
IE
F1
Σ
0 1v:) - Fi((x))
1=1
t=1
iEN
T
t
NR²
T
KN
NG
T
$ (4G+ LDG)
3
+
||x|+1
- xx111 +
?t
MT+1
Mh+1
2
From Calinescu et al. (2011) 1); Chekuri et al. (2014), we know that the optimal value of continuous problem (3) is equal to the optimal value of the corresponding discrete submodular maximization Eq)(1), so we can set x == 14; where A; is the maximizer of (1).
Next, we show a relationship between (Je UieN {or,:)) and E (F. Xe,i O lv:)). Lemma 13. If the function fe is monotone submodular and on is the action taken by the agent i E N at time t, then we have
B(fc (acit) B (((( Σ xx, x 1lv))
iEN
Proof. We prove this lemma by induction on N = WV. When N for any LE [T], we have that
B(F((x,,)) S ((F.(
X1,1
) 5 E
R~ 1711 (I(())
1x,
< E
R~ الln
Σ fi(a))
acR.
(28)
Ix,ale
fe(
1xx
NE
B(f((a))))
where the first inequality follows from the monotonicity of f. and [|x,,1 |h S 1; the second one from the submodularity of and Line 5-6 in Algorithm 1.
26

---

Published as a conference paper at ICLR 2025
Now let N > 1. For any R V, we denote R1 R \\ Vy and 8; Eaen. (xe for any E N. Then, we have that
Fe Σ x o 1v:) - F
Fi
01v.)) = E RR-EieN 410 (F((R))
7 Myd oln (F((RA) + (((R) (i(R1))
8,
VEN
iEN
ByR Bu EieN
=BR~EieN 7f
Hes ol, (f((R) - f((R1)) +BRNDNEN
H0,, (Ii(Ri))
of
E EREN M1i (II(R) - SACRII/RR)) + B BRNEENN to Hoou, (I((R))
$ ER olv, (Re u - (.(RI) -((RII))(())))R.)) + BRAINEN mi oiv,,, (fi(Ri))
-RR-IINN mionn (Fi(Ra U (axx)))
as
S B (ff((UEEN) fal,:)). <B(Fi
where the first inequality follows from the monotonicity of ft and s, < 1 and we get the second inequality follows from repeating the proof in (2.) because ((,,))((R))) a submodular function over VN for any fixed R S V and 0r,N selected from the set V/v according [x, xlvx
( Vx)
SN
Merging Lemma 13 into Lemma 12, we can get that
T
T
f((At)
Σ
TR
ViEE (a.i)))
T
NR
KN
KN
NG
s (4G + LDG)
Σ
3
Σ
| A:4.
1A; + 2 [-1
Σ Th-
+/++1
1=1 M
[=1
We know that all norms in miite-dimeniional real space are equivalent (Lax, 2014; Zhao & Lai, 2024), so ||||| S C2 [/||x|11. Finally, we can verify the (8) in Theorem 3, that is,
f((A)) Σ E fo (ULEN (alst))
NR 1/++1
T KNC₂
NG T 2
(4G LDG)
gr (T))
44114 +
Σ
M6+1
E PROOF OF THEOREM 4
In this section, we prove the Theorem 4.
Proof. When g(x) log(s), we know that, for any b,y (0, 1)m
D Dy.m (b. y) Σ (b. log(
bi
Σ
b
Σ
m
Vi-
T=1
T=1
Next, we consider the Lagrangian function, for any fixed y, E 10,
m
m
be log (2)) - Σ
m
m
f/ + X m
L(b, A)
Σ zabe
+ Σ
1).
Vi
1=1
Then, we have that
@L(b, A)
bi
+ log
+ X, Vi E [m].
(29)
ab;
y/
27

---

Published as a conference paper at ICLR 2025
Setting all equations in (29) O, get b; y, exp(-22) exp(-X) for any E [m] such that [()) - - y/ exp(-2i) exp(-A) - x. When Σ y/ exp(-zi) S 1,
L(O) maxx20 L(A) such that the optimal solution of = yi exe((=22 Similarly, when E (xpcx((22i)) 1,
m
I log Σ
us expl exp(=2:)))
max L(A),
A20
so bj y/ exp(-=i))xp log
Eim (yi (xx((==)))
exp(=x)
Bs expl =z))
PROOF OF THEOREM 5
In this section, we present the proof of Theorem 5. Specially, we assume || is I norm in this section. Like the Appendix D, we can show that
Lemma 14. In Algorithm 2, if we set the constraint C fx E [0, Eaev, Fa S 1, Vi N}
and Assumption 2 holds,w we have that, for any [I'] and E N,, we have that, for any [T] and i E N, X1,5 E C and Yt,i E C.
Lemma 15. In Algorithm 2, if we set the constraint C = fx E 1]m Emen Ta S 1, EN and Assumption I and 2 hold, we have that, for any E [T] and i E EN
X++1,1 arg min (- (-F 1v, x) N
1
XEC
where @ denotes the coordinate-vee multiplication, the i-th element of vector x @ is T;Y,, and 1v, denotes neddimensional vector where the entries at V; is equal to 1 and all others are 0.
Lemma 16. In Algorithm 2, if we the constraint C {x [0, Eaer, Ja S 1, 1i E N and Assumption and 5 hold, we have that
B(IIr,,)l1)) = B(Ix++11 Ve,alli) S Gm-
Moreover, also define the following new symbols for Algorithm 2:
8, 1i=1
Xt,
[x Xt,2 XX,]]] R xeate
N
EN
y.
Yos
yeate
We,1i Vr................... :y,v]] RUnN
N
X1,5
X, 1i=1
Scote
[ X
x R
Fe, X.+
Ye.is
reate
TCN] E B
Then, we also can show that
Lemma 17. In Algorithm 2, under the Assumption 1, 2 and 5, we have that, for any E [T] and i TEM N.
E([[x*41, - xt1llh N 3' (1 21-2)--
B(( - 8c41lli) <
VN (1-2)4+1-7
1 G G +D,
where = (ax())((W)),,A is the second largest magnitude of the eigenvalues of the weight matrix W and D suPx,yec [x x yll where C = (x 1]" Eaer, Ta & 1, E N).
[WI..
28

---

Published as a conference paper at ICLR 2025
Proof. From the definition of re, and &e, we can conclude that
X1+1. = Fe,s Nt,i re,
Wey
JENiU(})
(30)
(1 (1-7)xx0, 2 11 n
Fr,
Wij
JEM
where the final equality follows from step Algorithm 2. As result, from the E30, we can show that
cate ++
rraae (W & In) (..((1)))) (1)))xffate
+ 2
InN
n
peate +(1 - ( In)xpate ! InN
(31)
(W peate
+ 1nv
7(1
-
7) -- (W @ In r
cate
IaN-
we define xcale
[R:; &tj.... X:] Ru'N and from the Eq.(31), we also have that
1N1
x+1
2
IN)xf11
cate
(32)
1 1
-1-
In
rr cate
1,N.
N
n
Then, from the (31) and (32,, we have that, for any i E N,
X - Σ Σ (1 (1-2)
|r
(33)
JENU(()
E33) indicates that
B([|x+41,1 3141l12)=B( Σ Σ (1- TB 1
N rralll))
r=ljENuf1)
< E
Σ
(1-7
J6 N ||r lI)
== JENUU
Σ
|W
(1 T
bi N
JENUU()
VN3--T(1- -1-7)"-- G.
where the second inequality comes from Lemma 16 and the final inequality follows from
Ejenoug [[W'-] b VN Due y Ejen Wij also can
29

---

Published as a conference paper at ICLR 2025
have
E((Ily++1, - -8441112) -
Σ
wi, BlI X(t1ll1)
JEMiU((
Σ
Why (n)
-1 >)xxes + n
1n) x(+1l11)
JENLUfI)
(1-7)
Σ
wi,B(((Xx,, - -8422111 +7
Σ
B(l
B(l
1 1, 8 &111l11)
jEN(u(s}
JEN.Uff)
(1-))t11) G +
Like the Lemma 10, we can present a similar lemma for Algorithm 2, that is, Lemma 18. Consider our proposed Algorithm 2, if Assumption 1,2.3,5 hold and each set function fe monotone submodular with curvature for any E [T], then we can conclude that,
T
F(xx))
Σ
E E(F((()))
S (2G LD)
ΣΣ
Σ
[xx xcl11)
T
T
NG T
lyy. - xill1) + ΣΣ B(DKLLX (t,)) - DxL(x", x(+1,)) -DL((X(x++1))) +
Σ
m
2 1=1
t=liEN
where x is the optimal solution of (3)(3) and D = supx.yEc ||x x|x yll where C = (x E 10,
Eaer, Ta I 1, 1, N).
Then, we derive an upper bound for Et EiEN L B - Dxi(Xt, Xet1,)) Xett))) i.e.
Lemma 19. If Asssupttio 1,2,3 and 5 hold, we have that
T
ΣΣ
Σ
E
((DKL(x),NE)) DKL(XX X+t1,s)
1
iEN
T
E
Σ b
log
(Re+1.bls) yr,slj
+
Σ 5=1
(Dredls - (xxt1ab))
+
T
2N
The
m1
1=
EEN
Proof. From Nesterov (2013), we know that, for any two vector x, y E RT
[x] [vly
(x
[xl log
Σ
[x]
+
[yl,
1=1
j=1
/=1
Thus, we can show that
(E(DIIXxi
- PXI(X x(+1,))
(x
Th
TEA
ΣΣНE E
Σ XxL, log
Σ
(Dredls - (xe41ab))
+
iEN
1=1
ΣΣН
Σ |x
log
Σ
{x y log
[
Σ
n
(Drell - (Battidd))
Rett, )
t
30

---

Published as a conference paper at ICLR 2025
From Line 7 in Algorithm 2, we know that [8c+1,ls = (1 - 7) + 7. So if [x+11,1l
[x+1,aly S 18l or log( 3.11. S O. As for [x+1,,1] > 1 and 7 S 2/2
Xx+1,115 ) = log(
(1 - 7) [x + I )= = log (1+ 7(xx - 1)
[x1+1,11
log(
X(+1,115
(1 7)(x +
7(xx++1,15 3)
S (1 - 7) (x+t,1o
S 2%
where the final inequality follows from [x++1,3] - s [x++1,1] $ 2(1 - 7)1x+ S $2((1-
xx + + 7)-
Then, we have
ΣΣ
1
E ((DLL(Xi,Nu.) DKL(x; x(t1,))
ElieN T
T
E
log(
(et1ills [yc,ol)
+
Σ
(Iyedls - -betaab))
+
T Σ
2224
EliEN
1=1 m
Lemma 20. If Assumptiio 1,2,3 and hold, we have that
T ΣΣ t= 1EE
(etzolls) Iverels
N
log(
T
N (og( 2
E
Σ
xi log(
||x
x;]111.
1h
7/
11+1
1=1
Proof.
E
Eix Ix log(
[ye.ili
IEN
[yrels 1)
12
|x log(
[x log(
Wl
iEN
1=1
j=1
1
E
[ log(
E
xx als log(
T/t
yr,lh
T/++1
TEA
E
x
log
[ye4
E
xil log
lye+1.ely"
IEN
j=1 l
xx y log
[xi,,
log(
lye41.13
M++1
IEN
j=1
j=1
1
IE
x b
log
T/t11
IEN
j=1
31

---

Published as a conference paper at ICLR 2025
Firstly, from the convexity of function (og(H), we have
T
11
(vet2,11b)) )) - E
3
=
E
L log(
[x; log(
88411.11
7
1=1
ENN
j=1
5=1
T
11
xil log(
Σ IKEAUURD wise (ettl 1) F
[x]], log(
Mi+1
iEN
j=1
[& 1) E
E
Wik log(
[ log(
18
Mc+1
1=1
iEN
kENLUE
Σ
Wki)
E
> xxl log(
8 1) E Σ [x log(
M++1
t=l
iEN
kENiu(i)
= O.
Then, for (, we can show that
N (olgg("))
Σ VEN 7
E
[xil,
log(
[yr.ll )) s
1/2
j=1
where the final inequality follows from [yi,sl 2 2 such that log( ( S log(?) and Σ}=1(x]] S
N.
As for ② we can have that
E
[x lls log(
[ye+1.0b6 )) E
1 xx, log( Net1o1s 1)
7e+1
KEN
T
1
E
(xc+ - [x]]b log( beetials
ne+1
1=1
VEN
1
T
N log(?? 2)
|x]_
x1]111
M1+1
where the final inequality follows from log( byet) < (gg()). (- - ) We finally get
Moreover, we have I
N2 log(
(
ΣΣ IEN
n Σ 1=1
N2 \o (2)
T N log(?)
E
xxl, log(
<
| x;]l
ye.els
11t
71-11
Next, from Line 13-18 in Algorithm 2, we know that, for any E N, when
Eaer,
(yrsla (xp(nx
S 1, we can have [xe+1,]e [ye,la- As for
Eeen, [ye.]la (PXxx)) > 1, we have Eaev, [x+1,,la = 1 such that ΣØ=1 (Drsals-
(x+t1,l)) = EuEv, S As a result, we can conclude that
ΣΣ iE Th
Σ [vr.ds (xxetaab) s
32

---

Published as a conference paper at ICLR 2025
Finally, get these result
(x(
Σ E Fi(())) (3G² I.G))
ΣE
No gr
T(1
t=1
22 log(
Nogg(
2N
NG
G.D++
xx++1 - -xill +
1/--
11+1
7
1
Like Lemma 12, we also can verify that Lemma 21. In Algorithm 2, if Assumption 1,2,3,5 hold and each set function is monotone submodular with curvature e for any & E (T). then
T
((()))
EB(M
Fr
Σ IEN
Xt,i ① I2:)) S (1C²
LDG)
Σ N (1-)) --)² + GzD
1=1
N2 (og(
log 2)
T
2N 7
NG
|x
x
+
77+1
M1+1
From Calinescu al. (2011); Chekuri al. (2014), know that the optimal value of continuous problem (3) is equal to the optimal value of the corresponding discrete submodular maximization (I), we can set x == 1A; where A the maximizer of (I.
Next, like Lemma 13, we also can show relationship between TEJee( UseN {at,))) and ((F EiEN X1,, O lv.). Lemma 22. If the function fe is monotone submodular and ot is the action taken via the agent i E N at time t, then we have
B(fi( (arit)) 2 (F( Σ x 2 1w)).
iEN
Finally, we get
T Σ
T
T
f((A))
Σ
E Fi USEN (arit)) s (4G² + LDG)
N 8t (1 - -)) + +GDD
N 1o
N log(?)) 12)
2N
NG
|x|1|
x;
?t
71+1
[=1
33


Reviews:
[{"review_id": "iJ1BKqWd5s", "reviewer": "Reviewer_H5Ct", "summary": "The author(s) propose a continuous surrogate approximation of multi-agent submodular maximization problems and solve via mirror ascent approach to (i) achieve tight approximation, and (ii) reduce communication density among agents. The proposed approach is evaluated in multi-robot target tracking examples.", "questions": "1. Line 157: The assumption that different agents must have mutually disjoint action sets looks odd to me. Taking multi-target tracking task as an example, wouldn’t different agents totally have access to execute the same action?\n2. Multi-linear extension: I would appreciate that if the author(s) could speak more about how good the continuous relaxation is compared to the original submodular maximization problem and under which conditions. Right now, the presentation just takes this relaxation for granted.\n3. In Algorithm 1, what enables the relaxed requirement of a sparse communication graph stated in the contribution statement? Is this part of the author(s) contribution or something enabled by the fact of using existing online mirror ascent methods? A related point is that the author(s) claim that the novelty of their proposed non-oblivious surrogate function for the multi-linear extension objective is the curvature information. Is accounting for the curvature information in non-oblivious surrogate approximation of multi-linear extension a well-recognized challenge in the literature? \n4. The requirement that the objective function needs to be monotone submodular seems to be strong. Can the author(s) elaborate on how restrictive this is?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The contribution is novel and sound, and the theoretical results are strong.  \n2. The paper is well presented in general. The authors clearly motivated challenges existing in the literature and this work’s objectives.\n3. The efficacy of the proposed approach is validated using sufficient amount of empirical evidence.", "weaknesses": "1. Problem formulation\n- I think the author(s) should list the assumptions made in this section explicitly, such as those in lines 177 and 159.\n- I think this section is a bit unconnected with the motivating example. I would appreciate a bit more introduction about why and how problems like multi-agent tracking can be formulated as online submodular maximization problems. For example, I am a bit confused here why the objective function is revealed after agents make decisions and why the objective function is guaranteed to be submodular?\n2. Experiments:\n- Is all the targets being strictly homogeneous in type a requirement from the algorithm? What if different targets are of different types?\n3. Contribution: this work builds upon a few existing methods in the literature. The novelty of the approaches can be better specified; cf. Question 3.\n4. While submodular optimization has a variety of applications, the problem studied in this work seems to be more specific to robotics applications. I think is relatively less relevant to this venue. \n5. Other minor points:\n- Line 70: “Furthermore” – hyperlink is redundant\n- Figure 3: It can be shown in the caption or in the figure that 3 rows represent different target types. Right now, it’s a bit hidden in the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9N7jq0rwKw", "reviewer": "Reviewer_WfEW", "summary": "This work proposes two algorithms MA-OSMA and MA-OSEA that collaboratively solve an online, multi-agent submodular optimization problem. Both algorithms produce $\\left(\\frac{1-e^{-c}}{c} \\right)$ sub-optimal solutions in contrast to $\\frac{1}{1+c}$ approximate solutions produced by state of the art methods. They also achieve a regret bound of $\\tilde O\\left( \\sqrt\\frac{C_TT}{1-\\beta} \\right)$. The MA-OSMA algorithm requires a costly projection step, this is then removed by using a KL divergence and \"mixing uniform distribution\" argument in MA-OESA. The method is then illustrated via numerical simulations.", "questions": "- The paper lacks any discussion of how the performance of the two algorithms differ beyond what is in Table 1. How costly is the projection step? How do the two methods differ beyond a factor of $\\log T$ regret?\n- Does the spectral information show up anywhere in the regret bound of the OSG algorithm? Likewise, do any of the connection graph properties appear in the derivation of the approximation ratio in MA-OSMA or MA-OSEA. It seems like they need to appear somewhere and here they appear in the regret bound - was this an active choice? It seems like there is trade-off between approximation ratio and Regret.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper addresses an interesting and relevant problem - motivated by multi-agent robotic problems. The main contributions of the paper are:\n- Improving on the state of the art performance bounds of the OSG algorithm by approving the approximation quality to $\\frac{1-e^{-c}}{c}$ where $c$ encodes the curvature of the problem.\n- The second algorithm, MA-OESA, removes the need for a projection step which allegedly is computationally expensive.", "weaknesses": "I believe there are several areas where this paper can be improved - mostly in the area of presentation and clarity of exposition.\n\n- In section 2.1 the authors state that \"each agent $i$ within $\\mathcal N$ is equipped with a unique and discrete set of actions\". But in the numerical section this seems to be contradicted as the simulation considers the case where each agent has exactly the same choices: up, down, left, right, diagonal etc. Are they unique or identical?!\n\n- In the formulation (1), what is the set $\\mathcal A$? Is it just a subset of $\\mathcal V$?\n\n- In terms of motivation, it is not clear why the algorithm from Vondrak or Bian et al, cannot be used to achieve the $\\frac{1-e^{-c}}{c}$ bound. \n\n- It's a bit weird to claim that your own algorithm \"skillfully harnesses\" something. I suggest removing this from the abstract and body.\n\n- The explanation of how to circumvent the fact that KL-divergence is not Lipschitz is not clear at all. The text is full of jargon. What does \"mixing a uniform distribution\" mean? Neither Theorem 5 nor remark 9 seem to have any parameters from uniform distribution. Please provide some intuition about what is going on here.\n\n\n- The OSG method should be described and compared to MA-OSMA and MA-OESA in a more direct way. What is the main difference between the algorithms, how do the necessary assumptions differ etc. Why is it that it only achieves $\\frac{1}{1+c}$-accurate solutions? This will strengthen the numerical section where it is shown in simulations that the proposed methods out-perform it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F8ONj1KlYA", "reviewer": "Reviewer_NhDa", "summary": "This paper studies a multi-agent online submodular maximization problem (MA-OSM). In each step, each agent independently selects a decision from a unique decision set, queries local marginal gains of an underlying submodular function, and exchanges information with neighboring agents. By leveraging a novel surrogate function approach for the multi-linear extension of submodular functions, the paper proposes an online algorithm that achieves a tight approximation ratio relative to the offline solution under a connected communication graph, with a regret bound of $O\\left(\\sqrt{\\frac{C_T T}{1 - \\beta}}\\right)$, where $C_T$ is the deviation of the maximizer sequence and $\\beta$ is the spectral gap of the network. The paper further develops a projection-free variant of the first algorithm, and attains the same approximation ratio with a slight loss in the regret guarantee. Numerical results effectively illustrate the performance of the proposed algorithms compared to prior work, which has sub-optimal approximation ratios.", "questions": "- Could you provide formal comments on the tightness of the communication complexity for both proposed algorithms?\n- Since the proposed algorithms can be viewed as an online implementation of offline approximation algorithms, it would be beneficial to provide a formal comparison with the work of [Razazadeh and Kia 2023] in the main paper. \n- The regret guarantee depends on $C_T$, the deviation of the maximizer sequence. Please specify how $C_T$ varies and impacts the regret guarantee. \n- what does the subscript $d$ denote in the regret definition?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "-  The proposed algorithms improve the approximation ratio of prior work from $\\frac{1}{1+c}$ to the tight ratio $\\frac{1-e^{-c}}{c}$. Additionally, this improvement is achieved with limited feedback requirements, rather than needing a complete communication graph.\n\n- The use of surrogate functions to overcome limitations related to stationary points in the original multi-linear extension is both effective and inspiring. \n\n- The paper is well presented, with a coherent flow, clear contributions, and strong results.", "weaknesses": "- There is some ambiguity regarding the communication complexity of the proposed algorithms. Although they attain a tight approximation ratio, it is unclear if the communication complexity is also tight. Based on the title, the paper seems to claim tight communication efficiency; however, this aspect is not clearly addressed. Additionally, the paper appears to assume a static communication graph, which may not apply to applications like multi-target tracking as discussed in the numerical section.\n\n- In the proposed algorithm, each agent is required to query the local marginal gain oracle multiple times. While this is common in prior work, it is not evident if/how such an oracle would exist in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BTYMh2lOwV", "reviewer": "Reviewer_qEPy", "summary": "This paper proposes an algorithm for online multi-agent submodular optimization problem, which is then extended to a projection-free variant. The main contribution is that the proposed algorithm relaxes the complete graph assumption and achieves tighter approximation ratio, as compared to the SOTA algorithm.", "questions": "1. Can the authors comment on how to select $c$ in practice?\n2. The algorithm introduces a set of hyperparameters such as step size $\\eta_t$, mixing parameter, and the weight matrix. Can the authors comment on how to select these hyperparameters?\n3. In figure 3, I can understand the utility column. But can the authors elaborate on the other two columns and why are they also interesting?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well-written. The proposed algorithm removes the limitation of complete graph assumption as compared to the SOTA algorithm. It also achieves a tighter approximation ratio as compared to the SOTA algorithm.", "weaknesses": "1. The execution of the algorithm relies on the curvature parameter $c$. However, this parameter may be unknown beforehand. \n2. In line 11 of the Alg. 1 and line 12 of the Alg. 2, the objective function needs to be evaluated for 2$\\sum_i|\\mathcal{V}_i|$ times. This can be very inefficient when the function $f_t$ is expensive to evaluate or the number of actions is large.  \n3. The experimental evaluation part is relatively weaker than the theoretical contribution. In the experiments, the paper did not verify the theoretical result, that is, some figure showing the ratio between empirical objective value and the optimal value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VOBVAJQde4", "reviewer": "Reviewer_e6bZ", "summary": "This paper presents two algorithms for solving the multi-agent online submodular maximization problem, accompanied with a convergence analysis for each. Both algorithms achieve near-optimal approximation ratio while requiring less restrictive assumptions about the graph structure (connected instead of complete). Notably, the second algorithm further gets rid of the projection step by using a specific Bergman divergence (KL divergence) within the mirror descent framework. The effectiveness of the proposed algorithms is also validated through a simulated multi-target tracking task.", "questions": "1. The comparison of prior work can be better clarified. For now, the contribution part in the introduction doesn't provide a clear picture of how the improvements are made and why they are novel.\n2. The paper would benefit from more detailed insights into improvements and associated trade-offs? E.g. regarding the connectivity of the graph, while the prior work assume a complete graph, but they only require a directed acyclic graph (as indicated in Figure 1). In contrast, the completeness is no longer needed but the edges need to be undirected. Why is this trade-off beneficial? Another similar question comes from the regret bound: it is degrading from $\\tilde{\\mathcal{O}}(\\sqrt{C_T*T})$ to $\\mathcal{O}(\\sqrt{C_T * T/(1-\\beta)})$. Although the simulations suggest improved performance, a theoretical explanation of why this compromise in the regret bound is reasonable would be valuable. Could you provide more insights?\n3. Could you elaborate on how to sample from different actions under the constraint \"$\\sum_{a\\in\\mathcal{V}_i}x_a\\leq 1$\" without requiring normalization?\n4. Can you clarify the novelty of Theorem 2 compared to Corollary 7 in Zhang et al. 2024 in Remark 3? The results look very similar, apart from the difference in curvature.\n5. Can you explain more on the difference between Distributed-CG and this paper? The two seem closely related but Distributed-CG is only mentioned in the appendix.\n6. Line 1402: Can you provide a more detailed explanation of why the first inequality follows from the monotonicity of $f_t$? It is applied several time but the connection between the monotonicity of $F$ and monotonicity of $f$ is not clear \n7. Does this paper offer any novel insights into optimization, beyond those already established in the literature?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper's contributions and the structure are clearly delivered, with additional remarks are provided to enhance understanding. The appendix is well-organized and easy to read.\n2. The contributions are interesting and compelling. They advance prior work to a near-optimal approximation ration and substantially relaxing the assumptions regarding graph connectivity.", "weaknesses": "1. Overall, the writing could be improved. This paper is heavy on notations & definitions, and the authors should be more careful when introducing definitions/abbreviations/notations. Specific examples are listed below:\n\n- Line 16: What do OSG, MA-OSMA, MA-OSEA stand for? The contribution \"...skilfully (typo) harnessing the KL divergence...\" is too technical and detailed for an abstract. A more high-level intuition is expected at this stage.\n\n- Line 49: The abbreviation MA-OSM is introduced twice.\n\n- Line 138: Typo \"lowercase.\"\n\n- \"Notations\" paragraph: On Line 142, avoid starting a sentence with math notations. The lowercase \"s\" is used without an explicit definition.\n\n- Line 154: \"MA-OSM\" is introduced again.\n\n- Line 225: Consider using a different notation than \"F\" for clarity.\n\n- Theorem 2: Is the phrase \"for any x,y\" missing?\n\n- Algorithm 1: Using $\\eta_t$ suggests an adaptive step size, but it is set to a constant in Remark 8.\n\n- Assumption 5: Is $\\mathbb{E}[\\tilde{\\nabla}F_t^s(x)\\mid x]=\\nabla F_t^s(x)$ derived from the estimation procedure, or is it an assumption? Constant $G$ is not defined.\n\n- Theorem 5: notation $\\gamma$ should be redefined, as its first definition occurs early in the paper and the other one in Algorithm 2 appears only afterwards, which is shown later in the paper. Consider using a different set of parameters than $C_1,C_2,C_3$, which are already used in Theorem 3.\n\n- Line 992: typo \"y\"->\"x\"\n\n- Line 1058: \"argmin\"?\n\n- Line 1100: is $=[y_{t,i}]_{\\mathcal{V}\\textbackslash \\mathcal{V}_i}$ a typo?\n\n- Line 1126: Typo - $x$ should be $y_{t,i}$ in the first term on RHS.\n\n- Line 1029+1030: Typo $F^A$ should be $F^s$.\n\n- Line 1183: Can you provide more specific references to the results in Nedic&Ozdaglar, 2009 and Horn&Johnson, 2012?\n\n- Line 1291: Typo - $F^A$ should be $F^s$.\n\n- Line 1374: Typo - \"the first equation of Lemma 12.\"\n\n- Line 1420: Typo - $f$ missing.\n\n2. Algorithm 2: It would be beneficial to provide more insights into the difference between Algorithm 1&2.\n\n3. The related work section is not informative enough to provide a high-level overview of earlier work, provide more detailed explanation and comparison of the works listed in Table 1 more in detail would be helpful.\n\n4. Line 83: Please provide citations for these \"well-established consensus techniques.\"\n\n5. For the simulations, error bars are missing from the plot and 5 iterations seems insufficient for drawing robust conclusions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)