Multi-agent Performative Prediction with Greedy Deployment and Consensus Seeking Agents
Authors: Qiang LI
Chung-Yiu Yau
Hoi To Wai
Venue: NeurIPS 2022 Accept (2022)
Keywords: Performative prediction
Multi-agent
Decentralized stochastic algorithm.

Abstract: We consider a scenario where multiple agents are learning a common decision vector from data which can be influenced by the agents’ decisions. This leads to the problem of multi-agent performative prediction (Multi-PfD). In this paper, we formulate Multi-PfD as a decentralized optimization problem that minimizes a sum of loss functions, where each loss function is based on a distribution influenced by the local decision vector. We first prove the necessary and sufficient condition for the Multi-PfD problem to admit a unique multi-agent performative stable (Multi-PS) solution. We show that enforcing consensus leads to a laxer condition for existence of Multi-PS solution with respect to the distributions’ sensitivities, compared to the single agent case. Then, we study a decentralized extension to  the greedy deployment scheme [Mendler-Dünner et al., 2020], called the DSGD-GD   scheme. We show that DSGD-GD converges to the Multi-PS solution and analyze its non asymptotic convergence rate. Numerical results validate our analysis. 

Multi-agent Performative Prediction with Greedy Deployment and Consensus Seeking Agents
Qiang Li
Chung- Yiu Yau
Hoi-To Wai
Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong, Shatin, Hong Kong SAR of China {liqiang, cyyau, htwai cuhk. edu. hk
Abstract
We consider a scenario where multiple agents are learning a common decision vector from data which can be influenced by the agents' decisions. This leads the problem of multi-agent performative prediction (Multi-PfD). In this paper, we formulate Multi-PfD decentralized optimization problem that minimizes sum of loss functions, where each loss function is based on a distribution influenced by the local decision vector. We first prove the necessary and sufficient condition for the Multi-PID problem to admit unique multi-agent performative stable (Multi-PS) solution. We show that enforcing consensus leads to laxer condition for existence of Multi-PS solution with respect to the distributions' sensitivities, compared to the single agent case. Then, we study decentralized extension the greedy deployment scheme [Mendler- Dünner et al., 2020], called the DSGD-GD scheme. We show that DSGD-GD converges to the Multi-PS solution and analyze its non-asympootic convergence rate. Numerical results validate our analysis.
Introduction
Traditional learning/prediction problems often formulated with the assumption that data follows static distribution, from which decision vector sought by solving a corresponding optimization problem. While this assumption holds for 'stationary' tasks such as image classification. many real world tasks are dynamical, involving data that could influenced by decisions. the latter case, the predictions said to be performative. Example scenarios include when users strategic [Hardt et al., 2016, Dong et al., 2018, Kleinberg and Raghavan, 2020] such as in training an E-mail spam classifier, where users (including spammers) can adapt to the classifier's 's rules to evade detection.
common way to model performative prediction via incorporating decision-dependent distribution in formulating the learning problem Sirihonnrr--Cndella et al., 2008]. Since the pioneering work by Perdomo et al. [2020]. there is growing literature in analyzing the performative prediction problem, which studied the convergence of learning algorithms stable point of performative prediction [Mendler- Dünner et al., 2020, Drusvyatskiy and Xiao, 2020, Brown et al., 2022, Li and Wai, 2022, Wood et al., 202 1], algorithms to find stationary solution of performative risk [Izzo et al., 2021, 2022, Miller et al., 2021, Ray et al., 2022], update timescales of agent [Zrnic et al., 2021], etc.
Most of the existing works are focused on the single agent (learner) setting. In this paper, we concentrate on the multi-agent performative prediction (Multi-PíD) problem. Here, the agents are consensus-seekien seeking who seek common decision vector that minimizes the sum of loss functions through communications on a graph/network. Our setup pertains to the wide-spread applications of consensus- sttppe decentralized algorithms machine learning which leverages the large amount of data at cooperating agents, such as clinical data [Warnat- Herresthal et al., 2021], I, financial data [Li and Wang, 2019], etc. In specific, adopting consensus design can bring benefits such better out-of-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sample (i.e., generalization) performance, the ability to utilize data observed at all agents, improved robustness to agent failure. As pointed out by [Perdomo et al., 2020], real world applications may involve user data that can be influenced by the optimization solution leading to distribution shifts. For example, in clinical data, the agents wish to train model for treating some medical conditions. Upon the deployment of model, the future patients may react to the just deployed model by overstating their symptoms accordingly, which increase their chances of receiving better treatment at the hospital. Another example is the training of an E-mail spam classifier, where each agent represents regional server providing services to a subset of users. These users are in general different and may react to their serving agents differently, leading to heterogeneous and decision dependent data distributions. Notably, our setup differs from the recent works in [Narang et al., 2022, Piliouras and Yu, 2022] which consider game theoretical setup of Multi-PfD; see Fig. 1 and $2.
For the algorithmic model, we study a decentralized extension of the greedy deployment scheme [Mendler-Dünner et al., 2020], particularly we concentrate on the decentralized stochastic gradient (DSGD) [Lian et al., 2017] algorithm with greedy deployment (DSGD-GD). Overall, the DSGD-GD scheme emulates a scenario where agents apply DSGD, standard decentralized learning algorithm, while being agnostic to the performative nature of the prediction problem. In particular, upon each iteration, the non-converged local decisions will be deployed directly. Then, agents optimize their decision using stochastic gradient constructed from data with distribution shifted by local decision.
Tackling Multi-PiD with the DSCD DSGD-GD scheme yields a practical scenario of performative prediction in the multi-agent setting. We inquire the open questions: When will the Multi-PPt tfD problem admit a stable and consensual solution? If so, how fast does it take for DSGD-GD to converge to such solution? Does the limited communication in DSGD-GD impair its convergence rate? We provide affirmative answers to the above. Our idea hinges on adopting the concept of performative stable solution [Perdomo et al., 2020], which is a fixed point solution resulted from the interplay between agent(s) and data that react to the agent(s)' decisions. In particular, we focus on analyzing the multi-agent performative stable (Multi-PS) solution in our problem.
To our best knowledge, this paper provides the first study and analysis of Multi-PiD with consensus seeking agents via a practical DSGD-GD scheme. We highlight the following key contributions:
We provide necessary and sufficient condition on the sensitivity of decision dependent data distributions for the existence and uniqueness of the Multi-PS solution. An interesting finding is that the Multi-PS solution exists even if some of the performative prediction problems of individual agents are unstable. The consensus seeking behavior in Multi-PrD tends to stabilize the problem.
We study the DSGD-GD scheme and analyze its convergence towards the Multi-PS solution. We first show that the scheme is convergent under the same sufficient condition for existence of Multi-PS solution. With an appropriate step size rule, in expectation, the squared distance between the Multi-PS solution and the iterates decays as (1/t). and the squared consensus distance decays as Ol(tt), where t is the iteration number. Our tnnegrrined analysis also reveals that heterogeneous users, poorly connected graph may slow down the convergence of DSCD-GD. but only so in the transient, and the asymptotic rate has linear speedup property.
To validate analysis, we conduct numerical experiments on synthetic data and real data. Particularly, we consider the Gaussian mean estimation on synthetic data to validate our theory, and the logistics regression problem on the spambase dataset.
The paper is organized as follows. $2 introduces the Multi-PfD problem and DSCD-GD scheme. $3 presents the theoretical results on Multi-PID, DSGD-GD together with a proof outline. Finally, $4 shows numerical experiments to validate our analysis. All proofs can be found in the appendix.
Related Works As mentioned, the main ingredient of DSGD-GD scheme is the classical DSGD algorithm. The latter introduced in [Ram et al., 2010, Bianchi and Jakubowicz, 2012, Sayed, 2014] and is recently popularized for decentralized learning. Of relevance to our work are [Lian et al., 2017] which demonstrated a linear speed up against centralized SGD, and [Pu et al., 2021] with refined analysis, also see [Kong et al., 2021, Bars et al., 2022] on the effects of consensus steps and topology. We also mention recent advances to improve the efficiencies of DSGD in [Tang et al., 2018, Lan et al., 2020, Koloskova et al., 2019]. Our analysis entails fresh challenges as the sought Multi-PS solution cannot be described explicitly as an optimal solution to the Multi-PfD problem.
Another line of relevant works pertains to (multi-agent) reinforcement learning whose formulation also entails a decision-dependent distribution. To this end, policy gradient algorithms are analyzed in
2

---

[Zhang et al., 2020. Karimi et al.. 2019], and they have been recently extended to the multi-agent setting [Zhang et al., 2018, Chen et al.. 2021]; also see the survey [Zhang al., 2021]. Most of the above works showed convergence to a stationary point which may not be unique. This is in contrast to our analysis of DSGD-GD which converges to the unique Multi-PS solution.
2 Problem Setup
Consider scenario where there are n agents connected on an undirected and connected graph G == (V, F) such that V = [l,...,n), n). C V V. Note that we include self-loops such that (i, E E for any i E V. Each agent E V draws samples from the ith population of users. The latter is characterized by the distribution D;(O,) supported on Z C IR, p E N and parameterized by the agent's s decision vector 0, E Rd, E N. In other words, the ith population of users are only influenced by the ith agent's ' decision vector. Note that the populations of users can be heterogeneous such that (0) * ()"))) + j. even if 0 0'.
The agents aim find a common decision vector 0 E Rdd in collaborative fashion that minimizes the average of local losses. Consider the multi-agent performative prediction (Multi-PfDD problem:
ming,eet i 1 E.= Ez,-D,(0)) ((0,; s.t. 0, = ,, 4 (i.)) E.
(1)
Since G is connected, the constraint 0; 0 for (i.j)= E E enforces the decision to be in consensus across the n agents. In the above, E(0;; Z.) is the loss function of the fitness of the decision vector 0, with respect to (w.r..) the sample Z, The expected value Ez,-D, (e.) (E(0,; Zi) corresponds to the loss at agent w.r.t. the samples from the ith population of users.
Example 1. We describe strategic binary classification problem with linear utility for users to illustrate the application of (1). The sample Zi is defined by a tuple Z, = (X,, Y:) E RR [0,1) of feature and binary label, and the loss function is taken as the logistic regression function:
E(0: Z,) log (1 + exp((X; (0)) (X;;
2 1012
(2)
where > regularization parameter. The above loss function quantifies the mismatches between the classifier 0 and the given data tuple Z; = (X,,
On the other hand, the distribution (.) is controlled by the ith population of users. The distribution is decision dependent such that the sample Z; ~ (0:) depends on the ith decision O. Observing the ith decision Os, users of the ith population provides samples that are modified via a linear utility such that Z, (Xi, Yi) ~ D.)
(00).. is given by
X; = arg max mrngmaxxet Eedd (0, X)
1 x Y with (X,Y)~ ~ Di
2e;
for some E, > O, where De is a base data distribution of the ith population. Note that in the above, we have the closed form form solution X; = X + e,0,, Tuckling (1) leads to a common classifier O which takes the effects of the heterogeneous decision dependent distributions into account.
The Multi-PID problem (1) comprises of a stochastic objective function with a decision dependent distribution. In particular, for each agent i, the distribution D, (0.) captures feedback mechanism where users of the ith population react to the decision made by the ith agent. See Fig. I (left) for an illustration. Due to non-convexity, the performative risk in (1) can be difficult to minimize. In this paper, we are interested in the multi-agent performative stable (Multi-PS) solution:
rs = M() == arg mingeR" 1 Σ. EZ.DD. [1(0; 2,)1
(4)
which approximately solves (1). Notice that 0S is defined be a fixed point of the map M : R Rd The existence and uniqueness of 0.s will be shown under mild condition in Proposition 1.
Comparison to Existing Works. Our setup differs from recent works in [Piliouras and Yu, 2022, Narang et al., 2022]. Unlike ours, both works considered a game theoretical setting where the agents do not directly communicate their decisions. Instead, agents coupled through the data distributions which depend on the global decision profile == (0,... (0.....,..) O.))
In [Narang et al., 2022], agent/player i seeks to solve ming; (ZZDD. (v: Z+)] where the local distribution DD depends on the global decision / [Fig. 1 (middle)); while Piliouras and Yu [2022] study slightly different setting where the goal of agent/player i is to solve ming, [z, Z.)]
3

---

P100
(2.000)
P
(8)))
D (8)
Figure I: Comparing the frameworks of multi-agent/player performative prediction. (Left) This work: agent deploys 0g and local distribution (0,) is affected by 0 only; the agents communicate while aiming reach consensus 0 deploys 0, but local distribution is affected by joint decision (o...... 0z).
On eventually. (Middle) Narang al. [2022]: agent (Right) Piliouras and Yu [2022]: similar to [Narang et al., 2022] but the distribution is global D(O....., O.).
[Fg.. (right)]. Both works showed convergence to a stable equilibria via (stochastic) gradient- type updates. In contrast, our work considers cooperative agents who willing to share their decisions with other agents. Under this setting, we show that a natural decentralized scheme achieves convergence consensual decision that is performatively stable.
Decentralized Scheme. To find an approximate solution to (I) cooperative fashion, the natural approach is to deploy decentralized scheme where agents communicate limited amount of informa- tion with neighbors that are directly connected on G. Furthermore, we focus on a scenario where agents are agnostic to that their users may react to the agents' decisions. The above motivates us to study the following variant of the standard DSGD algorithm [Lian al., 2017].
Let us define a mixing matrix W E R on G such that Wij = W > 0 if (i,j) E E. otherwise Wi = if (i,j) & E, satisfying E Wij = 1 for any i = 1,..., n. We consider the scheme:
DSGD with Greedy Deployment (DSGD-GD) Scheme
At iteration Ê = 0, I, for any i E V, agent i updates his/her decision (0:) by the recursion consisting of two phases
(Phase 1) Zt+1 D.() (Phase 2) 0
Σズ= Wi 71t1 1 z
(5)
where 7++ > 0 is step size. Note that ve(0;; 2 2 denotes the gradient taken w.r.t. the first argument 0% and the samples Z,**1 at each agent are independent of each other.
The above combines the DSGD algorithm [Lian et al., 2017] with greedy deployment [Mendler- Dünner et al., 2020]. For iteration 2 0, the scheme can described with two phases:
In Phase 1, agent i deploys 0 at the ith population, whose users react to the decision and reveal sample z ~ (0)) to the agent. Note that this is greedy deployment scheme since the deployed decision of may not be stable w.r.t. (1). In Phase 2, agent receives the current decisions 6) from his/her neighbors j E N2 and update +1 according to the 'consensus' + 'stochastic gradient' step. Here, the "stochastic gradient' step is based on the local decision 0 and sample Z,+1 taken in phase one with greedy deployment. We remark that throughout the DSGD-GD scheme, the agents remain unaware of the performative behavior of their users.
Notice that the DSGD-GD scheme be interpreted as DSGD algorithm deploying biased stochastic gradient updates. Denote E, [-] as the conditional expectation up to iteration t, we observe
E, o (0); 2 = Ez, Vo (0);; 2 * Vo! (Ez,D, [((0) Z)])
(6)
The unbiased gradient on the r.h.s. also involves derivative w.r.t. the decision the distribution. Analyzing the convergence of DSGD therefore requires differrnnt techniques.

---

3
Main Results
This section studies the convergence of the DSGD-GD scheme and demonstrates that the latter can approximately solve the Multi-PfID problem (1). To facilitate our discussions, we first define:
0) = Ez, (o)) (o) (e(0; 2,),, /(0,0) :- - (((000)
Note that the first arguments in f f denote the agent's decision and the second argument is the deployed decision known the population of users. For the rest of this paper, unless otherwise specified, Ve(0; 2), ( O"), ( 8¹) denote the gradients taken w.r.t. the first argument 0.
Using the above notations, (1) is equivalent ming f(O; 0). We consider the set of assumptions:
A1. Fix any 0 E Rd, the function f(0:0) is p-strongly convex in O such that
f(0'; 0) 2 f(0: 0) + (V: 0) 0' 0) + (p/2) - 012. 40' 0 Rd.
(8)
A2. For any i 1, ................................ n, the loss function E(0: z) L- smooth such that
[VE(0;2) (( =1)|| S L 0'll || =111,, A 0 0 E R 2, E Z.
A3. For any i 1, ...... n, there exists a constant <; > such that
(() S 6 ||0 0'1l v 0
(10)
where (D, D') denotes the Wasserstein- distance between the distributions DD D'
AI, A2 require the loss functions to be strongly convex and smooth, while A3 states that the amount of distribution shift caused by the reaction of ith population to the agent's 's decision grows linearly with difference in decision. These assumptions are standard in the literature, e-g- [Perdomo et al.,
2020, Mendler-Dünne et al., 2020, Drusvyatskiy and Xiao, 2020]. To simplify notations, we define the average, maximum sensitivity as Caug Σi (i/n, <aa max;=1,..... G4 respectively.
Our first result establishes the existence of the Multi-PS solution OPS satisfying (S(PPS; ((OPS:0Ps) 0:
Proposition 1 (Existence and Uniqueness of PPS). Under A1-A3. Define the map M : Rd + RR
M( arg ming E. ()):
(11)
If fagg <. pz/ T., then the map M() a contraction with the unique fixed point 0P5 = M(PPS) If T./T, Cavg 2 L,/L, then there exists an instance of (11) where lim || cc.
See SA for the proof. Note the inverse condition number p//.. yields a light threshold on the sensitivity of the population for the stability of Multi-PID. Our result can be viewed as the multi-agent extension to [Perdomo et al., 2020, Prop. 4. J. Notice that while 0²S may not solve (I), it yields an approximate solution to the latter, depending on the magnitude of <aug: see [Perdomo et al., 2020].
Our result shows that Multi-PfD has a relaxed requirement for the existence of Multi-PS solution as it only depends on the average sensitiviry Caug- Consider when e; exceeds p/ L for the population served by ith agent, now there may not exist performative stable solution for the individual agent [Perdomo al., 2020]. Meanwhile, by Proposition 1, the Multi-PS solution still exists long as favg < /z/ L, e.g., when there are agents in the network with less sensitive users.
We also compare Proposition to [Narang et al., 2022]. Note that the latter considers decision- dependent distributions (1) with & ;= ....... 0n)) involving all decisions, which is different from our setting. Nevertheless, under similar conditions to Al-A3, Narang et al. [2022, Theorem 1] shows the performative stable equilibria exists if Σ < 22 I22 When 6; = Caug, it yields tavg < #4/( (/(V)L) which is more restrictive than the requirement Proposition
c
The relaxed condition in Proposition 1 can be attributed to the consensus seeking nature of (1), where agents with less sensitive users serve as mediators that prevent divergence of the map (11).
Convergence Analysis of DSGD-GD Scheme. Next, we focus on analyzing the convergence of the DSGD-GD scheme. We require the following assumptions:
A4. The non-negative matrix W doubly stochastic, i.e. W1 W There exists a constant
E (0, 1] such that W (1/m)111 || p.
5

---

A5. For any i = 1..... n and fixed 0 E R there exists a 2 0 such that
EZ,-D,(,)IVV Z.) - ff 011 - o² + 100 100-0% 0PS| PPS
(12)
A4 is standard assumption the mixing matrix, for example if G is connected graph, then W satisfying the condition can be constructed [Boyd et al., 2004]. Meanwhile, A5 bounds the variance of the 'stochastic gradient" ve(0; 2,) as the expected value to the latter yields Ez, ~D, ( (o) A (0; 0), where the gradients are taken w.r.t. the first argument O. Moreover, we assume that:
Z:)]
A6. For any i 1....: : there exists ç 2 such that
[VS(0 VS (0: 0)12 S (2 + 0 0PS|13) A A
(13)
It bounds the heterogeneity of the locally observed samples. As ()) = Eg,~D, [V 2;)]
(0) = -0), the constant will be = when the population associated with each agent produces identically distributed samples with the same deployed decision vector. Otherwise, ç measures degree of heterogeneity across populations. We remark that even when D; = ())
the samples - -3-1 may still not be identically distributed during the DSGD-GD iterations since the decision vectors 0 0f may not be in consensus when (. < 0o.
A6 also implies max:=1..... (O )1S 5² F. In fact, we show in (52) of the appendix, it suffices to prove the convergence of DSGD-GD GD without A6 as in [Pu et al., 2021, Yuan and Alghunaim, 2021]. We proceed our analysis with A6 extract tighter bound especially when is small.
In both A5, A6, we allowed the upper bounds to grow with (11 + ||0 8 [[3), e.g. A5 similar to [Pu et al., 2021, Assumption 1]. This is weaker condition than the commonly assumed uniform bound of (11), e.g.. in [Lian et al., 2017]. For example, it covers situations when the quadratic components in {(.) depends on both Z and O. Note that this relaxation implies that the variaaicehheterogenettt can be unbounded, leading to additional challenges in our analysis.
Define the following quantities and constants: fix any 8 >> O,
0 (1/n) Em= 0 0- = 0 -PPS O
(0) 0%) 00'T. p= μ (1 cagggg
L(1 + Emax] 2
0² + L3 + Emax) 12 == = 12o² + 18L2 Emax)
0 2ndeaag
C2
(14)
Note that O' is the distance between the ith averaged iterate o' and OPS, while O is d matrix of the tth consensus error. The following theorem establishes the convergence rate of DSGD-GD:
Theorem 1. Under A1-A6 and the condition on average sensitivity that Eavg < (1+8)E the step sizes {7h2 satisfy Ttt1 S i/. for any Z
Suppose
4 j
p
pei
sup (21
I min
p
02
/20g" V
192c (02 + +2)
4fica
poz
(15)
and the condition
2 S
minf
+ (m/4)) / 1+ (m/4)) 1 + p/(4 (p)} for any
Tes1 t 121, 1. Then, the iterates generated by DS admit the following bound for any 2 0.
ii7 2
288c1 (a" +2)
802
E
D
P²Ti
M+1
Jun
Yet1,
(16)
1=1
E
1
++
1
H+1 p)
10112 m
2(9 + 12 +
(17)
2
p²
M+
where D 1 + ?1 Se1 definitions of the constants Ci C2 c3 from (14).
o 0 denotes the initial error, A = D + 3 can'
Sg²
and recall the
mp
The free parameter 5 > 0 in (14) can be chosen arbitrarily. Thus, according to Theorem 1, DSGD-GD converges when the average sensitivity Eaug is strictly below the threshold // L in Proposition 1, i.c.,

---

the same sufficient and necessary condition that guarantees the existence of 0PS. Further, our result holds for general step size rules such as constant step size and diminishing step size.
og for some ag, 01 > In the latter case as To yield 0|| |P] + O, a common option 7 a1+t
T: - OL//t, we observe from (16), (17) that the distance performative stable solution |0']22 converges to zero as (1/t),, while the consensus error ||@] I converges to zero as ((1/t²). We remark that our analysis also applies to the case of time varying graph; see $G for a proof sketch.
On the other hand, the bound (16) can be simplified to
Lio (50 nijiip
o²
B O 0 P (1-
7i
np 7t-
(18)
As seen, the error is controlled by three terms. The first term is a transient term that consists of the product IT (1 (.)). It decays sub- sebb-eoeetrrillly and is scaled by the initial error D. The second term is transient term and is affected by the spectral gap of mixing matrix p. the degree of heterogeneity etc. It decays as (g Finally, the last term is fluctuation term that only depends on the averaged noise variance (o /n). It decays at the slowest rate as ((+)).
Effects of Network Topology and Heterogeneity. An interesting observation from (18) is on how the network topology (p) and heterogeneity across local sample distribution (s) affects the convergence behavior of DSGD-GD. First, we note that the last term of O o² / (ūi)) is similar to the fluctuation term in SGD using the batch size of n under centralized setting, e.g., [Moulines and Bach, 201 IJ. Second, the constants p, only affect the term of rate ((7)).
In the case with diminishing step size " aitz. the second term of (18) will vanish at faster rate than the last term. Particularly, if for some C> O,
7t S C 5p o +
(19)
then (18) will be dominated by O(n o² /(in)). In other words, the effects of the network topology and heterogeneous population vanish asymptotically as 0² + 0PS.
As such, the 'linear speedup' behavior of DSGD in [Lian et al., 2017, Pu et al., 2021] can be extended to Multi-PiD with the DSGD-GD scheme. Again, we highlight that the consensus seeking behavior of agents has led to such speedup in convergence towards the Multi-PS solution.
3.1 Proof of Theorem
We outline the main steps in proving Theorem 1. As a preparatory step, we borrow the following lemma the Lipschitzness of (00, O) from (Drusvyatskiy and Xiao, 2020, Lemma 2.1]:
Lemma 2 (Continuity of f.). Under A2, A3. For any o,, 0,, 0 0' E TRd, it holds:
f. 0) - V f. Illll s L 110 01 + Le; ||0 0'1l
(20)
By A4, the update recursion for the average iterate of DSGD-GD can be expressed as ++ (1/n) Σn 0 - = 7 Em VI 2/+²)
(21)
Using the above recursion, we show the following lemma for the one-step progress of DSGD-GD.
Lemma 3. (Descent Lemma) Fix any 8 and let eavg S ( Under AI, A2, A3, A5 and let the step sizes satisfy sup,20 70+1 S n 02" 1
the following bound holds
Eg 2.110++1 2 S S (1- (1741)
|000 |0=10
+
+c17741 + ten 1
2
20
(22)
1+1
for any t 2 O, where EA|-] is the expectation operator conditioned on the iterates up to the tth iteration, and recall the definitions of c1, 02 it from (14).
The proof is in SB. We highlight that proving the upper bound (22) requires the smoothness property Lemma 2 for handling the difference Σ (f)) 0;) (f PPS) as proportional to the error against the Multi-PS solution 0' and the consensus error / Lemma 3 prompts us to study the consensus error || [ f and key observation is:

---

Lemma 4. (Consensus Error Bound) Under A2-A6 and let the step sizes satisfy sup:20 76-1 S
p/ V20a, then it holds
E -
1 12 +5² 76+1
+9002 +5²) +52)
+
7+1
(23)
P
for any t 222 O, where we recall that == 12o² + 18L2 + Cmax)
The proof is in SC. (52) of the appendix, we provide an alternative consensus error bound without using A6, Note that despite the decision dependent distributions due to the performative nature of Multi-PfD, the above bound shows a similar trend as in [Bars et al., 2022, Pu al., 2021, Kong et al., 2021, Koloskova et al., 2019].
However, unlike [Bars et al., 2022, Lemma 2], the r.h.s. of (23) contains a O(1o² + h2+ 101)²
term which arises from A5, A6 with the growth condition. This introduces new challenges to analysis as it will be insufficient to conclude from (23) alone that DSGD-GD converges to a consensual solution.
Our plan is to consider Lemmas 3 and 4 simultaneously in order to control E| 0 1| E 1 Define the following sequence of non-negative numbers: for any 2
L++1 == E [1|0++1| + 7i++
Se1 pm
(24)
We obtain the following lemma: Lemma 5 (Convergence of L.). Under Al-A6. Suppose that the step sizes satisfy supr2o 7441 S
min
4 #
p2p (02
pei
}. For any t 2 0, it holds
4fter tpcs
Lit1 & (1
22) Le 77c (a² + + + n 11-2022211
(25)
Further, if the step sizes satisfy Tt-1 S min( (on((V (7/4)/² 8/1 + (ū/44)²²) for any 1 2 1, then
8c1
74% 2
D + 288c1 (o² +2)
80
E
0
+ 7+1
|10
++1
1
M+1 +
7+1 (26)
pn
2²
pin
i=1
where we recall that D = |1001
+ +
Sei pn
|
The proof is in $D, where (25) is based on a careful combination of Lemmas 3 and 4, and (26) is computed from the non non- -sympttpiooic analysis for the recursion (25).
Proof of Theorem 1. Lemma 5 immediately leads to (16) of the theorem as the lh.s. of (26) is lower ++++
bounded by E
+ -12... To obtain (17), we observe from the simplifying the r.h.s. of (26) that
288c| (o" + s²)
So"
80"
sup E f21
0
< D +
m
S D
A.
(27)
jun
2
C2
Note that | < A as well. Substituting the above into Lemma yields
1
1
| < (1 p/2) 1 11 + p--ppp----00 + 124 +52) +²))
(1- 2) ++1 1 0 + (9+ 12 + +
Σ
1+1
(1-2)
11
P 1+1-8
7
(28)
2
Applying Lemma in the appendix together with the step size condition 7//141 S p/(4 2p). t t2 1, leads to (17) of the theorem. This concludes our proof.
4 Numerical Experiments
We consider two examples of performative prediction problems to verify our theories. All experiments are conducted with Python on server using 80 threads of Intel Xeon 6318 CPU.
Multi-agent Gaussian Mean Estimation. We aim to illustrate Proposition 1, Theorem via scalar Gaussian mean estimation problem on synthetic data. We consider 25 agents connected
8

---

PS Error: |0'|
Consensus Error
Expected Risk
13a
122
Ring -
17
12
Ring 1=0.0
10
Ring é 1.05
190
22
Single = 1.01
1-1.1
Ring 2-00
129
Ring 1.01
157
Ring 1.005
12"
Ring = 0.9
Ring e
Single 1.01
Single
12"
10
300
Iterations
Iterations
Iterations
Figure 2: Multi-agent Gaussian Mean Estimation. (Left) Gap Multi-PS solution. Note that 0PS does not exist if Cavg 2 1 and the plots are thus skipped. (Middle) Consensus error | (Right) Performative risk (7). Results are averaged over 10 runs and shaded area is 90% confidence interval.
Train Gradient
Consensus Error
Test Accuracy
105
DSGD-GD 2- 0.01
DSCD-GD 2 0.1
10-1
DSGD-GD
10'
10
0.7
301
DSED č-
DSCD-GD Z- 0.61
16.1
DSGD 30 0-
DEGD-GD 6-0.01
305
DSGD-GD
0.0.0
D5GD/=0.01
D3ED 0-0.1
05G0/-0.1
DSGD E-1.0
20
0.4
DSGD 1-60
30
30'
10a
3.7
3.7
10"
30'
30'
30
307
310
35'
1.2
15"
15a
15"
Iterations
Iterations
Iterations
Figure 3: Spam Email Classification. (Left) Gradient on training dataset f a'> Note that ff(ers -0'S)= = 0 and thus the gradient norm measures the gap to 0PS (Middle) Consensus Error
(Right) Test accuracy with shifted distributions. We also compare the non non-performative optimal solution (dashed lines, DSCD in the legend) on the shifted dataset.
ring graph, and the Multi-PfD problem (1) is specified with {(0; Z.) = (0; - 2 The local
distributions are given by D.,).) = N(; + e,O,, o²) where 2; the mean value be estimated. For this problem, we have μ = 1, L = 1, as such if 0 < E Eavg < 1, the Multi-PS solution can be
computed in closed form as 85 = Σm= / [n(1 - avgg)] while OPS does not exist if eavg 2 1.
In our experiments, we set 2, = 10, o² 50 and step size for DSGD-GD as 7/- = an/(a) + t) with 4n = 50, Φ1 = 10a In Fig. 2, we compare the gap
|00 1| consensus error | expected per- formative risk f O0 T') of (1), against the iteration number t. We examine the behavior of DSGD-GD when the Multi-PiD problem has an averaged sensitivity parameter of cavg E {0.9, 1.01, 1.05, 1.1} and under a heterogencous, decision-dependent distribution environment where e; are distinct.
We first observe from Fig. 2 (left) and (middle) that when Cavg = 0.9 < 1. the gap 100 0 decays at (1/1)) as 1. + 20, while the consensus error || |e,,'' decays at ((1/(2). This coincides exactly with Theorem 1. Furthermore, in Fig. 2 (dash-dotted), we simulate a setting where eavg 0.9 but one of the agents with e = 1.01 is always disconnected from the network and perform the greedy deployment scheme individually. We observe from the figure that its performative risk (0; 0 diverges as t + co. This indicates that consensus can help stabilize the system.
Lastly, from Fig. (middle) and (right), we observe that whenever Caug > 1, the consensus error and performative risk diverge. Again, this corroborates with our Proposition 1.
Email Spam Classification. We evaluate the performance of DSGD GD by simulating the performative effects on a real dataset. This example a multi-agent spam classification task based on spambase, a dataset [Hopkins, 1999] with m = 4601 samples, d = 48 features. We adopt Example I and simulate a scenario with 25 regional servers on ring graph. Each server has access to training data from vn; = 138 samples from spambase modeling the different set of users; the rest of Mitrain 1150 samples are taken as testing data. The servers aim to find a common spam filter classifier via (2) with 3 10-4, To model the strategic behavior of users, their features X; are adapted to 0 through

---

maximizing linear utility function, resulting in the shifted distribution (0,),) specified in (3). The sensitivity parameters are set as 6, E {0.A6avg: 0.456avg:... 1.66avg) } with Cavg {0.01, 0.1, 1}.
Our results are shown in Fig. 3 as we compare the gradient |/ ( 0 I12 evaluated on the training dataset, the consensus error [ Il3. and the accuracy on the testing dataset, against the iteration number f. From Fig. 3 (left) and (middle), we observe that the DSGD-GD scheme converges to the Multi-PS solution and reaches consensus under various settings of faug. at the rates ((1/t), ((1/(), respectively. In Fig. 3 (right), we evaluate the performance of the trained classifier O on the testing dataset with shifted distribution due to 0 We compare with non ponn--eefoooiilllyy trained solution obtained by solving 0 arg ming Ei= (0; 0) (DSGD in the legend), i.c., without any shift in distributions, but evaluate the performance on distribution shifted by 0". As observed, the test accuracy decreases as sensitivity favg increases, and DSGD-GD achieves better accuracy than DSCD.
Conclusions & Limitations
In this paper, studied the Multi-PID problem, and analyzed its stability when DSGD-GD scheme is applied. Our results indicate that when agents are consensus seeking, Multi-PID admits a performative stable solution with laxer condition and DSGD-GD achieves linear speedup. Limitations results include the requirement of synchronous updates among agents, strongly convex loss [cf. A1], etc., which shall be explored in future extensions.
current
References
B. Le Bars, A. Bellet, M. Tommasi, and AM. Kermarrec. Yes, topology matters in decentralized optimization: Refined convergence and topology learning under heterogeneous data. arXiv preprini wrxiv:2204.0445:: 2022. URL httpt:t/aaatii......//// org/ aa//abb//222// /2044. 04452.
Pascal Bianchi and Jérémie Jakubowicz. Convergence of a multi-agent projected stochastic gradient
algorithm for non-convex optimization. IEEE transactions automatic control, 58(2):391-40) 2012.
Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, 46(4):667-68) 2004.
Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in stateful world. In AISTATS, 2022.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: benchmark for federated settings. In NeurlPS Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Basar. Communication-efficieee policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 2021.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic clas- sification from revealed preferences. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 55-70,25 2018.
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision--dependent distributions. ArXiv preprint arxiv:2011.11177 2020.
Andrzej Granas and James Dugundji. Fixed point theory, volume 14. Springer, 2003.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In ITCS, page 111-122 2016.
Reeber Hopkins, Mark. Spambase. UCI Machine Learning Repository, 1999.
Zachary Izzo, Lexing Ying, and James Zou. How to learn when data reacts to your model: performa- tive gradient descent. In ICML, pages 4641-4650. PMLR, 202..
10

---

Zachary Izzo, James Zou, and Lexing Ying, How to learn when data gradually reacts to your model. In AISTATS, 2022.
Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference on Learning Theory, pages 1944-1974.
PMLR. 2019.
Jon Kleinberg and Manish Raghavan. How do classifiers induce agents invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478 3487. PMLR, 2019.
Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian Stich. Consensus control for decentralized deep learning. In International Conference Machine Learning, pages 5686-5696. PMLR, 2021.
Guanghui Lan, Soomin Lee, and Yi Zhou. Communication--ffccenn algorithms for decentralized and stochastic optimization. Mathematical Programming. 180(1):237-288 2020.
Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv
preprint arXiv: 1XXiv:990000550 2019.
Qiang Li and Hoi-To Wai. State dependent performative prediction with stochastic approximation. In AISTATS, 2022.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu, Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In NeurlPS, 2017.
Celestine Mendler-Dünner, Juan Perdomo, Tijana Zmnc, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33:4929-4933 2020.
John Miller, Juan C. Perdomo, and Tijana Zmic. Outside the echo chamber: Optimizing the performative risk. In ICML, 2021.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in neural information processing systems, volume 24, 201
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian J. Ratliff. Multiplayer performative prediction: Learning in decision-dependdnt games. In AISTATS, 2022.
Juan Perdomo, Tijana Zrnie, Celestine Mendler-Dinner,, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599-7609. PMLR, 2020.
Georgios Piliouras and Fang-Y Yi Yu. Multi-agent performative prediction: From global stability and optimality to chaos. arXiv preprint arXiv:2201. 10483, 2022.
Shi Pu. Alexander Olshevsky, and Ioannis Ch Paschalidis. A sharp estimate on the transient time of distributed stochastic gradient descent. IEEE Transactions on Automatic Control, 2021.
Joaquin Quiñonero-Candela Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. MIT Press, 2008
Sundhar Ram, Angelia Nedić, and Venugopal V Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications, 147(3):516-555) 545, 2010.
Mitas Ray. Lillian J Ratliff, Dmitriy Drusvyatskiy, and Maryam Fazel, Decision-dependent risk minimization in geometrically decaying dynamic environments. In AAAI Conference on Artificial Intelligence, To appear, 2022.

---

Ali H Sayed. Adaptation, learning, and optimization over networks. Foundations and Trends in Machine Learning, 7:311-801, 2014.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Liu. d: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4855 PMLR, 2018.
Stefanie Warnat-Herresthar Hartmut Schultze, Krishnaprasad Lingadahalli Shastry, Sathyanarayanan Manamohan, Saikat Mukherjee, Vishesh Garg, Ravi Sarveswara, Kristian Händler, Peter Pickkers, N Ahmad Aziz, et al. Swarm learning for decentralized and confidential clinical machine learning. Nature, 594(7862):265-270 2021.
Killian Wood, Gianluca Bianchin, and Emiliano Dall' Anese. Online projected gradient descent for stochastic optimization with decision-dependee distributions. IEEE Control Systems Letters, 6: 1646-1653) 2021.
Kun Yuan and Sulaiman A Alghunaim. Removing data heterogeneity influence enhances network topology dependence of decentralized sgd. arXiv preprint arXiv: arXiv:2105.00003,, 2021.
Kaiqing Zhang, Zhuoran Yang. Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In International Conference on Machine Learning, pages 5872-588) PMLR, 2018.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 3586-3612, 2020.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and a algorithms. Handbooo of Reinforcemenl Learning and Control, pages 321-384, 2021.
Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? In NeurIPS, volume 34, 2021.
12


Reviews:
[{"review_id": "smwjwVWw_aE", "reviewer": "Reviewer_N8Lb", "summary": "This paper studies a multi-agent performative prediction problem, where the agents want to learn an identical local decision parameter to minimize the average of all local loss functions. The main challenge is that the local data distribution, which is an input to the local loss function, will change as the agents update the local decision vectors. Before this work, similar performative prediction problems have been studied in single-agent settings and competitive multi-agent settings. In contrast, this work studies a cooperative multi-agent setting where all agents are willing to share local decision vectors and want to reach a consensus. The authors propose a decentralized learning scheme and provide a finite-time convergence bound. They also conduct numerical simulations on synthetic data to validate the theoretical results.", "questions": "As discussed in ``Weakness’’, I am concerned about the motivation behind the proposed problem setting in this work. The authors presented three examples in this paper: Example 1, multi-agent Gaussian mean estimation, and Email Spam Classification, but it looks like they are artificially constructed to fit in the Multi-PfD setting rather than coming from real-world applications. In rebuttal, I hope the authors can discuss why some core assumptions in the setting (e.g., the consensus and local communication with neighbors) are critical in these application examples.", "limitations": "Yes, the authors discussed the limitations of this work in the last paragraph. And I don’t see any negative social impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper is well-written and easy to follow, and the broad topic of performative predictive is interesting for the ML community. The authors explained the intuition behind the problem setting, the algorithm, and the main theoretical results very well. They also did a detailed comparison with related works to emphasize the novelties and challenges of this work.\n\nWeakness: The multi-agent performative prediction problem setting proposed in this work is a novel and natural extension of the single agent setting, but the motivation is not sufficient in the following aspects: Since the local data distribution $D_i$ only depends on the local decision vector $\\theta_i$, it seems unnatural to require all agents to reach a consensus on their local decision vectors. Besides, the graph $G$ of agents is only used as a communication graph. Compared with other works where the local data distribution $D_i$  can depend on non-local decision vectors, the multi-agent problem considered here looks more like a localized problem. More application examples are desired to motivate the setting considered in this work.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qg_jC6Ebldp", "reviewer": "Reviewer_a5Cf", "summary": "This paper consider the problem of multi-agent performative prediction (Multi-PfD), and formulate Multi-PfD as a decentralized optimization problem. The authors first prove the necessary and sufficient condition for the Multi-PfD problem to admit a unique multi-agent performative stable (Multi-PS) solution, show that enforcing consensus leads to a laxer condition for existence of Multi-PS solution with respect to the distributions’ sensitivities, compared to the single agent case. Then, they study a decentralized extension to the greedy deployment scheme [Mendler-Dünner et al., 2020], called the DSGD-GD scheme. They show that DSGD-GD converges to the Multi-PS solution and analyze its non-asymptotic convergence rate.  \n\n\n", "questions": "Please clearly state the status of area of multi-agent performative prediction (Multi-PfD) and demonstrate your contribution positions. From the optimization side, I don't see too much novelty of the paper.  ", "limitations": "the authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: this paper provides the study and analysis of Multi-PfD with consensus seeking agents via a practical DSGD-GD scheme. The results indicate that when agents are consensus seeking, Multi-PfD admits a performative stable solution with laxer condition and DSGD-GD achieves linear speedup. \n\nCons: In terms of optimization, the proposed methods are not novel, especially with limitations such as the requirement of synchronous updates among agents, strongly convex loss, etc. I would say the major contribution will be on the Multi-PfD problem formulation side, which I am not quite familiar with.  ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Q3J2YTIAuYe", "reviewer": "Reviewer_JuZu", "summary": "This paper formulate Multi-PfD as a decentralized optimization problem and admit a multiagent solution. Compared to the single-agent case, enforcing consensus leads to a laxer condition for the existence of Multi-PS solution with respect to the distributions’ sensitivity. This paper study the DSGD-GD scheme and analyze its convergence towards the Multi-PS solution, and show that the scheme is convergent under the same sufficient condition for existence of Multi-PS solution", "questions": "Can the method be used on reinforcement learning to change the unique convergence problem of reinforcement learning algorithm?", "limitations": "No", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality:\nCompared to multi-agent reinforcement learning algorithms, the proposed DSGD-DG method can converge to a unique Multi-PS solution.\n\nquality, clarity:\nThe article is well organized.\n\n\nsignificance:\nThe algorithm proposed in this paper has practical significance. In the dynamic classification task, it can dynamically adapt to some changes in the environment. Such as spam classification tasks. The algorithm was also experimented on this task, and achieved good results on the spambase-based multi-agent spam classification task.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2urgibN0SO", "reviewer": "Reviewer_hRQZ", "summary": "The paper addresses multi-agent performative prediction (Multi-PfD), focusing on a setting where multiple agents are learning a common decision vector from data that can be influenced by their decisions. The paper formulates this as a decentralized optimization problem and identifies a necessary and sufficient condition for a unique multi-agent performative stable (Multi-PS) solution. The paper demonstrates that the consensus effect results in a relaxed requirement compared to the single agent case. As a solution to the problem, the paper studies a decentralized extension to a greedy deployment scheme (DSGD-GD), demonstrates that it converges to the Multi-PS solution, and analyzes the non-asymptotic convergence rate. The analysis reveals that heterogeneous users and poor graph connectivity may impair convergence but do not affect the asymptotic rate. Some numerical experiments on synthetic and real data are provided as validation of the analysis. ", "questions": "1.\tIs there a clear example where the consensus solution is clearly superior and desirable? i.e., Can the authors provide a stronger motivation for the studied problem?\n2.\tThere is relatively limited discussion of the assumption that the local distribution is only affected by the agent’s decision vector. Can the authors elaborate on how this restricts the application of the results to multi-agent problems? Is it possible to extend the results to handle this setting?\n3. As the authors acknowledge, the assumption of strong convexity is limiting. Can the authors comment on how the results might be extended to incorporate weaker requirements?\n", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1.\tThe paper studies an interesting problem and provides a thorough and useful theoretical analysis that addresses key questions of interest (existence of stable solution, convergence + rate). Although parts of the proofs are similar to those of related results in decentralized optimization and performative prediction, there are additional challenges in the analysis and these are handled in an elegant fashion.   \n2.\tThere is valuable discussion associated with the theoretical results. Going beyond expressions for bounds, the papers discusses key contributing factors to various terms. This leads to a specification of how factors such as graph connectivity impact the behaviour. \n3.\tThe assumptions underpinning the analysis do not impose unreasonable constraints that make the setting impractical, although the strongly convex loss assumption and the local decision impact do impose limitations. \n4.\tThe paper is very well written. The key theoretical results are presented in a clear manner and there is enough discussion of the proof procedure to provide the reader with an understanding of the general strategy. \n5.\tThe numerical experiments, while limited and not the main focus of the paper, do provide a validation of the theoretical analysis. \n\nWeaknesses\n\n1.\tThere is a relatively weak motivation for the setting under study in the paper. In the introduction, the paper cites Hardt et al., Dong et al., and Kleinberg et al. in providing an example scenario, but the extension to the multi-agent setting is not clearly motivated. The example is a spam classifier and the proposed multi-agent context is regional servers with users that respond in different ways. In this case, it’s not obvious why the consensus solution is desirable. If there is sufficient data, then it would seem that individual classifiers for each region would be preferable. If not, then I would think that it would be natural to explore compromises with some parameters being shared and others permitting a suitable response to the local data.    \n2.\tExperiments: While the experiments are primarily illustrative and serve the role of validating the theory, it is misleading and incorrect to claim that the paper “illustrate[s] the Multi-PfD problem in a real application” (l. 302). While the analyzed dataset is from a real application, neither the division into multiple agents nor the users’ proposed adaptation are.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept