Year: 2021

Abstract:
The recent framework of performative prediction (Perdomo et al., 2020) is aimed at capturing settings where predictions influence the target/outcome they want to predict. In this paper, we introduce a natural multi-agent version of this framework, where multiple decision makers try to predict the same outcome. We showcase that such competition can result in interesting phenomena by proving the possibility of phase transitions from stability to instability and eventually chaos. Specifically, we present settings of multi-agent performative prediction where under sufficient conditions their dynamics lead to global stability and optimality. In the opposite direction, when the agents are not sufficiently cautious in their learning/updates rates, we show that instability and in fact formal chaos is possible. We complement our theoretical predictions with simulations showcasing the predictive power of our results.

heading: 1 INTRODUCTION
text: Performative prediction (Perdomo et al., 2020) is a recently introduced framework that focuses on a natural but largely unexplored element of supervised learning. In many practical cases the predictive model can affect the very outcome that it is trying to predict. For example, predictions about which part of a road network will have high congestion trigger responses from the drivers which affect the resulting traffic realization leading to a shift of the target distribution. In such settings, (Perdomo et al., 2020) explored conditions for the existence and approximate optimality of stable equilibria of such processes.
One possible way to interpret the performative prediction setting is a single agent “game”, where the predictive agent is playing a game against himself. An agent chooses the parameters of his model as his actions but the predictive accuracy/cost of the model depends on his own past actions. Fixed points of this process do not allow for profitable deviations. Once cast in this light, it becomes self-evident that the restriction to a single predictive agent/model is arguably only the first step in capturing more general phenomena where there is a closed loop between predictive models and their environment. This motivates our central question: What is the interplay between stability, optimality in cases where multiple predictive models operate in parallel to each other? Can the competition between multiple models lead to novel phenomena such as phase transitions from stability to instability and chaos?
A natural setting to consider for example is market competition, where multiple hedge funds are trying to simultaneously predict future prices, volatility of financial instruments. Of course as they act upon their predictions they also move the prices of these commodities in a highly correlated way. As more agents enter the market and the competition becomes increasingly fierce, is it possible that at some point the market flips from quickly discovering accurate stable predictions reflecting the underlying market fundamentals to self-induced unpredictability and chaos? When it comes to performative prediction can too many cooks spoil the soup?
Our model Standard supervised learning consists of three components: a set of predictive models, a loss function, and a data distribution. The learner (agent) observes samples of the distribution, and then decides a predictive model. When predictions are performative, the agent’s decision of a predictive model influences the data distribution. Thus, instead of a fixed data distribution, a predictive prediction also has a distribution map: a mapping from the agent’s predictive models to
data distributions. We further propose multi-agent performative prediction which model the influence of multiple agents’ decisions on the data distribution, and ask whether these influence leads to convergent or chaotic systems.
To understand the framework of multi-agent performative prediction, we study a natural regression problem with multi-agent location-scale distribution maps (definition 2.2) where the agents’ influence is linear in the agents’ models. Specifically, the data consist of features and outcomes. For each agent i ∈ [n], his influence on the distribution of outcome is his model weighted by a scalar λi > 0. When n = 1, our multi-agent location-scale distribution map is a special case of locationscale family in Miller et al. (2021). In the market example, each hedge fund company tries to predict the price (outcome) based on macroeconomic data or other information (features). These influence parameters λ1, . . . , λn can be seen as each hedge fund’s capital that can influence the distribution of the future price.
Finally, we consider the agents do not know the dependency between their model and the data distribution, and they can only improve their predictive models myopically and iteratively. In this paper, the agents myopically use a reinforcement learning algorithm, exponentiated gradient for linear regression (Kivinen & Warmuth, 1997), to improve their predictive models in rounds. We study the long-term behavior, and ask if the system converge to the performative stable and optimal point, or behave chaotically.
Our results We first study basic properties of our multi-agent preformative prediction with multiagent location-scale distribution map. We show 1) the existence of performative stable point in our setting (proposition 3.1) and 2) the performative stability and performative optimality are equivalent (proposition 3.2). This equivalence allows us to focus on the dynamical behavior of the system.
In section 4, we introduce learning dynamics to the multi-agent performative prediction, and study their long-term behavior. We provide a threshold result which depends on the learning rates of exponentiated gradient descent and the collective influence. Theorem 4.1 shows the dynamics of exponential gradient descent converge to the performative stable and optimal point when the learning rate is small enough. Our convergence result in theorem 4.1 holds when the feature space is multi-dimensional, and every learning agent can use different learning rates starting at arbitrarily interior states. Our exact convergence result also works in the single-agent performative prediction setting. Contrarily, previous convergent results in Perdomo et al. (2020); Miller et al. (2021); Mendler-Dünner et al. (2020) only show that their dynamics converge to a small neighborhood of the performative stable point.
On the other hand, section 4.2 shows the dynamics can have chaotic behavior if the collective influence Ln is large enough. Specifically, theorem 4.6 shows that even when the feature space is in R2 these systems provably exhibit Li-Yorke chaos, when the collective influence ∑ i λi is large enough. This implies that there exists an uncountable “scrambled” set so that given any two initial conditions in the set, the liminf of the distance between these two dynamics is zero, but the limsup of their distance is positive. (definition 2.4) The chaotic result in theorem 4.6 also holds for the original single-agent performative prediction so long as the agent’s influence is large enough, and, thus, complements previous performative prediction works on convergence behavior, which primarily consider that the agent’s influence on the data distribution is sufficiently small. Moreover, no matter how small the agents’ learning rates, theorem 4.6 shows that chaos is inevitable in some performative predictions settings when the number of agents exceeds a carrying capacity. After that the system becomes totally unpredictable with small perturbations exploding exponentially fast. 1
Finally, section 5 provides numerical examples of our dynamics and show convergent and chaotic behavior. Additionally, through simulation, we demonstrate that our convergent and chaotic results also hold when the agents can only access noisy estimation of the gradient and conduct stochastic exponentiated gradient descent.
Related work Data distribution shift is not a new topic in ML, but earlier works focused primarily on exogenous changes to the data generating distribution. Performativity is machine learning was introduced by Perdomo et al. (2020). The original work and several follow-ups study the discrepancy between performative stability and performative optimality and prove approximated conver-
1We highlight our revision in blue color.
gence of learning dynamics, e.g., stochastic gradient descent, or iterative empirical risk minimization. (Mendler-Dünner et al., 2020; Drusvyatskiy & Xiao, 2020; Izzo et al., 2021) Performativity of prediction is also related to several applications: strategic classification (Hardt et al., 2016), retraining Bartlett (1992); Kuh et al. (1990).
Inspired by the instability of training algorithms in ML applications such as Generative Adversarial Networks (GANs), there has been a lot of recent interest in understanding conditions (particularly in multi-agent systems) where learning behavior may be non-equilibrating/unstable (Cheung & Tao, 2020; Balduzzi et al., 2020; Flokas et al., 2020; Andrade et al., 2021; Letcher, 2021; Giannou et al., 2021). The (in)stability and performance of exponentiated gradient descent in particular (also referred to as Multiplicative Weights Updates) and other closely related dynamics has attracted a lot of attention (Cohen et al., 2017; Bailey & Piliouras, 2018; Cheung, 2018; Panageas et al., 2019; Cheung & Piliouras, 2020; Vadori et al., 2021). The technique of Li-Yorke chaos has recently found applications across several different domains such as routing games, Cournot games and blockchain protocols (Palaiopanos et al., 2017; Chotibut et al., 2020; Bielawski et al., 2021; Cheung et al., 2021; Leonardos et al., 2021). To our knowledge, this is the first time where such formal chaotic results are established in settings related to performative prediction and supervised learning more generally.
Another line of related works is learning in games. Specifically, our dynamics can be seen as special cases multiplicative weight update (Hedge algorithms) on congestion games. Previous works on Hedge algorithms only show exact convergence when the learning rate is decreasing Kleinberg et al. (2009); Cohen et al. (2017), and, to our best knowledge, our results are the first that shows exact convergence of Hedge algorithms with small constant learning rates. Our results also complement the exact convergence result of the linear variant of multiplicative weight update by Palaiopanos et al. (2017).

heading: 2 PRELIMINARY

heading: 2.1 MULTI-AGENT PERFORMATIVE PREDICTION
text: A multi-agent performative prediction comprises n agents deploying their predictive models fθ1 , . . . , fθn with parameters θ1,θ2, . . . ,θn ∈ Θ that collectively influence the future data distribution. We formalize such dependency via a distribution map D(·) which outputs a distribution on the data, D(~θ), given a models profile ~θ := (θ1, . . . ,θn) ∈ Θn. A loss function `(z,θ′) measures the loss of a model fθ′ on a data point z ∈ Z , and the expected loss on a distribution D is Ez∼D[`(z,θ′)]. For performative prediction, we further define the decoupled performative loss on a distribution mapping D as
`(~θ,θ′) := Ez∼D(~θ)`(z,θ ′)
where θ′ ∈ Θ denotes a predictive model, while ~θ ∈ Θn denotes a deployed model profile. Given the set of model Θ, the loss function `, and the distribution mapping D, each agent in a multi-agent performative prediction (Θ, `,D) pursues minimal loss on the distribution that they collectively induce. We consider two solution concepts performative optimality and performative stability which generalizes the original ones in Perdomo et al. (2020).
Definition 2.1. Given (Θ, `,D), a models profile ~θ∗∈ Θn is performatively optimal if the total loss is minimized,
~θ∗ ∈ arg min ~θ∈Θn ∑ i `(~θ,θi).
Another desirable property of a model profile is that, given all agents deploy their models, their models are also simultaneously optimal for distribution that their model induces. Formally, ~θ∗ is performatively stable if for all i ∈ [n]
(θ∗)i ∈ arg min θi∈Θ `(~θ∗,θi).
The performative optimality does not implies the performative stable point. For performative optimal point, the variable for minimization ~θ affects both the first and the second argument, but only affect the second one for performative stable point. Now we introduce our model in this paper.
Location-scale distribution map In this paper, we study the family of multi-agent location-scale map for regression problem where a data point consists of d-dimensional feature and scalar outcome, z = (x, y). These are natural classes of distribution maps in which performative effects enter through an additive or multiplicative factor that is linear in ~θ. Definition 2.2. Given d ∈ N and d ≥ 2, and Θn ⊆ Rd, a distribution map D : Θn → Rd × R is a multi-agent location-scale distribution map on n parties if there exists a static distribution DX on Rd+1, θ0 ∈ Rd, and n linear functions Λ1, . . . ,Λn from Rd to Rd so that the distribution of (x, y) ∼ D(~θ) has the following form: The feature is x ∈ Rd and noise x0 ∈ R is jointly sampled from DX . Given feature x ∈ Rd and noise x0 ∈ R, and the the outcome is
y = 〈 θ0 −
n∑ i=1 Λi(θ i),x
〉 + x0.
In this paper, we consider the scaling maps Λi(θ) = λiθ for all θ ∈ Θ with scalar λi > 0 for all i ∈ [d]. We call λ := (λ1, . . . , λn) the influence parameters, and Ln := ∑n i=1 λi collective
influence. Furthermore, we let A := E [ xx> ] ∈ Rd×d be the covariance matrix of the feature, and
b := Aθ0 + E[x0x] ∈ Rd. We will specify the multi agent location-scale distribution map with parameters n, d,λ,A, and b.
When n = 1, our multi-agent location-scale distribution map is a special case of location-scale family in Miller et al. (2021) where the model θ may both the outcome y as well as the feature x.
Predictive Models and Loss Function We consider linear predictive model with constraint where fθ′(x) = 〈θ′,x〉, and the collection of parameter is the d-simplex, Θ = {θ : ∑d k=1 θk = 1, θk ≥ 0}. We use mean squared error to measure a predictive model θ′ ∈ Θ on a distribution map with a deployed model profile ~θ ∈ Θn, `(~θ,θ′) = E(x,y)∼D(~θ)[(y−fθ′(x)) 2] = E(x,y)∼D(~θ)[(y−θ ′ ·x)2].
Given a deployed model profile ~θ and a predictive model θ′, the gradient of the decoupled loss is g(~θ,θ′) := ∇θ′`(~θ,θ′), and ifD is a location-scale distribution map, g(~θ,θ′) = E(x,y)∼D(~θ)[2(θ
′ · x− y)x]. Furthermore, withA and b defined in definition 2.2, the gradient can be written as
g(~θ,θ′) = ∇θ′`(~θ,θ′) = 2A ( θ′ +
∑ i λiθ i
) − 2b. (1)
Additionally, given a deployed model profile ~θ and a predictive model profile ~θ′, we define the gradient of agent i’s decoupled loss as gi(~θ, ~θ′) := g(~θ, (θ′)i), and gi(~θ) := gi(~θ, ~θ) when the deployed model profile is identical to the predictive model profile. We denote the gradient of agent i’s average loss as ḡi(~θ) := ∑ l θ i lg i l( ~θ) for all ~θ ∈ Θn. Finally, we define ~ξ(~θ) = (ξ1, . . . , ξn)
with ξi ∈ Rd so that for all i ∈ [n] and k ∈ [d] ξik(~θ) := θik( ∑ θilg i l − gik). For brevity, we omit ~θ and define ~g := ~g(~θ) and ~ξ := ~ξ(~θ) when there is no ambiguity.

heading: 2.2 LEARNING DYNAMICS
text: We consider the agents myopically use a reinforcement learning algorithm exponentiated gradient for linear regression to improve their predictive models in rounds. We first define the original single agent’s exponentiated gradient for linear regression on a sequence of data points here and will state our dynamics on multi agent performative prediction in section 4. Definition 2.3 (Kivinen & Warmuth (1997)). Given a learning rate η > 0, an initial parameter θ0 ∈ Θ and a sequential of data points (xt, yt)t≥1, the exponentiated gradient descent for linear regression iteratively updates the model as follows: At round t+ 1, with previous parameter θt ∈ Θ the exponentiated gradient algorithm updates it to θt+1 so that
θt+1,k = θt,k exp(−2η(θt · xt − yt)xt,k)∑ l θt,l exp(−2η(θt · xt − yt)xt,l) for all k ∈ [d].
Note that each exponent 2(θt · xt − yt)xt,k is the k-th coordinate of the gradient of squared error `((xt, yt),θt) at θt which yields the name of exponentiated gradient descent.

heading: 2.3 DYNAMICAL SYSTEM
text: Definition 2.4. Let (X , f) be a dynamical system where X is a metric space and f is a mapping on X . We say (x, x′) ∈ X × X is a Li-Yorke pair if
lim inf t dist(f t(x), f t(x′)) = 0 and lim sup t dist(f t(x), f t(x′) > 0.
(X , f) is Li-Yorke chaotic if there is an uncountable set S ⊂ X (scrambled set) such that any pair of points x 6= x′ ∈ S is Li-Yorke pair.

heading: 3 MULTI-AGENT PERFORMATIVE LEARNING: STABILITY AND OPTIMALITY
text: Having introduced multi-agent performative prediction, we show some basic property of our location-scale distribution map with mean squared error as a warm-up. Using the first order condition and a potential function argument, we show 1) the existence of performative stable point in our model (proposition 3.1) and 2) the performative stability and performative optimality are equivalent (proposition 3.2). The proofs of both propositions are in appendix A.
We first show the existence and uniqueness of performative stable point through a potential function argument. The first part is due to the first order condition of convex optimization. The second part also use the first order condition, and ∂
∂θik Φ(~θ) = λig i k( ~θ) for all i ∈ [n] and k ∈ [d].
Proposition 3.1 (existence). Given the family of linear predictive models with constrains Θ, mean squared error ` and multi-agent location-scale distribution map with parameters n, d,λ,A, b in definition 2.2, ~θ∗ on (Θ, `,D) is performative stable if and only if the gradient (defined in eq. (1)) satisfies gik(~θ ∗) ≤ gil(~θ∗) for all i ∈ [n] and k ∈ [d] with θik > 0.
Furthermore, if A is positive definite, there exists a unique performative stable point ~θ∗, and ~θ∗ is also a global minimizer of the following convex function for all ~θ ∈ Θn
Φ(~θ) := ( ∑ i λiθ i)>A( ∑ i λiθ i) + ∑ i λi(θ i)>Aθi − 2b> ∑ i λiθ i. (2)
While model profile is performative stable does not necessary mean the loss is minimized, the following proposition shows that optimality and stability are equivalent in our setting.
Proposition 3.2. Given (Θ, `,D) defined in proposition 3.1, ~θ∗ is performative stable if and only if ~θ∗ is performatively optimal defined in definition 2.1.

heading: 4 MULTI-AGENT PERFORMATIVE LEARNING: CONVERGENCE AND CHAOS
text: In section 3, we study the stability and optimality of location-scale distribution map with mean squared error. Now we ask when each agent myopically improves his predictive model through reinforcement learning but their predictions are performative, what is the long term behavior of the system? Can the system converges to performative stable and optimal point, or behave chaotically?
We provide a threshold result depending on the learning rate and the collective influence Ln. Section 4.1 shows the dynamics converge to the performative stable and optimal point when when the learning rate is small enough. On the other hand, section 4.2 shows the dynamics can have chaotic behavior if the collective influence Ln is large enough.
Now, we define our dynamics (~θt)t≥0 formally. At each round, each agent accesses the data distribution which influenced by their previous model, and updates his model through exponentiated gradient descent. Specifically, given an initial model profile ~θ0 ∈ Θn and a learning rate profile η := (η1, . . . , ηn), each agent i applies the exponentiated gradient descent with initial parameter θi0 and learning rate ηi > 0: At round t + 1 > 1, each agent i use D(~θt) and estimates the gradient of the (expected) loss, gi(~θt) defined in eq. (1), and updates his model according to definition 2.3,
θit+1,k = θit,k exp(−ηigik(~θt))∑d l=1 θ i t,l exp(−ηigil(~θt)) for all t ≥ 0, i ∈ [n], and k ∈ [d]. (3)
We will use superscript to denote agent, i ∈ [n], and subscript for time, t ≥ 0, and index of feature, k, l ∈ [d]. Recall that the gradient of agent i’s average loss is ḡi(~θ) := ∑ l θ i lg i l( ~θ), and eq. (3) can be rewritten as θ i k exp(−ηig i k( ~θt))∑
l θ i l exp(−ηig i l ( ~θt))
= θik exp(ηi(ḡ i(~θt)−gik(~θt)))∑ l θ i l exp(ηi(ḡ i(~θt)−gil (~θt))) . Finally, given ~θ∗ and i ∈ [d],
we define the support of ~θ∗ as Si ⊆ [d] = {k : (θ∗)ik > 0}, and S̄i := [d] \ Si. Then ~θ∗ is an equilibrium (or fixed point) of eq. (3) if
gik( ~θ∗) = ḡi(~θ∗), for all i ∈ [n], k ∈ Si. (4)
We say a fixed point of eq. (3) is isolated if there exists an open set of it so that no other fixed point is in the set. Additionally, the performative stable condition in proposition 3.1 is equivalent to
gik( ~θ∗) = ḡi(~θ∗) and gil(~θ ∗) ≥ ḡi(~θ∗), for all i ∈ [n], k ∈ Si, l ∈ S̄i. (5) Therefore, the set of fixed points of eq. (3) contains the performative stable point.

heading: 4.1 CONVERGING WITH SMALL LEARNING RATE
text: In this section, we show when the learning rate of each agent is small enough the the dynamics in eq. (3) converge to performative stable point. Specifically, if the parameter of multi-agent performative learning (n, d,A,λ) is fixed, the dynamics in eq. (3) converge to performative stable point when η is “small” enough.
By eq. (5), ~θ∗ is a performative stable if the gradient in the support is no less than the average gradient. We call a performative stable point ~θ∗ proper if the gradient of non-support coordinate is greater than the average gradient: for all i ∈ [n] l ∈ S̄i, gil(~θ∗) > ḡi(~θ∗). The below theorem shows if the performative stable point is proper and equilibria satisfying eq. (4) are isolated, eq. (3) converges when maxi ηi is small enough and the ratio of ηi/ηj is bounded for all i and j. Theorem 4.1 (Convergence). Consider a constantRη > 0, and a multi-agent performative learning setting with parameter n, d,A, b,λ such thatA is positive definite, the performative stable point ~θ∗ is proper and its equilibria (defined in eq. (4)) are isolated. There exists η∗ > 0 so that dynamic in eq. (3) with learning rate profile η converges to the performative stable point, limt→∞ ~θt = ~θ∗, if the initial state is an interior point and η satisfies maxi ηi ≤ η∗ and maxi ηi/mini ηi ≤ Rη .
Informally, when the learning rate η are small, ~θt in eq. (3) can be approximated by a solution of an ordinary differential equation, ~ϑ(t‖η‖1), where the initial condition is ~ϑ(0) = ~θ0 and
d dt ϑik(t) = ηi ‖η‖1 ϑik(t)(ḡ i(~ϑ(t))− gik(~ϑ(t))) (6)
for all t ≥ 0, i ∈ [n], and k ∈ [d]. We formalize this intuition in the proof of lemma 4.4. Note that the set of fixed points of eq. (6) is identical to eq. (3) and satisfies eq. (4).
The proof of theorem 4.1 has two parts. First we show the continuous approximation eq. (6) converges to the performative stable point. Then we study the relationship between eq. (3) and eq. (6), and prove the eq. (3) also converges to a performative stable point.
From Potential Function to Convergence of Equation (6) In this section, theorem 4.2 shows the dynamics of eq. (6) converge to performative stable point which will be useful to show the convergence of eq. (3).
Theorem 4.2. If all points satisfying eq. (4) are isolated and A is positive definite, and ~ϑ(0) is in the interior of Θn, the limit limt→∞ ~ϑ(t) = ~θ∗ is the performative stable point.
Theorem 4.2 can be seen as the continuous version of theorem 4.1. Compared to theorem 4.1, theorem 4.2 does not require that the performative stable point is proper, but theorem 4.2 also implicitly requires the ratio of learning rate between any two agents is bounded.
To prove theorem 4.2. we prove lemma 4.3 which shows that Φ in eq. (2) is a potential function for eq. (6) so that time derivative of Φ is decreasing for all non-fixed points. Then, in the proof of theorem 4.2, we further prove that the dynamics in eq. (6) converge to performative stable points when the initial condition ~ϑ(0) is an interior point. The proof is similar to a proof in Kleinberg et al. (2009), and is presented in appendix B.
Lemma 4.3. Given a solution of eq. (6), the time derivative of Φ in eq. (2) is 0 at fixed points of eq. (6), and negative at all other points. Furthermore,
d dt Φ(~ϑ(t)) ≤ −1 2 ∑ i ηi ∑ i λiηi ∑ i,k λiηi|ϑik( ∑ l ϑilg i l − gik)| 2 ≤ −mini λiηi 2 ∑ i ηi ∑ i λiηi ‖~ξ(~ϑ)‖21.
From Approximation to Convergence of Equation (3) Given the convergence of eq. (6), we show the dynamics of eq. (3) also converges to a performative stable point. The argument has two stages. We first show given any neighborhood of performative stable points D, eq. (3) will hits D and stay in D in finite amount of steps in lemma 4.4. Then lemma 4.5 shows that eq. (3) converges to a performative stable point which completes the proof of theorem 4.1. Lemma 4.4. Given any open set D ∈ Θn that contains the performative stable point, there exists η∗ small enough so that for all ~θ0 ∈ Θn, there exists τ so that ~θt ∈ D for all t ≥ τ .
The proof is based on standard approximation result of numerical solution to ordinary differential equations, and is presented in appendix C.
Lemma 4.5. Let ~θ∗ is the performative stable point and D is a small enough neighborhood of ~θ∗. Besides the condition in theorem 4.1, if the initial condition of eq. (3), ~θ0, is in D and ~θt ∈ D for all t ≥ 0, the limit of eq. (3) is the performative stable point limt→∞ ~θt = ~θ∗.
The proof uses the fact that the right-hand side of eq. (3) decreases as the dynamic converges to the fixed point. Therefore, even though the learning rate profile is fixed, the error between eq. (3) and eq. (6) vanishes as they converge to the fixed point. We present the proof in appendix D.

heading: 4.2 CHAOS WITH CONSTANT LEARNING RATE
text: Now we want to ask the converse question in section 4.1. Do the dynamics in eq. (3) still converge, if the learning rate is fixed, as the number of agent increases? Alternatively, do the dynamics converge when the agents have overwhelming influence on the data distribution?
Theorem 4.6 shows that the dynamics is Li-York chaotic whenLn = ∑ i λi is large even with d = 2. Note that large Ln may be due to a fixed number of agent which have overwhelming influence, or the number of agents is large. The later case implies for any small η, no matter how cautious the agents are, as number of agent increases the chaos inevitably occurs. Theorem 4.6. Given a multi-party induced location scale family distribution with A, b, d = 2, and a common learning rate η > 0, if all n agents use the exponentiated gradient with a common learning rate η in eq. (3) and A is diagonally dominant, there exists a carrying capacity L∗ such that if Ln = ∑n i=1 λi ≥ L∗ the dynamics (~θt)t∈N is Li-Yorke chaotic and thus has periodic orbits of all possible periods.
To prove theorem 4.6, we show there exists an uncountable scrambled set defined in definition 2.4. First we consider all agents start from the same initial model, and show the dynamics eq. (3) can be captured by the following function,
fu,v(x) = x
x+ (1− x) exp(u(x− v)) ∀x ∈ [0, 1] (7)
with proper choice of u ∈ R and v ∈ R. Note that v is an equilibrium, and u controls steepness. First, when all agents start from the same initial model, θi0 = θ0 for all i ∈ [n], and use the same learning rate η, their models are identical for all t ≥ 0. For all t there exists θt so that θit = θt for all i. Additionally, since d = 2, we can use a single parameter to encode a linear predictive model with constraints. Given θ ∈ Θ = ∆2, we define p(θ) = θ1 ∈ [0, 1] and omit the input θ when it is clear. Thus, we can rewrite the dynamics as pt = p(θt) which are one-dimensional dynamics on [0, 1], and pt+1 = pt
pt+(1−pt)eη(g i 1( ~θt)−gi2(
~θt)) . We set
α(L) =2η (1 + L) (A1,1 −A1,2 −A2,1 +A2,2) and β(L) = (1 + L)(A2,2 −A2,1) + (b1 − b2)
(1 + L)(A1,1 −A1,2 −A2,1 +A2,2) ,
and write αn = α(Ln) and βn = β(Ln). By direct computation the dynamic of pt is
pt+1 = fαn,βn(pt) (8)
where αn encodes the update pace and βn is an equilibrium of the dynamic. We further set β∞ := A2,2−A2,1 A1,1−A1,2−A2,1+A2,2 and δ(L) := β(L)−β∞ which converges to zero asL→∞. IfA is diagonally dominant α(L) is positive and increasing for all L ≥ 0. Additionally, because A1,1 − A1,2 and A2,2 − A2,1 are positive, we can permute the coordinate so that β∞ ∈ (0, 1/2]. With Li et al. (1982), the lemma below implies the existence of period three points and the proof is in appendix E.
Lemma 4.7. If β∞ ∈ (0, 1/2), there exists a constant L∗ > 0 so that if L ≥ L∗, there exists a trajectory x0, x1, x2, and x3 with fα(L),β(L)(xi) = xi+1 such that x3 < x0 < x1.
Proof of theorem 4.6. First by lemma 4.7, for all L ≥ L∗, there exists a trajectory x0, x1, x2, x3 so that x3 < x0 < x1. Additionally, existence of such trajectory implies the exists of period three points by Li et al. (1982). Finally, by the seminal work of Li & Yorke (1975), it implies that the map is Li-York chaotic.

heading: 5 SIMULATION
text: Now we simulate the one-dimensional dynamics in eq. (8) of one agent with different learning rate η and collective influence L.
We first define a location-scale distribution map. Let the feature x1, x2 and noise x0 are mutually independent Gaussian distribution with zero mean, and the variance are E[x21] = 3, E[x22] = 7, and E[x20] = 1. Finally, θ0 = 0. Therefore,
A = E[xx>] = [ 3 0 0 7 ] , and b = Aθ0 + E[x0x] = [ 0 0 ] .
Given learning rate η > 0, and collective influence L, we have α(L) = 20η(1 + L), and the performative stable point β(L) = 0.7.
The top row of fig. 1 shows the temporal behavior of pt under different (L, η). The bottom row in fig. 1 demonstrates our (convergent and chaotic) results are robust even when the value of gradient is noisy. Specifically, we consider at each round t, instead of gi1(~θt)−gi2(~θt) = 2(1+L)(1,−1)Aθt− 2(1,−1)b, the agent replace A and b with empirical moments on m samples. This process can be seen as a stochastic exponentiated gradient descent which uses a stochastic estimation of the gradient.
We can see chaotic behavior happens in fig. 1c with L = 14 and η = 0.05, and such behavior persists in fig. 1f when the evaluations of gradient are noisy. On the other hand, when the learning rate is small enough (figs. 1a and 1b) the dynamics converge to the performative stable point 0.7. Furthermore, in figs. 1d and 1e the dynamics converge even with noisy estimation of gradient.
Finally, fig. 2 shows the temporal behavior of the loss. Under the same setting as fig. 1c, fig. 2b shows not only the temporal behavior pt is chaotic, but also the mean squared loss. On the other hand, under the same setting as fig. 1a, fig. 2a shows convergent behavior of loss.

heading: 6 CONCLUSION
text: We introduce a framework of multi-agent performative prediction and investigate whether classical reinforcement learning algorithms can converge or behave chaotically depending on the collective influence of the agents model and learning rate. However, we view our example as only scratching the surface of the work of multi-agent performative predictions.
Our framework leads to several new theoretical problems. In particular, it would be interesting to understand whether this threshold is generic and if our results still hold on other reinforcement learning algorithms or other general multi-agent distribution maps. Our framework also provides a new viewpoint to several applications. One natural application is strategic classification. Hardt et al. (2016) In this context, our framework can be seen as strategic learners in strategic classification problem where both data and classifiers are strategic. However, the features also respond to the deployed models in conventional strategic classification, which is not captured in our multi-agent location-scale distribution map. It would be interesting to investigate our dynamics in the context of strategic prediction. Another application is pricing strategy/prediction, where multiple companies predict the demand function and set their prices.
Both our digital and real-world environments are increasingly under the influence of or ever more powerful and numerous ML systems. As these algorithms trigger actions that change the state of the system that produces their joint input data (e.g., AI-triggered ads shown to users affecting their behavior, or automated trading systems affecting stock prices, etc), they are effectively forming closed loop systems and can no longer be understood fully in isolation. As we show in this paper, even fairly simple and innocuous such settings can exhibit phase transitions going from optimal behavior to chaos. We believe such phenomena are worthy of a careful investigation and we hope that this paper sets out some useful building blocks by bringing together optimization/performance analysis with Lyapunov theory and chaos theory.
ETHICS STATEMENT
Our work showcases the possibility of competing prediction algorithms leading to instability and chaos. Extra steps should be taken, whenever possible, so that related systems operate within the range of parameters leading to stability. We hope that our work helps both by identifying a potential threat for ML systems as well as providing some guidance on how to counter or minimize it.
REPRODUCIBILITY
All of our theoretical results are stated fully, including previous definitions and results on which they are based. They are accompanied by proofs, either in the main paper or in the appendix. The setting of our simulation results are stated fully in the main paper.

heading: A PROOFS AND DETAILS IN SECTION 3
text: Proof of proposition 3.1. First under the mean squared loss function, each agent i’s decoupled performative loss function `(~θ′,θi) is convex in θi. Thus, for linear predictive model, we can apply the KKT conditions on definition 2.1 so that a collection of predictive models ~θ ∈ Θn is performatively stable if and only if for all i ∈ [n], k ∈ [d] with θik > 0, ∂∂θik `( ~θ′,θi) ≤ ∂ ∂θil
`(~θ′,θi) for all l ∈ [d] where ~θ′ = ~θ. Therefore, with eq. (1), ~θ∗ is performative stable if
gik( ~θ∗) ≤ gil(~θ∗) (9)
holds for all i ∈ [n] and k ∈ [d] with θik > 0.
With eq. (9), we now show that there exists a unique performative stable point ~θ∗ by proving that 1) Φ in eq. (2) is strictly convex, and 2) ~θ∗ is a minimizer of Φ. First, to show Φ is strictly convex, it is sufficient to show the Hessian of Φ positive definite. Because Φ is a quadratic function on Θn, the Hessian of Φ is a constant matrix in Rnd×nd By the partial derivative of eq. (2), for all i, j ∈ [n] and k, l ∈ [d], we have (∇2Φ)ik,jl = ∂ 2
∂θik∂θ j l Φ = 2λiλjAk,l if i 6= j and (∇2Φ)ik,il = 2λi(λi+ 1)Ak,l. Let L ∈ Rn×n with Lij = 2λiλj if i 6= j and 2λi(1 +λi) which is positive definite because λi > 0 for all i ∈ [n]. Then, the Hessian of Φ is the Kronecker product of L andA,
∇2Φ = 2λ1(1 + λ1)A . . . 2λ1λnA... . . . ... 2λnλ1A . . . 2λn(1 + λn)A  = L⊗A. Because L and A are both positive definite, the Hessian is also positive definite. Therefore, Φ is strictly convex, and there exist a unique minimum of Φ in the compact set Θn. Now we show ~θ∗ is performative stable if and only if ~θ∗ is a minimizer of Φ. By the first order condition and the partial derivative of eq. (2), the minimum of eq. (2) at ~θ∗ if and only if gik(~θ
∗) ≤ gil(~θ∗) for all i ∈ [n] k, l ∈ [d] with (θ∗)ik > 0. Therefore, ~θ∗ is the minimum of Φ if and only if ~θ∗ is a performative stable point.
Proof of proposition 3.2. Given a profile of models ~θ, the total cost is∑ i `(~θ, (θ)i) = ∑ i E(x,y)∼D(~θ)[(y− θ i · x)2]
= ∑ i E
 〈x,θ0 −∑
j
λjθ j − θi 〉 + x0 2 
which is a convex function on ~θ ∈ Θn. Additionally,
∂
∂θik ∑ ı `(~θ,θı) = (1 + λi)g i k( ~θ, ~θ) + ∑ ı∈[n]:ı6=i λig i k( ~θ, ~θ) = (1 + nλi)g i k( ~θ, ~θ)
which is the gradient of decoupled performative loss scaled by (1 + nλi). Thus, we can apply the KKT conditions and the minimum happens if and only if eq. (9) holds.

heading: B PROOF AND DETAILS FOR THEOREM 4.2
text: Proof of lemma 4.3. By chain rule,
d dt Φ(~ϑ(t)) = ∑ i∈[n],k∈[d] ∂ ∂θik (~ϑ(t)) · d dt ~ϑ(t), (10)
so the time derivative of the potential function is zero if the dynamics is at a fixed point of eq. (6).
Now we compute a closed form of the time derivative and show the derivative is zero only if the dynamics is at a fixed point of eq. (6). Here we omit the input t to simplify the notation.
d dt Φ(~ϑ(t)) = ∑ i,k ∂ ∂θik (~ϑ(t)) · ηi ‖η‖1 ϑik(t)( ∑ l ϑil(t)g i l( ~ϑ(t))− gik(~ϑ(t))) (by eqs. (6) and (10))
= 1
‖η‖1 ∑ i λiηi (∑ k ( gik ) · ϑik (∑ l ϑilg i l − gik )) (by the partial derivative of eq. (2))
= 1
2‖η‖1 ∑ i λiηi ∑ k,l∈[d] ϑikϑ i l(2g i kg i l − 2(gik)2) (because ∑ l ϑ i l = 1)
= −1
2‖η‖1 ∑ i λiηi ∑ k,l∈[d] ϑikϑ i l(g i k − gil)2
Now we bound the time derivative.
− 2‖η‖1 (∑ i λiηi ) d dt Φ(~ϑ(t))
=  ∑ i∈[n],k,l∈[d] λiηiϑ i kϑ i l  ∑ i∈[n],k,l∈[d] λiηiϑ i kϑ i l(g i k − gil)2  (∑k ϑik = ∑l ϑil = 1) ≥
 ∑ i∈[n],k,l∈[d] λiηiϑ i kϑ i l|gik − gil | 2 . (by Cauchy inequality) ≥
 ∑ i∈[n],k∈[d] λiηi ∣∣∣∣∣∣ϑik ∑ l∈[d] ϑil(g i k − gil) ∣∣∣∣∣∣ 2 (by triangle inequality)
Therefore, ddtΦ( ~ϑ(t)) = 0 only if ϑik ( gik − ∑ l∈[d] ϑ i lg i l ) = 0 for all i ∈ [n] and k ∈ [d] which is a fixed point of eq. (6).
We can further simplify the bound by ~ξ. Because ∑ i,k λiηi|ϑik( ∑ l ϑ i lg i l − gik)| ≥
(mini λiηi) ∑ i,k |ξik(~ϑ)| = (mini λiηi) ‖~ξ(~ϑ)‖1, d dtΦ(
~ϑ(t)) ≤ −mini λiηi2∑i ηi∑i λiηi ‖~ξ(~ϑ)‖21. Proof of theorem 4.2. When the fixed points are isolated satisfying eq. (4), by lemma 4.3, the dynamics in eq. (6) converges to a fixed point of eq. (6), ~θ∗ ∈ Θn. Because ~θ∗ is a fixed point, for all i ∈ [n], k ∈ [d],
(θ∗)ik ( ḡi(~θ∗)− gik(~θ∗) ) = (θ∗)ik ∑ l (θ∗)ilg i l( ~θ∗)− gik(~θ∗) = 0
By proposition 3.1, the fixed point condition implies each coordinate of the gradient of loss in the support are identical, gik(~θ
∗) = ḡi(~θ∗) for all i and k ∈ Si. Thus, if the fixed point ~θ∗ is not performative stable, there exists ı and κ with (θ∗)ıκ = 0 so that g ı κ( ~θ∗) < ḡı(~θ∗). Furthermore,
exp(−ηıgıκ(~θ∗)) > ∑ l(θ ∗)ıl exp(−ηıgıl(~θ∗)). We can pick a small enough > 0 and define
U := {~θ : exp(−ηıgıκ) > ∑ l θıl exp(−ηıgıl) + } (11)
which contains ~θ∗ and is an open set because ~g and the exponential function are continuous. Since ~ϑ(t) converges to ~θ∗ as t → ∞, there exists a time t so that for all t ≥ t , ~ϑ(t) ∈ U . However, if ~ϑ(t) ∈ U and ~ϑ(t) is an interior point, we get ddtϑ i k(t) > 0 by eqs. (6) and (11). Therefore, ϑik(t) is positive and increasing for t ≥ t . We reached a contradiction because ϑik(t)→ (θ∗)ik = 0. Therefore, ~θ∗ is a performative stable point.

heading: C PROOF ANS DETAILS FOR LEMMA 4.4
text: To prove lemma 4.4, show the dynamic eq. (3) can be approximated by eq. (6) and the error vanishes as η∗ decreases. Thus, we can show the dynamic can hit an arbitrary neighborhood of the performative stable point. We further use Φ to show the dynamic will stay in the neighborhood. Below we state two ancillary lemmas to control the error of our approximation.
We define an error vector ~e(~θ) ∈ Rn×d between eqs. (3) and (6) so that
η2i e i k( ~θ) :=
θik exp(ηi(ḡ i − gik))∑
l θ i l exp(ηi(ḡ i − gil)) − θik − ηiξik
We omit the input ~θ of ~e and ~et := ~e(~θt) when there is no ambiguity. We show if the the error vector is small, Φ is decreasing in dynamics eq. (3).
Claim C.1 (Approximated potential). There exist C4, so that for all t and ~θ0 ∈ Θn, the difference of eq. (2) on eq. (3) satisfies
Φ(~θt+1)− Φ(~θt) ≤ −mini λ2i η2i 2 ∑ i λiηi ‖~ξt‖21 + max i λiη 2 i max i,k,~θ |gik(~θ)| · ‖~et‖1 + d2C4 ∥∥∥~θt+1 − ~θt∥∥∥2 1 .
Claim C.2. If maxi ηi is small enough and satisfies eq. (12), there exists a constant C so that
|eik(~θ)| ≤ C for all i ∈ [n], k ∈ [d], and ~θ ∈ Θn.
The proofs of these two claims are based on first order approximation.
Proof of claim C.1. By the partial derivative of eq. (2), we have ∂ 2
∂θik∂θ j l
Φ(~θ) = 2λiλjAl,k if i 6= j
and ∂ 2
∂θik∂θ i l Φ(~θ) = 2λi(1 +λi)Al,k. Thus, the second order partial derivatives of Φ can bounded by the twice of C4 := maxı λı(λı + 1) maxk,lAk,l. By Taylor’s expansion, we have
Φ(~θt+1)− Φ(~θt) ≤∇Φ(~θt) · ( ~θt+1 − ~θt ) + d22C4
2 ∥∥∥~θ(t+ 1)− ~θ(t)∥∥∥2 2
≤ ∑
i∈[n],k∈[d]
λig i k( ~θt)(ηiξ i k( ~θt) + η 2 i e i k( ~θt)) + d 2C4 ∥∥∥~θ(t+ 1)− ~θ(t)∥∥∥2 1
(by the partial derivative of eq. (2)) = ∑
i∈[n],k∈[d]
λiηig i t,kξ i t,k + λiη 2 i g i t,ke i t,k + d 2C4 ∥∥∥~θt+1 − ~θt∥∥∥2 1
≤ −1 2 ∑ i λiηi ∑ i,k λiηi|ξit,k| 2 + ∑ i∈[n],k∈[d] λiη 2 i g i t,ke i t,k + d 2C4 ∥∥∥~θt+1 − ~θt∥∥∥2 1 (by lemma 4.3)
Therefore, we have
Φ(~θt+1)− Φ(~θt) ≤ −mini λ2i η2i 2 ∑ i λiηi ‖~ξt‖21 + max i λiη 2 i max i,k,~θ |gik(~θ)| · ‖~et‖1 + d2C4 ∥∥∥~θt+1 − ~θt∥∥∥2 1
which completes the proof.
Proof of claim C.2. By if η∗ is small enough and satisfies eq. (12), we have ηi(ḡi − gik) ≤ 1, and θik+ηiθ i k(ḡ i−gik) ≤ θikeηi(ḡ i−gik) ≤ θik+ηiθik(ḡi−gik)+ e2η 2 i θ i k(ḡ
i−gik)2 for all i, k and ~θ ∈ Θn. Additionally, with ξik = θ i k(ḡ i − gik), we can rewrite it as
θik ≤ θikeηi(ḡ i−gik) − ηiξik ≤ θik +
e 2 η2i θ i k(ḡ i − gik)2.
Therefore, the error can be upper bounded as
η2i e i k ≤
θik + ηiξ i k + e 2η 2 i θ i k(ḡ i − gik)2∑ l θ i l + ηiξ i l − (θik + ηiξik) = e 2 η2i θ i k(ḡ i − gik)2,
because ∑ l θ i l = 1 and ∑ l ξ i l = 0. For lower bound, we have,
η2i e i k ≥
θik + ηiξ i k∑
l θ i l + ηiξ i l + e 2η 2 i θ i l(ḡ i − gil)2 − (θik + ηiξik) ≥ −(θik + ηiξik) ( eη2i 2 ∑ l θil(ḡ i − gil)2 ) .
If we set C := emax~θ ∣∣∑ l θ i l(ḡ i − gil)2 ∣∣, because |ηiξik| ≤ ηi2 maxk |gik| ≤ 1 by eq. (12) and
θik ≤ 1, we have ∣∣∣eik(~θ)∣∣∣ ≤ C.
Proof of lemma 4.4. Because D is open, we can set D′ so that ~θ∗ ∈ D′, D′ ⊂ D, and sup~θ∈D′ Φ( ~θ) < 12 inf ~θ/∈D Φ( ~θ). We will pick η∗ small enough so that ~θt+1 ∈ D for all ~θt ∈ D′ ⊂ D. The proof has two parts: we first show the dynamics eq. (3) hits the set D. Then we prove eq. (3) stays in D afterward.
By theorem 4.2, there exists τ so that ~ϑ(τ) ∈ D′. Now by Gronwall’s inequality we can set η∗ small enough so that ~θτ/‖η‖1 ∈ D. Formally, given the dynamics in eq. (3), we define right-continuous step functions ~θ(t) = ~θbtc and ~e(t) := ~e(~θbtc) for all t ≥ 0. Then the dynamics in eq. (3) can be written as θik(t)− θik(0) = t−1∑ s=0 (θis+1,k − θis,k) = t−1∑ s=0 ( ηiξ i k( ~θs) + η 2 i e i k( ~θs) ) = ηi ∫ t 0 ξik( ~θ(s)) + ηie i k(s) ds
On the other hand, the solution of eq. (6) can be written as
ϑik(ηit)− ϑik(0) = ηi ‖η‖1
∫ t ‖η‖1
0
ξik( ~ϑ(s)) ds = ηi ∫ t 0 ξik( ~ϑ(‖η‖1s)) ds
Because ξik are continuous and Θ n is compact, there exists L > 0 so that ξik is L-Lipschitz with respect to one norm for all i and k. Thus, the difference between above equations is∣∣θik(t)− ϑik(‖η‖1t)∣∣ ≤ηi ∫ t 0 ∣∣∣ξik(~θ(s))− ξik(~ϑ(‖η‖1s))∣∣∣ ds+ η2i ∫ t 0 |eik(s)| ds
≤ηiL ∫ t
0
∥∥∥~θ(s)− ~ϑ(ηis)∥∥∥ 1 ds+ η2iCt (L-Lipschitz and claim C.2)
Therefore, by Gronwall’s inequality and ηi ≤ η∗, we have∥∥∥~θ(t)− ~ϑ(‖η‖1t)∥∥∥ 1 ≤ η∗ndL ∫ t 0 ∥∥∥~θ(s)− ~ϑ(‖η‖1s)∥∥∥ 1 ds+ (η∗) 2ndCt ≤ (η∗)2ndCteη∗ndLt
Because ~ϑ(τ) ∈ D′, we can pick η∗ small enough so that ~θ(τ/‖η‖1) = ~θbτ/‖η‖1c ∈ D and Φ(~θbτ/‖η‖1c) < inf ~θ/∈D Φ( ~θ).
Now we show the second part that ~θt ∈ D for all t ≥ bτ/‖η‖1c. First, with claim C.1, we will prove that the potential function is decreasing for all ~θt /∈ D′ when η∗ small enough. We estimate three terms in claim C.1 separately. First, because ~θ∗ ∈ D′ and Θn\D′ is compact, min~θ/∈D′ ‖~ξ(~θ)‖1 > 0 exists. Then mini λ 2 iη 2 i
2 ∑ i λiηi ‖~ξt‖21 = Ω(maxi ηi) By claim C.2, maxi λiη2i maxi,k,~θ |g i k( ~θ)| · ‖~et‖1 =
O(maxi η 2 i ). Finally, d 2C4 ∥∥∥~θt+1 − ~θt∥∥∥2 1 = O(maxi η 2 i ). Therefore, there exists η∗ small enough so that the potential function Φ(~θt+1) − Φ(~θt) < 0 for all ~θt /∈ D′ and η. Therefore Φ(~θt) < min~θ/∈D Φ( ~θ) for all t ≥ bτ/‖η‖1c which completes the proof.

heading: D PROOFS AND DETAILS FOR LEMMA 4.5
text: Lemma 4.3, shows the value of Φ is decreasing in eq. (6), and the decrease rate is lower bounded by the one norm of ~ξ. Thus, if we can show the error between eq. (3) and eq. (6) is bounded by ‖~ξ‖1, we have the value of Φ is also decreasing on eq. (3). The main challenge is that because ~ξ(~θ∗) = 0, we need to control the error as ~ξ converges to zero but η∗ is fixed.
We first show three ancillary claims, claim D.1 to D.3. Claim D.1 show the vanishing components of ~θt decrease rapidly once the dynamic is inD. Claim D.2 and D.3 show the supporting component also decrease once the vanishing components are small enough.
Given (n, d,A,λ), we define the following constants C1 := 14 maxi,l,θ∈Θn |g i l |, C2 := 2mini,k(θ∗)ik , C3 := edmax(C1, C2), and C4 := maxı λı(λı+1) maxk,lAk,l. We require the maximum learning rate is bounded by η∗ which satisfies the following conditions.
η∗ max i,k,~θ∈Θn
|gik(~θ)| ≤ 1
2 (12)
η∗ndC3 max ~θ ‖~ξ(~θ)‖1 ≤ 1 (13)
Additionally, given the bound of learning rate ratio, maxi ηimini ηi ≤ Rη , we requires
R2ηη 3 ∗ <
mini λ 2 i 16 ∑ i λi min
{ 4
C3 maxi(λi) max~θ ‖~g‖1 ,
1
d2C4
} (14)
Note that max η 3 i
min η2i is less then the right hand side of eq. (14). On the other hand, by lemma 4.4, we
can pick D small enough so that the following conditions holds.
1 2 min i∈[n],k∈Si (θ∗)ik ≤ min i∈[n],k∈Si,~θ∈D θik (15)
We first show for all i and k ∈ S̄i, θit,k is decreasing and converges to zero exponentially fast as t increases. Because ~θ∗ is a proper performative stable, ∑ l(θ ∗)ile −ηigil (~θ ∗) = e−ηiḡ i(~θ∗) > e−ηig i k( ~θ∗) for all i and k ∈ S̄i. We can take η∗, 1, and D small enough so that for all ~θ ∈ D and all learning rate profile η with max ηi ≤ η∗,
e−ηig i k < (1− 1) ∑ l θile −ηigil , i ∈ [n], k ∈ S̄i (16)
Claim D.1 (Vanishing components). Given η∗, 1, and D in eq. (16), if ~θt ∈ D for all t ≥ 0, for all i ∈ [n] and k ∈ Si, θik(t) is decreasing in t and for all t ≥ 0
0 ≤ θit,k ≤ θi0,ke− 1t.
Proof of claim D.1. By eq. (16), for all t ≥ 0, θit+1,k = θit,k exp(−ηigit,k)∑ l θ i t,l exp(−ηig i t,l) ≤ (1 − 1)θit,k. Therefore, θit,k is decreasing, and θ i t,k ≤ θi0,ke− 1t.
Claim D.2. There exists a constant C3 such that for all ~θ ∈ Θn with δ1 > 0 so that ‖~ξ(~θ)‖1 ≥ 2 √ δ1, and |ξik(~θ)| ≤ δ1 for all i ∈ [n] and k ∈ S̄i, then
|eik(~θ)| ≤ C3‖~ξ(~θ)‖21, (17)
for all i ∈ [n] and k ∈ [d].
Claim D.2 shows if the one norm of ~ξ is much bigger than the vanishing components, the error term ~e can be bounded by the ‖~ξ‖21. Moreover, claim D.1 ensures that the vanishing components decrease rapidly, so the condition of claim D.2 readily holds.
Proof of claim D.2. Given ~θ and δ1 > 0 that satisfy the condition, we first show two inequalities to bound θik(ḡ
i − gik)2 for supporting and vanishing component respectively. For a vanishing component k ∈ S̄i,
θik(ḡ i − gik)2 ≤ max i,l,θ∈Θn |gil | · |θik(ḡi − gik)| ≤ 4C1 · δ1 ≤ C1‖~ξ‖21. (18)
Then for a supporting component k ∈ Si, with eq. (15) we have
θik(ḡ i − gik)2 ≤
1
mini,l,~θ∈D θ i l
(θik(g i − gik))2 ≤
2
mini,k(θ∗)ik |ξik|2 ≤ C2‖~ξ‖21. (19)
Now we use above two inequalities to approximate eq. (3). For nominator, because 1 + x ≤ exp(x) ≤ 1+x+ e2x
2 for all x ≤ 1, θik exp(ηi(ḡi−gik)) ≥ θik+ηiθik(ḡi−gik) = θik+ηiξik. On the other hand, because ηi(ḡi−gik) ≤ 1 by eq. (12), θik exp(ηi(ḡi−gik)) ≤ θik+ηiξik+ e2θ i kη 2 i (ḡ
i−gik)2. By eqs. (18) and (19), we have
0 ≤ θikeηi(ḡ i−gik) − θik − ηiξik ≤
e 2 max(C1, C2)η 2 i ‖~ξ‖21 (20)
For denominator, we sum over eq. (20). Because ∑ l θ i l = 1 and ∑ l θ k l (ḡ i − gil) = 0, we have
0 ≤ ∑ l θile ηi(ḡ i−gil ) − 1 ≤ ed 2 max(C1, C2)η 2 i ‖~ξ‖21 (21)
Given i ∈ [n] and k ∈ [d], we apply the above equation to eq. (3). For upper bounds, we have
η2i e i k( ~θt) =
θik exp(ηi(ḡ i − gik))∑
l θ i l exp(ηi(ḡ i − gil)) − θit,k − ηiξit,k
≤θit,ke−ηig i k( ~θt) − θit,k − ηiξit,k (by eq. (21))
≤emax(C1, C2) 2 η2i ‖~ξ‖21 (by eq. (20))
For lower bounds,
η2i e i k( ~θt) =
θik exp(ηi(ḡ i − gik))∑
l θ i l exp(ηi(ḡ i − gil)) − θit,k − ηiξit,k
≥ θit,k + ηiξ i t,k
1 + edmax(C1,C2)2 η 2 i ‖~ξ‖21
− θit,k − ηiξit,k (by eqs. (20) and (21))
≥− (θit,k + ηiξit,k) ( edmax(C1, C2)
2 η2i ‖~ξ‖21
) (1/(1 + x) ≥ 1− x)
≥− edmax(C1, C2)η2i ‖~ξ‖21 (θit,k ≤ 1 and ηiξit,k ≤ 1 by eq. (12)) Therefore, with C3 := edmax(C1, C2) we finish the proof. Claim D.3. There exists 2 > 0 so that for all ~θt ∈ Θn and δ1 > 0 so that ‖~ξ(~θt)‖1 ≥ 2 √ δ1, and |ξik(~θt)| ≤ δ1 for all i ∈ [n] and k ∈ S̄i, then Φ(~θt+1)− Φ(~θt) ≤ 2‖~ξ(~θt)‖21.
Proof for claim D.3. By claim C.1,
Φ(~θt+1)− Φ(~θt) ≤ −mini λ2i η2i 2 ∑ i λiηi ‖~ξt‖21 + max i λiη 2 i max i,k,~θ |gik(~θ)| · ‖~et‖1 + d2C4 ∥∥∥~θt+1 − ~θt∥∥∥2 1 .
We can bound the later two terms by claim D.2. For the second term, ‖~et‖1 ≤ ndC3‖~ξt‖21. For the third term, ∥∥∥~θt+1 − ~θt∥∥∥
1 ≤ ∑ i,k ( ηi|ξit,k|+ C3η2i ‖~ξ‖21 ) ≤max
i ηi‖~ξ‖1 + ndC3 max i η2i ‖~ξ‖21.
≤2 max i ηi‖~ξ‖1 ( by eq. (13))
With above inequalities, by eq. (14), we have mini λ 2 iη 2 i 4 ∑ i λiηi > maxi λiη 2 i maxi,k,~θ |g i k( ~θ)|ndC3 and mini λ 2 iη 2 i
4 ∑ i λiηi > 4d2C4 maxi η 2 i . Therefore there exists a constant
2 := mini λ
2 i η 2 i 2 ∑ i λiηi −max i λiη 2 i max i,k,~θ |gik(~θ)|ndC3 − 4d2C4 max i η2i > 0
so that Φ(~θt+1)− Φ(~θt) < − 2‖~ξt‖21.
Proof of lemma 4.5. To prove limt→∞ ~θt = ~θ∗, there are two equivalent ways to measure the progress, besides ‖~θt − ~θ∗‖1. First because ~θ∗ is an isolated fixed point of eq. (6), ~θt converges to ~θ∗ if and only if limt→∞ ~ξ(~θt) = ~0. On the other hand, because Φ is strictly convex and and ~θ∗ is the minimum point, ~θt converges to ~θ∗ if and only if limt→∞Φ(~θt) = min~θ Φ(
~θ). With these two equivalent conditions, given any > 0, there exists δ > 0 so that ‖~θ − ~θ∗‖1 < when
~θ ∈ Vδ := { ~θ : Φ(~θ) ≤ max
~θ′:‖~ξ(~θ′)‖1≤δ Φ(~θ′)
} .
Therefore, it is sufficient for us to show for all δ > 0, there is tδ so that ~θt ∈ Vδ for all t ≥ tδ . With technical claim D.1 to D.2, our proof has two parts. First we show that the dynamic hits Vδ . Then, the dynamic stays in Vδ .
For the first part, given δ > 0 and 0 < C < 1, by claim D.1 there exists T1 such that each vanishing component |ξit,k| ≤ C2δ2/4 for all t ≥ T1. Then by claim D.3, there exists T2 ≥ T1 such that ‖~ξT2‖1 ≤ Cδ. Otherwise, the value of Φ decreases by a nonzero constant 2‖~ξt‖21 ≥ C 2δ2 > 0 at each round which contradicts that the minimum of Φ bounded.
For the second part, if ‖~ξt‖1 ≤ Cδ ≤ δ for all t ≥ T2, then we finish the proof. Otherwise, there exists τ ≥ T2 so that ‖~ξτ‖1 ≤ Cδ < ‖~ξτ+1‖1. Now we prove that Φ(~θτ+1) ≤ max~θ′:‖~ξ(~θ′)‖1≤δ Φ(
~θ′). Because the difference between ~θτ+1 and ~θτ is ‖~θτ+1 − ~θτ‖1 ≤ maxi ηi‖~ξτ‖1 +maxi η2i ‖~eτ‖1 ≤ 2 maxi ηi‖~ξτ‖1 when η∗ is small enough, and ~ξ is a Lξ-Lipschitz ~θ for some constant Lξ in one norm, we have
Cδ < ‖~ξτ+1‖1 ≤ ‖~ξτ‖1 + ‖~ξτ+1 − ~ξτ‖1 ≤ ‖~ξτ‖1 + 2Lξ max i ηi‖~ξτ‖1 ≤ δ, (22)
when C is small enough so that C(1 + 2Lξ maxi ηi) ≤ 1. Therefore, ‖~ξτ+1‖1 ≤ δ and Φ(~θτ+1) ≤ max~θ′:‖~ξ(~θ′)‖1≤δ Φ(
~θ′). Finally, because |ξit,k| ≤ C2δ2/4 for all t ≥ τ + 1, by claim D.3, the potential function is decreasing for all t ≥ τ + 1, unless ‖~ξ‖t ≤ Cδ. Both make the potential function less than max~θ′:‖~ξ(~θ′)‖1≤δ Φ( ~θ′) which completes the proof.

heading: E PROOF AND DETAIL FOR THEOREM 4.6
text: Proof of lemma 4.7. Define PL(x) := α(L)(x−β(L)) which is increasing for allL because α(L) > 0. With PL, fα(L),β(L)(x) = xx+(1−x) exp(PL(x)) . Take x1(L) = x1 := 1−1/α(L), x2(L) = x2 := fα(L),β(L)(x1(L)), and x3(L) = x3 := fα(L),β(L)(x2(L)). We will define x0(L) later. We will omit L and use x1, x2, and x3.
To define x0(L), we set y(L) := β(L)/2, and want to show
fα(L),β(L)(y) > x1, (23)
which is equivalent to (α(L)− 1)(1− y(L)) exp(PL(y(L))) < y(L). When L is large enough, we have β(L) ∈ ( 2β∞3 , 4β∞ 3 ). Additionally because α(L) > 0, we have PL(y(L)) = − 1 2α(L)β(L) < − 13α(L)β∞. Therefore, we have (α(L) − 1)(1 − y(L))e PL(y(L)) ≤ α(L)e−α(L) β∞ 3 < β∞3 < y(L) when L is large enough, and prove eq. (23). On the other hand, because β(L) < 43β∞ and
PL(β(L)) = 0, we have fα(L),β(L)(β(L)) = β(L) < 12 (β∞+1). Moreover, 1 2 (β∞+1) < 1− 1 α(L) , holds when L is large enough. These two imply
fα(L),β(L)(β(L)) = β(L) < x1(L). (24)
Combining eqs. (23) and (24), by intermediate value theorem, there exists x0 such that
fα(L),β(L)(x0) = x1 with y < x0 < β(L) < x1. (25)
Now we show x3 < x0. With 1−x1(L) = 1/α(L) and 0 < x1 < 1, we have x2 = fα(L),β(L)(x1) = x1
x1+α(L)−1 exp(PL(x1)) ≤ α(L)exp(PL(x1)) . Because β∞ < 1/2, when L is large enough, x1(L) =
1− 1α(L) > 1 4 (2β(L) + 3) and, thus, PL(x1) > α(L) ( 3 4 − β(L) 2 ) . Therefore, we have
x2 ≤ α(L) exp ( −α(L) ( 3
4 − β(L) 2
)) (26)
Finally, because PL(x2) ≥ PL(0) = −β(L), we get
x3 =fα(L),β(L)(x2) ≤ x2
x2 + (1− x2) exp(−α(L)β(L))
= x2 exp(α(L)β(L))
1 + x2(exp(α(L)β(L))− 1) ≤x2 exp(α(L)β(L)) (since exp(α(L)β(L)) > 1 when L is large)
≤α(L) exp ( α(L) ( β(L)− ( 3
4 − β(L) 2
))) (eq. (26))
=α(L) exp
( 3α(L)
2
( β(L)− 1
2 )) Finally, because β∞ < 1/2, x3 converges to 0 when L is large enough. Therefore,
x3 < y < x0. (27)
By eqs. (25) and (27), we have x3 < x0 < x1 which completes the proof.

Review summaries:
This paper studied the different behaviours of using exponentiated gradient descent (Def. 2.3) in linear regression with different learning rates. The setting is called performative prediction, which can be viewed as a special case of reinforcement learning (after the model makes a prediction, the environment returns a feedback by changing the data distribution).  The main results consist of two parts, for small enough and large learning rates:  (i) with small enough learning rate, the authors proved that the exponentiated gradient descent is "stable" (asymptotically converges to some global minimizer). The proof is based on standard analysis of studying a potential (surrogate/Lyapunov) function for the mean squared error, and arguing that the gradient flow vanishes only if the potential approaches $0$, which implies that the convergence of the flow. Then the discrete gradient update is approximating the flow well if the stepsize is small enough.  (ii) if the learning rate is larger than some threshold value, the authors then showed that the exponentiated gradient descent became Li-Yorke chaotic, where it can periodically oscillate for infinitely many times. The main idea is to use Eq. (7) to characterize the dynamics, and show that under some conditions Eq. (7) induces a sequence of { x_i }_{ i >= 1}, with some recurrent behaviours as shown in Lemma 4.7.  The authors then verified the theoretical findings using simulations on simple examples.

The paper analyzes the performative prediction setting (Perdomo 2020) where multiple agents perform gradient descent to converge to a performatively optimal point. The agent are modeled by constrained linear predictive models which are used for linear regression.  The authors show that the learning dynamics  converges to the multi-agent performatively stable point for small learning rates.  The stable point coincides with the optimal point where the sum of the agent's losses are minimized.  The requirement for convergence is that the hessian of the loss must be positive definite, which is satisfied by existence of a potential function.  The authors also show  that the dynamics exhibits Li-York chaos for large enough learning rates.