# Multi-agent Performative Prediction: From Global Stability and Optimality to
Chaos111This research-project is supported in part by the National Research
Foundation, Singapore under NRF 2018 Fellowship NRF-NRFF2018-07, AI Singapore
Program (AISG Award No: AISG2-RP-2020-016), NRF2019-NRF-ANR095 ALIAS grant,
AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science,
Technology and Research (A*STAR), grant PIE-SGP-AI-2018-01 and Provost’s Chair
Professorship grant RGEPPV2101.

Georgios Piliouras SUTD<EMAIL_ADDRESS>Fang-Yi Yu Harvard University,
<EMAIL_ADDRESS>
###### Abstract

The recent framework of performative prediction [28] 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.

##  1 Introduction

Performative prediction [28] 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, [28] 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:

######  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?

###  1.1 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_ which is a map 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 this 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. The influence of
agent $i\in[n]$ on the outcome distribution is his model weighted by a scalar
$\lambda_{i}>0$. When $n=1$, our multi-agent location-scale distribution map
is a special case of location-scale family in Miller et al. [25]. In the
market example, each hedge fund company predicts the price (outcome) based on
macroeconomic data or other information (features). These influence parameters
$\lambda_{1},\dots,\lambda_{n}$ can be seen as each hedge fund’s capital that
can influence the future price.

Moreover, the agents often cannot know the distribution map that captures the
dependency between their model and the data distribution. Therefore, we
consider that the agents use a reinforcement learning algorithm, exponentiated
gradient for linear regression [17], to myopically and iteratively improve
their predictive models in rounds. We study the long-term behavior and ask if
the system converges to the performative stable and optimal point, or behaves
chaotically.

###  1.2 Our results

We first study the basic properties of our multi-agent preformative prediction
with a multi-agent location-scale distribution map. We show 1) the existence
of performative stable point in our setting (LABEL:prop:existence) and 2) the
performative stability and performative optimality are equivalent
(LABEL:prop:stable2optimal). 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 where the agents use reinforcement learning algorithms, and study
their long-term behavior. We provide a threshold result on the learning rates
of exponentiated gradient descent and the collective influence:
LABEL:thm:converge shows the dynamics of exponential gradient descent converge
to the performative stable and optimal point when the learning rate is small
enough fixing agents’ influence parameters $\lambda_{1},\dots,\lambda_{n}$.
Our convergence result in LABEL:thm:converge 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 [28, 25, 24] 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 $\sum_{i}\lambda_{i}$ is large enough for any fixed
learning rate. Specifically, LABEL:thm:chaos_one shows that even when the
feature space is in $\mathbb{R}^{2}$ these systems provably exhibit Li-Yorke
chaos, when the collective influence $\sum_{i}\lambda_{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.
(LABEL:def:chaos) The chaotic result in LABEL:thm:chaos_one 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, LABEL:thm:chaos_one shows that chaos is inevitable
in some performative predictions settings when the number of agents exceeds a
carrying capacity. After that, the system becomes unpredictable with small
perturbations exploding exponentially fast. Though our chaotic result closely
follows Chotibut et al. [10], we need a new proof for the existence of period
three orbits, because the fixed point of our dynamics changes as the total
influence $\sum_{i}\lambda_{i}$ increases.

Finally, section 5 provides numerical examples of our dynamics and shows
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 [28]. The original work
and several follow-ups study the discrepancy between performative stability
and performative optimality and prove approximated convergence of learning
dynamics, e.g., stochastic gradient descent, or iterative empirical risk
minimization. [24, 12, 16] Performativity of prediction is also related to
several applications: strategic classification [15], retraining [4, 19].

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 [8, 3, 13, 1, 21,
14]. 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 [11, 2, 6, 27, 7,
29]. The technique of Li-Yorke chaos has recently found applications across
several different domains such as routing games, Cournot games and blockchain
protocols [26, 10, 5, 9, 20]. 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 [18, 11], 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. [26].

##  2 Preliminary

###  2.1 Multi-agent Performative Prediction

We first formulate the framework of multi-agent performative prediction, and
we introduce an example of multi-agent performative prediction on which we
will focus.

A _multi-agent performative prediction_ comprises $n$ agents deploying their
predictive models $f_{\theta^{1}},\dots,f_{\theta^{n}}$ with parameters
${\bm{\theta}}^{1},{\bm{\theta}}^{2},\dots,{\bm{\theta}}^{n}\in\Theta$ that
collectively influence the future data distribution. We formalize such
dependency via a _distribution map_ $\mathcal{D}(\cdot)$ which outputs a
distribution on the data, $\mathcal{D}({\vec{\bm{\theta}}})$, given a _models
profile_
${\vec{\bm{\theta}}}:=({\bm{\theta}}^{1},\dots,{\bm{\theta}}^{n})\in\Theta^{n}$.
A loss function $\ell({\bm{z}},{\bm{\theta}}^{\prime})$ measures the loss of a
model $f_{{\bm{\theta}}^{\prime}}$ on a data point ${\bm{z}}\in\mathcal{Z}$,
and the expected loss on a distribution $\mathcal{D}$ is
$\mathbb{E}_{{\mathbf{z}}\sim\mathcal{D}}[\ell({\mathbf{z}},{\bm{\theta}}^{\prime})]$.
For performative prediction, we further define the decoupled performative loss
on a distribution mapping $\mathcal{D}$ as

$\ell({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime}):=\mathbb{E}_{{\mathbf{z}}\sim\mathcal{D}({\vec{\bm{\theta}}})}\ell({\mathbf{z}},{\bm{\theta}}^{\prime})$

where ${\bm{\theta}}^{\prime}\in\Theta$ denotes a _predictive model_ , while
${\vec{\bm{\theta}}}\in\Theta^{n}$ denotes a _deployed model profile_.

Given the set of model $\Theta$, the loss function $\ell$, and the
distribution mapping $\mathcal{D}$, each agent in a multi-agent performative
prediction $(\Theta,\ell,\mathcal{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 [28].

######  Definition 2.1 (label = def:stable).

Given $(\Theta,\ell,\mathcal{D})$, a models profile
${\vec{\bm{\theta}}}^{*}{\in\Theta^{n}}$ is _performatively optimal_ if the
total loss is minimized,

${\vec{\bm{\theta}}}^{*}\in\operatorname*{arg\,min}_{{\vec{\bm{\theta}}}{\in\Theta^{n}}}\sum_{i}\ell({\vec{\bm{\theta}}},{\bm{\theta}}^{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, ${\vec{\bm{\theta}}}^{*}$ is
_performatively stable_ if for all $i\in[n]$

$({\bm{\theta}}^{*})^{i}\in\operatorname*{arg\,min}_{{\bm{\theta}}^{i}{\in\Theta}}\ell({\vec{\bm{\theta}}}^{*},{\bm{\theta}}^{i}).$

The performative optimality does not implies the performative stable point.
For performative optimal point, the variable for minimization
${\vec{\bm{\theta}}}$ 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, ${\bm{z}}=({\bm{x}},y)$. In the location-scale distribution
map, the performative effects is linear in ${\vec{\bm{\theta}}}$.

######  Definition 2.2.

Given $d\in\mathbb{N}$ and $d\geq 2$, and
${\Theta^{n}}\subseteq\mathbb{R}^{d}$, a distribution map
$\mathcal{D}:{\Theta^{n}}\to\mathbb{R}^{d}\times\mathbb{R}$ is a _multi-agent
location-scale distribution map on $n$ parties_ if there exists a static
distribution $\mathcal{D}_{X}$ on $\mathbb{R}^{d+1}$,
${\bm{\theta}}^{0}\in\mathbb{R}^{d}$, and $n$ linear functions
$\Lambda_{1},\dots,\Lambda_{n}$ from $\mathbb{R}^{d}$ to $\mathbb{R}^{d}$ so
that the distribution of
$({\mathbf{x}},{\textnormal{y}})\sim\mathcal{D}({\vec{\bm{\theta}}})$ has the
following form: The feature is ${\bm{x}}\in\mathbb{R}^{d}$ and noise
$x_{0}\in\mathbb{R}$ is jointly sampled from $\mathcal{D}_{X}$. Given feature
${\bm{x}}\in\mathbb{R}^{d}$ and noise $x_{0}\in\mathbb{R}$, and the the
outcome is

${y=\left\langle{\bm{\theta}}^{0}-\sum_{i=1}^{n}\Lambda_{i}({\bm{\theta}}^{i}),{\bm{x}}\right\rangle+x_{0}.}$

In this paper, we consider the scaling maps
$\Lambda_{i}({\bm{\theta}})=\lambda_{i}{\bm{\theta}}$ for all
${\bm{\theta}}\in\Theta$ with scalar $\lambda_{i}>0$ for all $i\in[d]$. We
call $\bm{\lambda}:=(\lambda_{1},\dots,\lambda_{n})$ the influence parameters,
and $L_{n}:=\sum_{i=1}^{n}\lambda_{i}$ collective influence. Furthermore, we
let
${\bm{A}}:=\mathbb{E}\left[{\mathbf{x}}{\mathbf{x}}^{\top}\right]\in\mathbb{R}^{d\times
d}$ be the covariance matrix of the feature, and
${\bm{b}}:={\bm{A}}{\bm{\theta}}^{0}+\mathbb{E}[{\textnormal{x}}_{0}{\mathbf{x}}]\in\mathbb{R}^{d}$.
We will specify the multi agent location-scale distribution map with
parameters $n,d,\bm{\lambda},{\bm{A}}$, and ${\bm{b}}$.

When $n=1$, our multi-agent location-scale distribution map is a special case
of location-scale family in Miller et al. [25] where the model ${\bm{\theta}}$
may both the outcome $y$ as well as the feature ${\bm{x}}$.

#### Linear Predictive Models and Mean Squared Loss Function

We consider _linear predictive model with constraint_ where
$f_{{\bm{\theta}}^{\prime}}({\bm{x}})=\langle{\bm{\theta}}^{\prime},{\bm{x}}\rangle$,
and the collection of parameter is the $d$-simplex,
$\Theta=\\{{\bm{\theta}}:\sum_{k=1}^{d}\theta_{k}=1,\theta_{k}\geq 0\\}$. We
use _mean squared error_ to measure a predictive model
${\bm{\theta}}^{\prime}\in\Theta$ on a distribution map with a deployed model
profile ${\vec{\bm{\theta}}}\in\Theta^{n}$,
$\ell({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime})=\mathbb{E}_{({\mathbf{x}},{\textnormal{y}})\sim\mathcal{D}({\vec{\bm{\theta}}})}[({\textnormal{y}}-f_{{\bm{\theta}}^{\prime}}({\mathbf{x}}))^{2}]=\mathbb{E}_{({\mathbf{x}},{\textnormal{y}})\sim\mathcal{D}({\vec{\bm{\theta}}})}[({\textnormal{y}}-{\bm{\theta}}^{\prime}\cdot{\mathbf{x}})^{2}]$.

Given a deployed model profile ${\vec{\bm{\theta}}}$ and a predictive model
${\bm{\theta}}^{\prime}$, the gradient of the decoupled loss is
${\bm{g}}({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime}):=\nabla_{{\bm{\theta}}^{\prime}}\ell({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime})$.
If $\mathcal{D}$ is a location-scale distribution map,
${\bm{g}}({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime})=\mathbb{E}_{({\mathbf{x}},{\textnormal{y}})\sim\mathcal{D}({\vec{\bm{\theta}}})}[2({\bm{\theta}}^{\prime}\cdot{\mathbf{x}}-{\textnormal{y}}){\mathbf{x}}]$.
Furthermore, with ${\bm{A}}$ and ${\bm{b}}$ defined in definition 2.2, the
gradient can be written as

${\bm{g}}({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime})=\nabla_{{\bm{\theta}}^{\prime}}\ell({\vec{\bm{\theta}}},{\bm{\theta}}^{\prime})=2{\bm{A}}\left({\bm{\theta}}^{\prime}+\sum_{i}\lambda_{i}{\bm{\theta}}^{i}\right)-2{\bm{b}}.$
(1)

Additionally, given a deployed model profile ${\vec{\bm{\theta}}}$ and a
predictive model profile ${\vec{\bm{\theta}}}^{\prime}$, we define the
gradient of agent $i$’s decoupled loss as
${\bm{g}}^{i}({\vec{\bm{\theta}}},{\vec{\bm{\theta}}}^{\prime}):={\bm{g}}({\vec{\bm{\theta}}},({\bm{\theta}}^{\prime})^{i})$,
and
${\bm{g}}^{i}({\vec{\bm{\theta}}}):={\bm{g}}^{i}({\vec{\bm{\theta}}},{\vec{\bm{\theta}}})$
when the deployed model profile is identical to the predictive model profile.
We denote the gradient of agent $i$’s average loss as
$\bar{g}^{i}({\vec{\bm{\theta}}}):=\sum_{l}\theta_{l}^{i}g^{i}_{l}({\vec{\bm{\theta}}})$
for all ${\vec{\bm{\theta}}}\in\Theta^{n}$. Finally, we define
$\vec{\bm{\xi}}({\vec{\bm{\theta}}})=(\bm{\xi}^{1},\dots,\bm{\xi}^{n})$ with
$\bm{\xi}^{i}\in\mathbb{R}^{d}$ so that for all $i\in[n]$ and $k\in[d]$
$\xi^{i}_{k}({\vec{\bm{\theta}}}):=\theta^{i}_{k}(\sum\theta^{i}_{l}g^{i}_{l}-g^{i}_{k})$
which is the gradient subtracted by the average gradient. For brevity, we omit
${\vec{\bm{\theta}}}$ and define
$\vec{{\bm{g}}}:=\vec{{\bm{g}}}({\vec{\bm{\theta}}})$ and
${\vec{\bm{\xi}}}:={\vec{\bm{\xi}}}({\vec{\bm{\theta}}})$ when there is no
ambiguity.

###  2.2 Learning dynamics

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 (name = Kivinen & Warmuth [17], label =
def:exponentiated).

Given a learning rate $\eta>0$, an initial parameter
${\bm{\theta}}_{0}\in\Theta$ and a sequential of data points
$({\bm{x}}_{t},y_{t})_{t\geq 1}$, the _exponentiated gradient descent for
linear regression_ iteratively updates the model as follows: At round $t+1$,
with previous parameter ${\bm{\theta}}_{t}\in\Theta$ the exponentiated
gradient algorithm updates it to ${\bm{\theta}}_{t+1}$ so that

$\theta_{t+1,k}=\frac{\theta_{t,k}\exp(-2\eta({\bm{\theta}}_{t}\cdot{\bm{x}}_{t}-y_{t})x_{t,k})}{\sum_{l}\theta_{t,l}\exp(-2\eta({\bm{\theta}}_{t}\cdot{\bm{x}}_{t}-y_{t})x_{t,l})}\text{
for all }k\in[d].$

Note that each exponent $2({\bm{\theta}}_{t}\cdot{\bm{x}}_{t}-y_{t})x_{t,k}$
is the $k$-th coordinate of the gradient of squared error
$\ell(({\bm{x}}_{t},y_{t}),{\bm{\theta}}_{t})$ at ${\bm{\theta}}_{t}$ which
yields the name of exponentiated gradient descent.

###  2.3 Dynamical system

######  Definition 2.4 (label = def:chaos).

Let $(\mathcal{X},f)$ be a dynamical system where $\mathcal{X}$ is a metric
space and $f$ is a mapping on $\mathcal{X}$. We say
$(x,x^{\prime})\in\mathcal{X}\times\mathcal{X}$ is a Li-Yorke pair if

$\liminf_{t}dist(f^{t}(x),f^{t}(x^{\prime}))=0\text{ and
}\limsup_{t}dist(f^{t}(x),f^{t}(x^{\prime})>0.$

$(\mathcal{X},f)$ is Li-Yorke chaotic if there is an uncountable set
$S\subset\mathcal{X}$ (scrambled set) such that any pair of points $x\neq
x^{\prime}\in S$ is Li-Yorke pair.

##  3 Multi-agent Performative Learning: Stability and Optimality

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
(LABEL:prop:existence) and 2) the performative stability and performative
optimality are equivalent (LABEL:prop:stable2optimal). 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
$\frac{\partial}{\partial\theta^{i}_{k}}\Phi({\vec{\bm{\theta}}})=\lambda_{i}g^{i}_{k}({\vec{\bm{\theta}}})$
for all $i\in[n]$ and $k\in[d]$.

######  Proposition 3.1 (name = existence, label = prop:existence).

Given the family of linear predictive models with constrains $\Theta$, mean
squared error $\ell$ and multi-agent location-scale distribution map with
parameters $n,d,\bm{\lambda},{\bm{A}},{\bm{b}}$ in definition 2.2,
${\vec{\bm{\theta}}}^{*}$ on $(\Theta,\ell,\mathcal{D})$ is performative
stable if and only if the gradient (defined in eq. 1) satisfies
$g^{i}_{k}({\vec{\bm{\theta}}}^{*})\leq g^{i}_{l}({\vec{\bm{\theta}}}^{*})$
for all $i\in[n]$ and $k\in[d]$ with $\theta^{i}_{k}>0$.

Furthermore, if ${\bm{A}}$ is positive definite, there exists a unique
performative stable point ${\vec{\bm{\theta}}}^{*}$ that is also a global
minimizer of the following convex function

$\Phi({\vec{\bm{\theta}}}):=(\sum_{i}\lambda_{i}{\bm{\theta}}^{i})^{\top}{\bm{A}}(\sum_{i}\lambda_{i}{\bm{\theta}}^{i})+\sum_{i}\lambda_{i}({\bm{\theta}}^{i})^{\top}{\bm{A}}{\bm{\theta}}^{i}-2{\bm{b}}^{\top}\sum_{i}\lambda_{i}{\bm{\theta}}^{i},\text{
for all }{\vec{\bm{\theta}}}\in\Theta^{n}.$ (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 (label = prop:stable2optimal).

Given $(\Theta,\ell,\mathcal{D})$ defined in LABEL:prop:existence,
${\vec{\bm{\theta}}}^{*}$ is performative stable if and only if
${\vec{\bm{\theta}}}^{*}$ is performatively optimal defined in
LABEL:def:stable.

##  4 Multi-agent Performative Learning: Convergence and Chaos

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 $L_{n}$. 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 $L_{n}$ is large enough.

Now, we define our dynamics $({\vec{\bm{\theta}}}_{t})_{t\geq 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
${\vec{\bm{\theta}}}_{0}\in\Theta^{n}$ and a learning rate profile
$\bm{\eta}:=(\eta_{1},\dots,\eta_{n})$, each agent $i$ applies the
exponentiated gradient descent with initial parameter ${\bm{\theta}}^{i}_{0}$
and learning rate $\eta_{i}>0$: At round $t+1>1$, each agent $i$ use
$\mathcal{D}({\vec{\bm{\theta}}}_{t})$ and estimates the gradient of the
(expected) loss, ${\bm{g}}^{i}({\vec{\bm{\theta}}}_{t})$ defined in eq. 1, and
updates his model according to LABEL:def:exponentiated,

$\theta^{i}_{t+1,k}=\frac{\theta^{i}_{t,k}\exp(-\eta_{i}g^{i}_{k}({\vec{\bm{\theta}}}_{t}))}{\sum_{l=1}^{d}\theta^{i}_{t,l}\exp(-\eta_{i}g^{i}_{l}({\vec{\bm{\theta}}}_{t}))}\text{
for all }t\geq 0,i\in[n],\text{ and }k\in[d].$ (3)

We will use superscript to denote agent, $i\in[n]$, and subscript for time,
$t\geq 0$, and index of feature, $k,l\in[d]$. Recall that the gradient of
agent $i$’s average loss is
$\bar{g}^{i}({\vec{\bm{\theta}}}):=\sum_{l}\theta_{l}^{i}g^{i}_{l}({\vec{\bm{\theta}}})$,
and eq. 3 can be rewritten as
$\frac{\theta^{i}_{k}\exp(-\eta_{i}g^{i}_{k}({\vec{\bm{\theta}}}_{t}))}{\sum_{l}\theta^{i}_{l}\exp(-\eta_{i}g^{i}_{l}({\vec{\bm{\theta}}}_{t}))}=\frac{\theta^{i}_{k}\exp(\eta_{i}(\bar{g}^{i}({\vec{\bm{\theta}}}_{t})-g^{i}_{k}({\vec{\bm{\theta}}}_{t})))}{\sum_{l}\theta^{i}_{l}\exp(\eta_{i}(\bar{g}^{i}({\vec{\bm{\theta}}}_{t})-g^{i}_{l}({\vec{\bm{\theta}}}_{t})))}$.
Finally, given ${\vec{\bm{\theta}}}^{*}$ and $i\in[d]$, we define the support
of ${\vec{\bm{\theta}}}^{*}$ as
$S_{i}\subseteq[d]=\\{k:(\theta^{*})^{i}_{k}>0\\}$, and
$\bar{S}_{i}:=[d]\setminus S_{i}$. Then ${\vec{\bm{\theta}}}^{*}$ is an
_equilibrium (or fixed point)_ of eq. 3 if

$g^{i}_{k}({\vec{\bm{\theta}}}^{*})=\bar{g}^{i}({\vec{\bm{\theta}}}^{*}),\text{
for all }i\in[n],k\in S_{i}.$ (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 LABEL:prop:existence is equivalent to

$g^{i}_{k}({\vec{\bm{\theta}}}^{*})=\bar{g}^{i}({\vec{\bm{\theta}}}^{*})\text{
and
}g^{i}_{l}({\vec{\bm{\theta}}}^{*})\geq\bar{g}^{i}({\vec{\bm{\theta}}}^{*}),\text{
for all }i\in[n],k\in S_{i},l\in\bar{S}_{i}.$ (5)

Therefore, the set of fixed points of eq. 3 contains the performative stable
point.

###  4.1 Converging with Small Learning Rate

In this section, we show when the learning rate of each agent is small enough
the the dynamics in eq. 3 converge to the performative stable point.
Specifically, if the parameter of multi-agent performative learning
$(n,d,{\bm{A}},\bm{\lambda})$ is fixed, the dynamics in eq. 3 converge to
performative stable point when $\bm{\eta}$ is “small” enough.

By eq. 5, ${\vec{\bm{\theta}}}^{*}$ is performative stable if the gradient in
the support is no less than the average gradient. We call a performative
stable point ${\vec{\bm{\theta}}}^{*}$ _proper_ if the gradient of non-support
coordinate is greater than the average gradient: for all $i\in[n]$
$l\in\bar{S}_{i}$,
$g^{i}_{l}({\vec{\bm{\theta}}}^{*})>\bar{g}^{i}({\vec{\bm{\theta}}}^{*})$. The
below theorem shows if the performative stable point is proper and equilibria
satisfying eq. 4 are isolated, eq. 3 converges when $\max_{i}\eta_{i}$ is
small enough and the ratio of $\eta_{i}/\eta_{j}$ is bounded for all $i$ and
$j$.

######  Theorem 4.1 (name = Convergence,label = thm:converge).

Given a constant $R_{\eta}>0$, and a multi-agent performative learning setting
with parameter $n,d,{\bm{A}},{\bm{b}},\bm{\lambda}$ where ${\bm{A}}$ is
positive definite, the performative stable point ${\vec{\bm{\theta}}}^{*}$ is
proper and its equilibria (defined in eq. 4) are isolated, there exists
$\eta_{*}>0$ so that dynamic in eq. 3 with learning rate profile $\bm{\eta}$
converges to the performative stable point,
$\lim_{t\to\infty}{\vec{\bm{\theta}}}_{t}={\vec{\bm{\theta}}}^{*},$ if the
initial state is an interior point and $\bm{\eta}$ satisfies
$\max_{i}\eta_{i}\leq\eta_{*}$ and $\max_{i}\eta_{i}/\min_{i}\eta_{i}\leq
R_{\eta}$.

Informally, when the learning rate $\bm{\eta}$ are small,
${\vec{\bm{\theta}}}_{t}$ in eq. 3 can be approximated by a solution of an
ordinary differential equation, $\vec{\bm{\vartheta}}(t\|\bm{\eta}\|_{1})$,
where the initial condition is
$\vec{\bm{\vartheta}}(0)={\vec{\bm{\theta}}}_{0}$ and

$\frac{d}{dt}\vartheta^{i}_{k}(t)=\frac{\eta_{i}}{\|\bm{\eta}\|_{1}}\vartheta^{i}_{k}(t)(\bar{g}^{i}(\vec{\bm{\vartheta}}(t))-g^{i}_{k}(\vec{\bm{\vartheta}}(t)))$
(6)

for all $t\geq 0,i\in[n]$, and $k\in[d]$. Note that the set of fixed points of
eq. 6 is identical to eq. 3 and satisfies eq. 4. We will formalize this
approximation in the proof of LABEL:thm:converge_const.

The proof of LABEL:thm:converge 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, LABEL:thm:converge_conti 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 (label = thm:converge_conti).

If all points satisfying eq. 4 are isolated and ${\bm{A}}$ is positive
definite, and $\vec{\bm{\vartheta}}(0)$ is in the interior of $\Theta^{n}$,
the limit $\lim_{t\to\infty}\vec{\bm{\vartheta}}(t)={\vec{\bm{\theta}}}^{*}$
is the performative stable point.

LABEL:thm:converge_conti can be seen as the continuous version of
LABEL:thm:converge with two subtlety. First LABEL:thm:converge_conti does not
require that the performative stable point is proper. Second,
LABEL:thm:converge_conti also implicitly requires the ratio of learning rate
between any two agents is bounded.

To prove LABEL:thm:converge_conti, we need LABEL:lem:potential_conti which
shows that $\Phi$ in eq. 2 is a potential function for eq. 6 so that time
derivative of $\Phi$ is negative for all non-fixed points. Thus, the limit of
eq. 6 is a fixed point. Furthermore, in the proof of LABEL:thm:converge_conti,
we prove that the limit of eq. 6 is performative stable when the initial
condition $\vec{\bm{\vartheta}}(0)$ is an interior point. The proof is similar
to a proof in [18], and is presented in appendix B.

######  Lemma 4.3 (label = lem:potential_conti).

Given a solution of eq. 6, the time derivative of $\Phi$ in eq. 2 is $0$ at
fixed points of eq. 6, and negative at all other points. Furthermore,

$\frac{d}{dt}\Phi(\vec{\bm{\vartheta}}(t))\leq\frac{-1}{2\sum_{i}\eta_{i}\sum_{i}\lambda_{i}\eta_{i}}\left(\sum_{i,k}\lambda_{i}\eta_{i}|\vartheta^{i}_{k}(\sum_{l}\vartheta^{i}_{l}g^{i}_{l}-g^{i}_{k})|\right)^{2}\leq\frac{-\min_{i}\lambda_{i}\eta_{i}}{2\sum_{i}\eta_{i}\sum_{i}\lambda_{i}\eta_{i}}\|{\vec{\bm{\xi}}}({\vec{\bm{\vartheta}}})\|_{1}^{2}.$

#### 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. First,
LABEL:thm:converge_const shows that given any neighborhood of performative
stable points $D$, eq. 3 will hits $D$ and stay in $D$ in a finite number of
of steps. Then LABEL:thm:converge_point shows that eq. 3 converges to a
performative stable point which completes the proof of LABEL:thm:converge.

######  Lemma 4.4 (label = thm:converge_const).

Given any open set $D\in\Theta^{n}$ that contains the performative stable
point, there exists $\eta_{*}$ small enough so that for all interior initial
point ${\vec{\bm{\theta}}}_{0}\in\Theta^{n}$, there exists $\tau$ so that
${\vec{\bm{\theta}}}_{t}\in D$ for all $t\geq\tau$.

The proof is based on standard approximation result of numerical solution to
ordinary differential equations, and is presented in appendix C.

######  Lemma 4.5 (label = thm:converge_point).

Let ${\vec{\bm{\theta}}}^{*}$ be the performative stable point and $D$ be a
small enough neighborhood of ${\vec{\bm{\theta}}}^{*}$. In additional to the
conditions in LABEL:thm:converge, if the initial condition of eq. 3,
${\vec{\bm{\theta}}}_{0}$, is in $D$ and ${\vec{\bm{\theta}}}_{t}\in D$ for
all $t\geq 0$, the limit of eq. 3 is the performative stable point
$\lim_{t\to\infty}{\vec{\bm{\theta}}}_{t}={\vec{\bm{\theta}}}^{*}.$

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.

###  4.2 Chaos with Constant Learning Rate

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?

LABEL:thm:chaos_one shows that the dynamics is Li-York chaotic when
$L_{n}=\sum_{i}\lambda_{i}$ is large even with $d=2$. Note that large $L_{n}$
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 $\eta$, no
matter how cautious the agents are, as number of agent increases the chaos
inevitably occurs.

######  Theorem 4.6 (name = Chaos, label = thm:chaos_one).

Given a multi-agent induced location scale family distribution with
${\bm{A}}$, ${\bm{b}}$, $d=2$, and a common learning rate $\eta>0$, if all $n$
agents use the exponentiated gradient with a common learning rate $\eta$ in
eq. 3 and ${\bm{A}}$ is diagonally dominant, there exists a carrying capacity
$L^{*}$ such that if $L_{n}=\sum_{i=1}^{n}\lambda_{i}\geq L^{*}$ the dynamics
$({\vec{\bm{\theta}}}_{t})_{t\in\mathbb{N}}$ is Li-Yorke chaotic and thus has
periodic orbits of all possible periods.

To prove LABEL:thm:chaos_one, we show there exists an uncountable scrambled
set defined in LABEL:def:chaos. First we consider all agents start from the
same initial model, and show the dynamics eq. 3 can be captured by the
following function,

$f_{u,v}(x)=\frac{x}{x+(1-x)\exp(u(x-v))}\;\forall x\in[0,1]$ (7)

with proper choice of $u\in\mathbb{R}$ and $v\in\mathbb{R}$. Note that $v$ is
an equilibrium, and $u$ controls steepness. First, when all agents start from
the same initial model, ${\bm{\theta}}^{i}_{0}={\bm{\theta}}_{0}$ for all
$i\in[n]$, and use the same learning rate $\eta$, their models are identical
for all $t\geq 0$. For all $t$ there exists ${\bm{\theta}}_{t}$ so that
${\bm{\theta}}^{i}_{t}={\bm{\theta}}_{t}$ for all $i$. Additionally, since
$d=2$, we can use a single parameter to encode a linear predictive model with
constraints. Given ${\bm{\theta}}\in\Theta=\Delta_{2}$, we define
$p({\bm{\theta}})=\theta_{1}\in[0,1]$ and omit the input ${\bm{\theta}}$ when
it is clear. Thus, we can rewrite the dynamics as $p_{t}=p({\bm{\theta}}_{t})$
which are one-dimensional dynamics on $[0,1]$, and
$p_{t+1}=\frac{p_{t}}{p_{t}+(1-p_{t})e^{\eta(g^{i}_{1}({\vec{\bm{\theta}}}_{t})-g^{i}_{2}({\vec{\bm{\theta}}}_{t}))}}$.
We set

$\displaystyle\alpha(L)=$ $\displaystyle
2\eta\left(1+L\right)(A_{1,1}-A_{1,2}-A_{2,1}+A_{2,2})\text{ and
}\beta(L)=\frac{(1+L)(A_{2,2}-A_{2,1})+(b_{1}-b_{2})}{(1+L)(A_{1,1}-A_{1,2}-A_{2,1}+A_{2,2})},$

and write $\alpha_{n}=\alpha(L_{n})$ and $\beta_{n}=\beta(L_{n})$. By direct
computation the dynamic of $p_{t}$ is

$p_{t+1}=f_{\alpha_{n},\beta_{n}}(p_{t})$ (8)

where $\alpha_{n}$ encodes the update pace and $\beta_{n}$ is an equilibrium
of the dynamic. We further set
$\beta_{\infty}:=\frac{A_{2,2}-A_{2,1}}{A_{1,1}-A_{1,2}-A_{2,1}+A_{2,2}}$ and
$\delta(L):=\beta(L)-\beta_{\infty}$ which converges to zero as $L\to\infty$.
If ${\bm{A}}$ is diagonally dominant $\alpha(L)$ is positive and increasing
for all $L\geq 0$. Additionally, because $A_{1,1}-A_{1,2}$ and
$A_{2,2}-A_{2,1}$ are positive, we can permute the coordinate so that
$\beta_{\infty}\in(0,1/2]$. With [23], the lemma below implies the existence
of period three points and the proof is in appendix E.

######  Lemma 4.7 (name = period three, label = lem:three).

If $\beta_{\infty}\in(0,1/2)$, there exists a constant $L^{*}>0$ so that if
$L\geq L^{*}$, there exists a trajectory $x_{0},x_{1},x_{2}$, and $x_{3}$ with
$f_{\alpha(L),\beta(L)}(x_{i})=x_{i+1}$ such that $x_{3}<x_{0}<x_{1}$.

###### Proof of LABEL:thm:chaos_one.

First by LABEL:lem:three, for all $L\geq L^{*}$, there exists a trajectory
$x_{0},x_{1},x_{2},x_{3}$ so that $x_{3}<x_{0}<x_{1}$. Additionally, existence
of such trajectory implies the exists of period three points by [23]. Finally,
by the seminal work of Li & Yorke [22], it implies that the map is Li-York
chaotic. ∎

##  5 Simulation

(a) $(14,0.001)$ without noise

(b) $(1.4,0.05)$ without noise

(c) $(14,0.05)$ without noise

(d) $(14,0.001)$ with noise

(e) $(1.4,0.05)$ with noise

(f) $(14,0.05)$ with noise

Figure 1: Here we plot the temporal behavior of $p_{t}$ starting at
$p_{0}=0.2$ for $100$ rounds under various $L$ and $\eta$, and noisy
estimation of gradient of mean squared error with $m$ samples. The top row
(figs. 1(c), 1(a) and 1(b)) present different combination of $(L,\eta)$, and
bottom row (figs. 1(f), 1(d) and 1(e)) consider the gradient is estimated from
$m=10$ and $m=100$ samples.

Now we simulate the one-dimensional dynamics in eq. 8 of one agent with
different learning rate $\eta$ and collective influence $L$.

We first define a location-scale distribution map. Let the feature
${\textnormal{x}}_{1},{\textnormal{x}}_{2}$ and noise ${\textnormal{x}}_{0}$
are mutually independent Gaussian distribution with zero mean, and the
variance are $\mathbb{E}[{\textnormal{x}}_{1}^{2}]=3$,
$\mathbb{E}[{\textnormal{x}}_{2}^{2}]=7$, and
$\mathbb{E}[{\textnormal{x}}_{0}^{2}]=1$. Finally,
${\bm{\theta}}^{0}={\bm{0}}$. Therefore,

${\bm{A}}=\mathbb{E}[{\mathbf{x}}{\mathbf{x}}^{\top}]=\begin{bmatrix}3&0\\\
0&7\end{bmatrix},\text{ and
}{\bm{b}}={\bm{A}}{\bm{\theta}}^{0}+\mathbb{E}[{\textnormal{x}}_{0}{\mathbf{x}}]=\begin{bmatrix}0\\\
0\end{bmatrix}.$

Given learning rate $\eta>0$, and collective influence $L$, we have
$\alpha(L)=20\eta(1+L)$, and the performative stable point $\beta(L)=0.7$.

The top row of fig. 1 shows the temporal behavior of $p_{t}$ under different
$(L,\eta)$. 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
$g_{1}^{i}({\vec{\bm{\theta}}}_{t})-g_{2}^{i}({\vec{\bm{\theta}}}_{t})=2(1+L)(1,-1){\bm{A}}{\bm{\theta}}_{t}-2(1,-1){\bm{b}}$,
the agent replace ${\bm{A}}$ and ${\bm{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. 1(c) with $L=14$ and $\eta=0.05$,
and such behavior persists in fig. 1(f) when the evaluations of gradient are
noisy. On the other hand, when the learning rate is small enough (figs. 1(a)
and 1(b)) the dynamics converge to the performative stable point $0.7$.
Furthermore, in figs. 1(d) and 1(e) 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. 1(c), fig. 2(b) shows not only the temporal behavior $p_{t}$
is chaotic, but also the mean squared loss. On the other hand, under the same
setting as fig. 1(a), fig. 2(a) shows convergent behavior of loss.

(a) $(14,0.001)$ without noise

(b) $(14,0.05)$ without noise

Figure 2: The temporal behavior of the total cost for $100$ rounds under
various $\eta$.

##  6 Conclusion

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. [15] 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.

## References

  * Andrade et al. [2021] Gabriel P Andrade, Rafael Frongillo, and Georgios Piliouras.  Learning in matrix games can be arbitrarily complex.  In _Conference on Learning Theory (COLT)_ , 2021.
  * Bailey & Piliouras [2018] James P. Bailey and Georgios Piliouras.  Multiplicative weights update in zero-sum games.  In _ACM Confernce on Economics and Computation_ , pp. 321–338, 2018\.
  * Balduzzi et al. [2020] David Balduzzi, Wojciech M. Czarnecki, Thomas W. Anthony, Ian M. Gemp, Edward Hughes, Joel Z. Leibo, Georgios Piliouras, and Thore Graepel.  Smooth markets: A basic mechanism for organizing gradient-based learners.  _CoRR_ , abs/2001.04678, 2020.  URL https://arxiv.org/abs/2001.04678.
  * Bartlett [1992] Peter L Bartlett.  Learning with a slowly changing distribution.  In _Proceedings of the fifth annual workshop on Computational learning theory_ , pp. 243–252, 1992.
  * Bielawski et al. [2021] Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Michał Misiurewicz, and Georgios Piliouras.  Follow-the-regularized-leader routes to chaos in routing games.  _ICML_ , 2021.
  * Cheung [2018] Yun Kuen Cheung.  Multiplicative weights updates with constant step-size in graphical constant-sum games.  In _NeurIPS 2018_ , pp. 3532–3542, 2018.
  * Cheung & Piliouras [2020] Yun Kuen Cheung and Georgios Piliouras.  Chaos, extremism and optimism: Volume analysis of learning in games.  In _NeurIPS 2020_ , 2020.
  * Cheung & Tao [2020] Yun Kuen Cheung and Yixin Tao.  Chaos of learning beyond zero-sum and coordination via game decompositions.  In _International Conference on Learning Representations_ , 2020.
  * Cheung et al. [2021] Yun Kuen Cheung, Stefanos Leonardos, and Georgios Piliouras.  Learning in markets: Greed leads to chaos but following the price is right.  In Zhi-Hua Zhou (ed.), _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021_ , pp. 111–117. ijcai.org, 2021.  doi: 10.24963/ijcai.2021/16.
  * Chotibut et al. [2020] Thiparat Chotibut, Fryderyk Falniowski, Michał Misiurewicz, and Georgios Piliouras.  The route to chaos in routing games: When is price of anarchy too optimistic?  _NeurIPS_ , 2020.
  * Cohen et al. [2017] Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos.  Learning with bandit feedback in potential games.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pp. 6372–6381, 2017.
  * Drusvyatskiy & Xiao [2020] Dmitriy Drusvyatskiy and Lin Xiao.  Stochastic optimization with decision-dependent distributions, 2020.
  * Flokas et al. [2020] Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Thanasis Lianeas, Panayotis Mertikopoulos, and Georgios Piliouras.  No-regret learning and mixed nash equilibria: They do not mix.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Giannou et al. [2021] Angeliki Giannou, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Panayotis Mertikopoulos.  Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information.  _COLT_ , 2021.
  * Hardt et al. [2016] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic classification.  In _Proceedings of the 2016 ACM conference on innovations in theoretical computer science_ , pp. 111–122, 2016.
  * Izzo et al. [2021] Zachary Izzo, Lexing Ying, and James Zou.  How to learn when data reacts to your model: performative gradient descent.  _arXiv preprint arXiv:2102.07698_ , 2021.
  * Kivinen & Warmuth [1997] Jyrki Kivinen and Manfred K Warmuth.  Exponentiated gradient versus gradient descent for linear predictors.  _information and computation_ , 132(1):1–63, 1997\.
  * Kleinberg et al. [2009] Robert Kleinberg, Georgios Piliouras, and Éva Tardos.  Multiplicative updates outperform generic no-regret learning in congestion games.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , pp. 533–542, 2009.
  * Kuh et al. [1990] Anthony Kuh, Thomas Petsche, and Ronald L Rivest.  Learning time-varying concepts.  In _NIPS_ , pp. 183–189, 1990.
  * Leonardos et al. [2021] Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen, Stratis Skoulakis, and Georgios Piliouras.  Dynamical analysis of the EIP-1559 ethereum fee market.  _CoRR_ , abs/2102.10567, 2021.  URL https://arxiv.org/abs/2102.10567.
  * Letcher [2021] Alistair Letcher.  On the impossibility of global convergence in multi-loss optimization.  In _International Conference on Learning Representations_ , 2021.
  * Li & Yorke [1975] Tien-Yien Li and James A. Yorke.  Period three implies chaos.  _The American Mathematical Monthly_ , 82(10):985–992, 1975.  ISSN 00029890, 19300972.  URL http://www.jstor.org/stable/2318254.
  * Li et al. [1982] Tien-Yien Li, Michał Misiurewicz, Giulio Pianigiani, and James A. Yorke.  Odd chaos.  _Physics Letters A_ , 87(6):271–273, 1982.  ISSN 0375-9601.  doi: https://doi.org/10.1016/0375-9601(82)90692-2.  URL https://www.sciencedirect.com/science/article/pii/0375960182906922.
  * Mendler-Dünner et al. [2020] Celestine Mendler-Dünner, Juan C Perdomo, Tijana Zrnic, and Moritz Hardt.  Stochastic optimization for performative prediction.  _arXiv preprint arXiv:2006.06887_ , 2020.
  * Miller et al. [2021] John Miller, Juan C Perdomo, and Tijana Zrnic.  Outside the echo chamber: Optimizing the performative risk.  _arXiv preprint arXiv:2102.08570_ , 2021.
  * Palaiopanos et al. [2017] Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras.  Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos.  _CoRR_ , abs/1703.01138, 2017.  URL http://arxiv.org/abs/1703.01138.
  * Panageas et al. [2019] Ioannis Panageas, Georgios Piliouras, and Xiao Wang.  Multiplicative weights updates as a distributed constrained optimization algorithm: Convergence to second-order stationary points almost always.  In _International Conference on Machine Learning_ , pp. 4961–4969. PMLR, 2019.
  * Perdomo et al. [2020] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt.  Performative prediction.  In _International Conference on Machine Learning_ , pp. 7599–7609. PMLR, 2020.
  * Vadori et al. [2021] Nelson Vadori, Rahul Savani, Thomas Spooner, and Sumitra Ganesh.  Consensus multiplicative weights update: Learning to learn using projector-based game signatures.  _arXiv preprint arXiv:2106.02615_ , 2021.

##  Appendix A Proofs and Details in Section 3

###### Proof of LABEL:prop:existence.

First under the mean squared loss function, each agent $i$’s decoupled
performative loss function
$\ell({\vec{\bm{\theta}}}^{\prime},{\bm{\theta}}^{i})$ is convex in
${\bm{\theta}}^{i}$. Thus, for linear predictive model, we can apply the KKT
conditions on LABEL:def:stable so that a collection of predictive models
${\vec{\bm{\theta}}}\in\Theta^{n}$ is performatively stable if and only if for
all $i\in[n]$, $k\in[d]$ with $\theta^{i}_{k}>0$,
$\frac{\partial}{\partial\theta^{i}_{k}}\ell({\vec{\bm{\theta}}}^{\prime},{\bm{\theta}}^{i})\leq\frac{\partial}{\partial\theta^{i}_{l}}\ell({\vec{\bm{\theta}}}^{\prime},{\bm{\theta}}^{i})$
for all $l\in[d]$ where ${\vec{\bm{\theta}}}^{\prime}={\vec{\bm{\theta}}}$.
Therefore, with eq. 1, ${\vec{\bm{\theta}}}^{*}$ is performative stable if

$g^{i}_{k}({\vec{\bm{\theta}}}^{*})\leq g^{i}_{l}({\vec{\bm{\theta}}}^{*})$
(9)

holds for all $i\in[n]$ and $k\in[d]$ with $\theta^{i}_{k}>0$.

With eq. 9, we now show that there exists a unique performative stable point
${\vec{\bm{\theta}}}^{*}$ by proving that 1) $\Phi$ in eq. 2 is strictly
convex, and 2) ${\vec{\bm{\theta}}}^{*}$ is a minimizer of $\Phi$. First, to
show $\Phi$ is strictly convex, it is sufficient to show the Hessian of $\Phi$
positive definite. Because $\Phi$ is a quadratic function on $\Theta^{n}$, the
Hessian of $\Phi$ is a constant matrix in $\mathbb{R}^{nd\times nd}$ By the
partial derivative of eq. 2, for all $i,j\in[n]$ and $k,l\in[d]$, we have
$(\nabla^{2}\Phi)_{ik,jl}=\frac{\partial^{2}}{\partial\theta^{i}_{k}\partial\theta^{j}_{l}}\Phi=2\lambda_{i}\lambda_{j}A_{k,l}$
if $i\neq j$ and
$(\nabla^{2}\Phi)_{ik,il}=2\lambda_{i}(\lambda_{i}+1)A_{k,l}$. Let
${\bm{L}}\in\mathbb{R}^{n\times n}$ with $L_{ij}=2\lambda_{i}\lambda_{j}$ if
$i\neq j$ and $2\lambda_{i}(1+\lambda_{i})$ which is positive definite because
$\lambda_{i}>0$ for all $i\in[n]$. Then, the Hessian of $\Phi$ is the
Kronecker product of ${\bm{L}}$ and ${\bm{A}}$,

$\nabla^{2}\Phi=\begin{pmatrix}2\lambda_{1}(1+\lambda_{1}){\bm{A}}&\dots&2\lambda_{1}\lambda_{n}{\bm{A}}\\\
\vdots&\ddots&\vdots\\\
2\lambda_{n}\lambda_{1}{\bm{A}}&\dots&2\lambda_{n}(1+\lambda_{n}){\bm{A}}\end{pmatrix}={\bm{L}}\otimes{\bm{A}}.$

Because ${\bm{L}}$ and ${\bm{A}}$ are both positive definite, the Hessian is
also positive definite. Therefore, $\Phi$ is strictly convex, and there exist
a unique minimum of $\Phi$ in the compact set $\Theta^{n}$. Now we show
${\vec{\bm{\theta}}}^{*}$ is performative stable if and only if
${\vec{\bm{\theta}}}^{*}$ is a minimizer of $\Phi$. By the first order
condition and the partial derivative of eq. 2, the minimum of eq. 2 at
${\vec{\bm{\theta}}}^{*}$ if and only if
$g^{i}_{k}({\vec{\bm{\theta}}}^{*})\leq g^{i}_{l}({\vec{\bm{\theta}}}^{*})$
for all $i\in[n]$ $k,l\in[d]$ with $(\theta^{*})^{i}_{k}>0$. Therefore,
${\vec{\bm{\theta}}}^{*}$ is the minimum of $\Phi$ if and only if
${\vec{\bm{\theta}}}^{*}$ is a performative stable point. ∎

###### Proof of LABEL:prop:stable2optimal.

Given a profile of models ${\vec{\bm{\theta}}}$, the total cost is

$\displaystyle\sum_{i}\ell({\vec{\bm{\theta}}},({\bm{\theta}})^{i})=$
$\displaystyle\sum_{i}\mathbb{E}_{({\mathbf{x}},{\textnormal{y}})\sim\mathcal{D}({\vec{\bm{\theta}}})}[({\textnormal{y}}-{\bm{\theta}}^{i}\cdot{\mathbf{x}})^{2}]$
$\displaystyle=$
$\displaystyle\sum_{i}\mathbb{E}\left[\left(\left\langle{\mathbf{x}},{\bm{\theta}}^{0}-\sum_{j}\lambda_{j}{\bm{\theta}}^{j}-{\bm{\theta}}^{i}\right\rangle+x_{0}\right)^{2}\right]$

which is a convex function on ${\vec{\bm{\theta}}}\in\Theta^{n}$.
Additionally,

$\frac{\partial}{\partial\theta^{i}_{k}}\sum_{\imath}\ell({\vec{\bm{\theta}}},{\bm{\theta}}^{\imath})=(1+\lambda_{i})g^{i}_{k}({\vec{\bm{\theta}}},{\vec{\bm{\theta}}})+\sum_{\imath\in[n]:\imath\neq
i}\lambda_{i}g^{i}_{k}({\vec{\bm{\theta}}},{\vec{\bm{\theta}}})=(1+n\lambda_{i})g^{i}_{k}({\vec{\bm{\theta}}},{\vec{\bm{\theta}}})$

which is the gradient of decoupled performative loss scaled by
$(1+n\lambda_{i})$. Thus, we can apply the KKT conditions and the minimum
happens if and only if eq. 9 holds. ∎

##  Appendix B Proof and Details for Theorem LABEL:thm:converge_conti

###### Proof of LABEL:lem:potential_conti.

By chain rule,

$\frac{d}{dt}\Phi(\vec{\bm{\vartheta}}(t))=\sum_{i\in[n],k\in[d]}\frac{\partial}{\partial\theta^{i}_{k}}(\vec{\bm{\vartheta}}(t))\cdot\frac{d}{dt}\vec{\bm{\vartheta}}(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.

$\displaystyle\frac{d}{dt}\Phi(\vec{\bm{\vartheta}}(t))=$
$\displaystyle\sum_{i,k}\frac{\partial}{\partial\theta^{i}_{k}}(\vec{\bm{\vartheta}}(t))\cdot\frac{\eta_{i}}{\|\bm{\eta}\|_{1}}\vartheta^{i}_{k}(t)(\sum_{l}\vartheta^{i}_{l}(t)g^{i}_{l}(\vec{\bm{\vartheta}}(t))-g^{i}_{k}(\vec{\bm{\vartheta}}(t)))$
(by eqs. 6 and 10) $\displaystyle=$
$\displaystyle\frac{1}{\|\bm{\eta}\|_{1}}\sum_{i}\lambda_{i}\eta_{i}\left(\sum_{k}\left(g^{i}_{k}\right)\cdot\vartheta^{i}_{k}\left(\sum_{l}\vartheta^{i}_{l}g^{i}_{l}-g^{i}_{k}\right)\right)$
(by the partial derivative of eq. 2) $\displaystyle=$
$\displaystyle\frac{1}{2\|\bm{\eta}\|_{1}}\sum_{i}\lambda_{i}\eta_{i}\sum_{k,l\in[d]}\vartheta^{i}_{k}\vartheta^{i}_{l}(2g^{i}_{k}g^{i}_{l}-2(g^{i}_{k})^{2})$
(because $\sum_{l}\vartheta^{i}_{l}=1$) $\displaystyle=$
$\displaystyle\frac{-1}{2\|\bm{\eta}\|_{1}}\sum_{i}\lambda_{i}\eta_{i}\sum_{k,l\in[d]}\vartheta^{i}_{k}\vartheta^{i}_{l}(g^{i}_{k}-g^{i}_{l})^{2}$

Now we bound the time derivative.

$\displaystyle-2\|\bm{\eta}\|_{1}\left(\sum_{i}\lambda_{i}\eta_{i}\right)\frac{d}{dt}\Phi(\vec{\bm{\vartheta}}(t))$
$\displaystyle=$
$\displaystyle\left(\sum_{i\in[n],k,l\in[d]}\lambda_{i}\eta_{i}\vartheta^{i}_{k}\vartheta^{i}_{l}\right)\left(\sum_{i\in[n],k,l\in[d]}\lambda_{i}\eta_{i}\vartheta^{i}_{k}\vartheta^{i}_{l}(g^{i}_{k}-g^{i}_{l})^{2}\right)$
($\sum_{k}\vartheta^{i}_{k}=\sum_{l}\vartheta^{i}_{l}=1$) $\displaystyle\geq$
$\displaystyle\left(\sum_{i\in[n],k,l\in[d]}\lambda_{i}\eta_{i}\vartheta^{i}_{k}\vartheta^{i}_{l}|g^{i}_{k}-g^{i}_{l}|\right)^{2}.$
(by Cauchy inequality) $\displaystyle\geq$
$\displaystyle\left(\sum_{i\in[n],k\in[d]}\lambda_{i}\eta_{i}\left|\vartheta^{i}_{k}\sum_{l\in[d]}\vartheta^{i}_{l}(g^{i}_{k}-g^{i}_{l})\right|\right)^{2}$
(by triangle inequality)

Therefore, $\frac{d}{dt}\Phi(\vec{\bm{\vartheta}}(t))=0$ only if
$\vartheta^{i}_{k}\left(g^{i}_{k}-\sum_{l\in[d]}\vartheta^{i}_{l}g^{i}_{l}\right)=0$
for all $i\in[n]$ and $k\in[d]$ which is a fixed point of eq. 6.

We can further simplify the bound by ${\vec{\bm{\xi}}}$. Because
$\sum_{i,k}\lambda_{i}\eta_{i}|\vartheta^{i}_{k}(\sum_{l}\vartheta^{i}_{l}g^{i}_{l}-g^{i}_{k})|\geq\left(\min_{i}\lambda_{i}\eta_{i}\right)\sum_{i,k}|\xi^{i}_{k}({\vec{\bm{\vartheta}}})|=\left(\min_{i}\lambda_{i}\eta_{i}\right)\|{\vec{\bm{\xi}}}({\vec{\bm{\vartheta}}})\|_{1}$,
$\frac{d}{dt}\Phi(\vec{\bm{\vartheta}}(t))\leq\frac{-\min_{i}\lambda_{i}\eta_{i}}{2\sum_{i}\eta_{i}\sum_{i}\lambda_{i}\eta_{i}}\|{\vec{\bm{\xi}}}({\vec{\bm{\vartheta}}})\|_{1}^{2}$.
∎

###### Proof of LABEL:thm:converge_conti.

When the fixed points are isolated satisfying eq. 4, by
LABEL:lem:potential_conti, the dynamics in eq. 6 converges to a fixed point of
eq. 6, ${\vec{\bm{\theta}}}^{*}\in\Theta^{n}$. Because
${\vec{\bm{\theta}}}^{*}$ is a fixed point, for all $i\in[n],k\in[d]$,

$(\theta^{*})^{i}_{k}\left(\bar{g}^{i}({\vec{\bm{\theta}}}^{*})-g^{i}_{k}({\vec{\bm{\theta}}}^{*})\right)=(\theta^{*})^{i}_{k}\sum_{l}(\theta^{*})^{i}_{l}g^{i}_{l}({\vec{\bm{\theta}}}^{*})-g^{i}_{k}({\vec{\bm{\theta}}}^{*})=0$

By LABEL:prop:existence, the fixed point condition implies each coordinate of
the gradient of loss in the support are identical,
$g^{i}_{k}({\vec{\bm{\theta}}}^{*})=\bar{g}^{i}({\vec{\bm{\theta}}}^{*})$ for
all $i$ and $k\in S_{i}$. Thus, if the fixed point ${\vec{\bm{\theta}}}^{*}$
is not performative stable, there exists $\imath$ and $\kappa$ with
$(\theta^{*})^{\imath}_{\kappa}=0$ so that
$g^{\imath}_{\kappa}({\vec{\bm{\theta}}}^{*})<\bar{g}^{\imath}({\vec{\bm{\theta}}}^{*})$.
Furthermore,
$\exp(-\eta_{\imath}g^{\imath}_{\kappa}({\vec{\bm{\theta}}}^{*}))>\sum_{l}(\theta^{*})^{\imath}_{l}\exp(-\eta_{\imath}g^{\imath}_{l}({\vec{\bm{\theta}}}^{*}))$.
We can pick a small enough $\epsilon>0$ and define

$U_{\epsilon}:=\\{{\vec{\bm{\theta}}}:\exp(-\eta_{\imath}g^{\imath}_{\kappa})>\sum_{l}\theta^{\imath}_{l}\exp(-\eta_{\imath}g^{\imath}_{l})+\epsilon\\}$
(11)

which contains ${\vec{\bm{\theta}}}^{*}$ and is an open set because
$\vec{{\bm{g}}}$ and the exponential function are continuous. Since
$\vec{\bm{\vartheta}}(t)$ converges to ${\vec{\bm{\theta}}}^{*}$ as
$t\to\infty$, there exists a time $t_{\epsilon}$ so that for all $t\geq
t_{\epsilon}$, $\vec{\bm{\vartheta}}(t)\in U_{\epsilon}$. However, if
$\vec{\bm{\vartheta}}(t)\in U_{\epsilon}$ and $\vec{\bm{\vartheta}}(t)$ is an
interior point, we get $\frac{d}{dt}\vartheta^{i}_{k}(t)>0$ by eqs. 6 and 11.
Therefore, $\vartheta^{i}_{k}(t)$ is positive and increasing for $t\geq
t_{\epsilon}$. We reached a contradiction because
$\vartheta^{i}_{k}(t)\to(\theta^{*})^{i}_{k}=0$. Therefore,
${\vec{\bm{\theta}}}^{*}$ is a performative stable point. ∎

##  Appendix C Proof ans Details for Theorem LABEL:thm:converge_const

To prove LABEL:thm:converge_const, show the dynamic eq. 3 can be approximated
by eq. 6 and the error vanishes as $\eta_{*}$ decreases. Thus, we can show the
dynamic can hit an arbitrary neighborhood of the performative stable point. We
further use $\Phi$ 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
$\vec{{\bm{e}}}({\vec{\bm{\theta}}})\in\mathbb{R}^{n\times d}$ between eqs. 3
and 6 so that

$\eta_{i}^{2}e^{i}_{k}({\vec{\bm{\theta}}}):=\frac{\theta^{i}_{k}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{k}))}{\sum_{l}\theta^{i}_{l}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{l}))}-\theta^{i}_{k}-\eta_{i}\xi^{i}_{k}$

We omit the input ${\vec{\bm{\theta}}}$ of $\vec{{\bm{e}}}$ and
$\vec{{\bm{e}}}_{t}:=\vec{{\bm{e}}}({\vec{\bm{\theta}}}_{t})$ when there is no
ambiguity. We show if the the error vector is small, $\Phi$ is decreasing in
dynamics eq. 3.

######  Claim C.1 (name = Approximated potential, label = lem:potential_dis).

There exist $C_{4}$, so that for all $t$ and
${\vec{\bm{\theta}}}_{0}\in\Theta^{n}$, the difference of eq. 2 on eq. 3
satisfies

$\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})\leq\frac{-\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{2\sum_{i}\lambda_{i}\eta_{i}}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}+\max_{i}\lambda_{i}\eta_{i}^{2}\max_{i,k,{\vec{\bm{\theta}}}}|g^{i}_{k}({\vec{\bm{\theta}}})|\cdot\|\vec{{\bm{e}}}_{t}\|_{1}+d^{2}C_{4}\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|^{2}_{1}.$

######  Claim C.2 (label = lem:err_const).

If $\max_{i}\eta_{i}$ is small enough and satisfies eq. 12, there exists a
constant $C$ so that

$|e^{i}_{k}({\vec{\bm{\theta}}})|\leq C\text{ for all }i\in[n],k\in[d],\text{
and }{\vec{\bm{\theta}}}\in\Theta^{n}.$

The proofs of these two claims are based on first order approximation.

###### Proof of LABEL:lem:potential_dis.

By the partial derivative of eq. 2, we have
$\frac{\partial^{2}}{\partial\theta^{i}_{k}\partial\theta^{j}_{l}}\Phi({\vec{\bm{\theta}}})=2\lambda_{i}\lambda_{j}A_{l,k}$
if $i\neq j$ and
$\frac{\partial^{2}}{\partial\theta^{i}_{k}\partial\theta^{i}_{l}}\Phi({\vec{\bm{\theta}}})=2\lambda_{i}(1+\lambda_{i})A_{l,k}$.
Thus, the second order partial derivatives of $\Phi$ can bounded by the twice
of
$C_{4}:=\max_{\imath}\lambda_{\imath}(\lambda_{\imath}+1)\max_{k,l}A_{k,l}$.
By Taylor’s expansion, we have

$\displaystyle\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})$
$\displaystyle\leq$
$\displaystyle\nabla\Phi({\vec{\bm{\theta}}}_{t})\cdot\left({\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right)+\frac{d^{2}2C_{4}}{2}\left\|{\vec{\bm{\theta}}}(t+1)-{\vec{\bm{\theta}}}(t)\right\|^{2}_{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[n],k\in[d]}\lambda_{i}g^{i}_{k}({\vec{\bm{\theta}}}_{t})(\eta_{i}\xi^{i}_{k}({\vec{\bm{\theta}}}_{t})+\eta_{i}^{2}e^{i}_{k}({\vec{\bm{\theta}}}_{t}))+d^{2}C_{4}\left\|{\vec{\bm{\theta}}}(t+1)-{\vec{\bm{\theta}}}(t)\right\|^{2}_{1}$
(by the partial derivative of eq. 2) $\displaystyle=$
$\displaystyle\sum_{i\in[n],k\in[d]}\lambda_{i}\eta_{i}g^{i}_{t,k}\xi^{i}_{t,k}+\lambda_{i}\eta_{i}^{2}g^{i}_{t,k}e^{i}_{t,k}+d^{2}C_{4}\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|^{2}_{1}$
$\displaystyle\leq$
$\displaystyle\frac{-1}{2\sum_{i}\lambda_{i}\eta_{i}}\left(\sum_{i,k}\lambda_{i}\eta_{i}|\xi^{i}_{t,k}|\right)^{2}+\sum_{i\in[n],k\in[d]}\lambda_{i}\eta_{i}^{2}g^{i}_{t,k}e^{i}_{t,k}+d^{2}C_{4}\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|^{2}_{1}$
(by LABEL:lem:potential_conti)

Therefore, we have

$\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})\leq\frac{-\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{2\sum_{i}\lambda_{i}\eta_{i}}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}+\max_{i}\lambda_{i}\eta_{i}^{2}\max_{i,k,{\vec{\bm{\theta}}}}|g^{i}_{k}({\vec{\bm{\theta}}})|\cdot\|\vec{{\bm{e}}}_{t}\|_{1}+d^{2}C_{4}\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|^{2}_{1}$

which completes the proof. ∎

###### Proof of LABEL:lem:err_const.

By if $\eta_{*}$ is small enough and satisfies eq. 12, we have
$\eta_{i}(\bar{g}^{i}-g^{i}_{k})\leq 1$, and
$\theta^{i}_{k}+\eta_{i}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})\leq\theta^{i}_{k}e^{\eta_{i}(\bar{g}^{i}-g^{i}_{k})}\leq\theta^{i}_{k}+\eta_{i}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})+\frac{e}{2}\eta_{i}^{2}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2}$
for all $i,k$ and ${\vec{\bm{\theta}}}\in\Theta^{n}$. Additionally, with
$\xi^{i}_{k}=\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})$, we can rewrite it as

$\theta^{i}_{k}\leq\theta^{i}_{k}e^{\eta_{i}(\bar{g}^{i}-g^{i}_{k})}-\eta_{i}\xi^{i}_{k}\leq\theta^{i}_{k}+\frac{e}{2}\eta_{i}^{2}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2}.$

Therefore, the error can be upper bounded as

$\displaystyle\eta_{i}^{2}e^{i}_{k}\leq\frac{\theta^{i}_{k}+\eta_{i}\xi^{i}_{k}+\frac{e}{2}\eta_{i}^{2}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2}}{\sum_{l}\theta^{i}_{l}+\eta_{i}\xi^{i}_{l}}-(\theta^{i}_{k}+\eta_{i}\xi^{i}_{k})=\frac{e}{2}\eta_{i}^{2}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2},$

because $\sum_{l}\theta^{i}_{l}=1$ and $\sum_{l}\xi^{i}_{l}=0$. For lower
bound, we have,

$\displaystyle\eta_{i}^{2}e^{i}_{k}\geq$
$\displaystyle\frac{\theta^{i}_{k}+\eta_{i}\xi^{i}_{k}}{\sum_{l}\theta^{i}_{l}+\eta_{i}\xi^{i}_{l}+\frac{e}{2}\eta_{i}^{2}\theta^{i}_{l}(\bar{g}^{i}-g^{i}_{l})^{2}}-(\theta^{i}_{k}+\eta_{i}\xi^{i}_{k})\geq-(\theta^{i}_{k}+\eta_{i}\xi^{i}_{k})\left(\frac{e\eta_{i}^{2}}{2}\sum_{l}\theta^{i}_{l}(\bar{g}^{i}-g^{i}_{l})^{2}\right).$

If we set
$C:=e\max_{{\vec{\bm{\theta}}}}\left|\sum_{l}\theta^{i}_{l}(\bar{g}^{i}-g^{i}_{l})^{2}\right|$,
because $|\eta_{i}\xi^{i}_{k}|\leq\eta_{i}2\max_{k}|g^{i}_{k}|\leq 1$ by eq.
12 and $\theta^{i}_{k}\leq 1$, we have
$\left|e^{i}_{k}({\vec{\bm{\theta}}})\right|\leq C$. ∎

###### Proof of LABEL:thm:converge_const.

Because $D$ is open, we can set $D^{\prime}$ so that
${\vec{\bm{\theta}}}^{*}\in D^{\prime}$, $D^{\prime}\subset D$, and
$\sup_{{\vec{\bm{\theta}}}\in
D^{\prime}}\Phi({\vec{\bm{\theta}}})<\frac{1}{2}\inf_{{\vec{\bm{\theta}}}\notin
D}\Phi({\vec{\bm{\theta}}})$. We will pick $\eta_{*}$ small enough so that
${\vec{\bm{\theta}}}_{t+1}\in D$ for all ${\vec{\bm{\theta}}}_{t}\in
D^{\prime}\subset 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 LABEL:thm:converge_conti, there exists $\tau$ so that
${\vec{\bm{\vartheta}}}(\tau)\in D^{\prime}$. Now by Gronwall’s inequality we
can set $\eta_{*}$ small enough so that
${\vec{\bm{\theta}}}_{\tau/\|\bm{\eta}\|_{1}}\in D$. Formally, given the
dynamics in eq. 3, we define right-continuous step functions
${\vec{\bm{\theta}}}(t)={\vec{\bm{\theta}}}_{\lfloor t\rfloor}$ and
$\vec{{\bm{e}}}(t):=\vec{{\bm{e}}}({\vec{\bm{\theta}}}_{\lfloor t\rfloor})$
for all $t\geq 0$. Then the dynamics in eq. 3 can be written as

$\theta^{i}_{k}(t)-\theta^{i}_{k}(0)=\sum_{s=0}^{t-1}(\theta^{i}_{s+1,k}-\theta^{i}_{s,k})=\sum_{s=0}^{t-1}\left(\eta_{i}\xi^{i}_{k}({\vec{\bm{\theta}}}_{s})+\eta_{i}^{2}e^{i}_{k}({\vec{\bm{\theta}}}_{s})\right)=\eta_{i}\int_{0}^{t}\xi^{i}_{k}({\vec{\bm{\theta}}}(s))+\eta_{i}e^{i}_{k}(s)\,ds$

On the other hand, the solution of eq. 6 can be written as

$\vartheta^{i}_{k}(\eta_{i}t)-\vartheta^{i}_{k}(0)=\frac{\eta_{i}}{\|\bm{\eta}\|_{1}}\int_{0}^{\frac{t}{\|\bm{\eta}\|_{1}}}\xi^{i}_{k}({\vec{\bm{\vartheta}}}(s))\,ds=\eta_{i}\int_{0}^{t}\xi^{i}_{k}({\vec{\bm{\vartheta}}}(\|\bm{\eta}\|_{1}s))\,ds$

Because $\xi^{i}_{k}$ are continuous and $\Theta^{n}$ is compact, there exists
$L>0$ so that $\xi^{i}_{k}$ is $L$-Lipschitz with respect to one norm for all
$i$ and $k$. Thus, the difference between above equations is

$\displaystyle\left|\theta^{i}_{k}(t)-\vartheta^{i}_{k}(\|\bm{\eta}\|_{1}t)\right|\leq$
$\displaystyle\eta_{i}\int^{t}_{0}\left|\xi^{i}_{k}({\vec{\bm{\theta}}}(s))-\xi^{i}_{k}({\vec{\bm{\vartheta}}}(\|\bm{\eta}\|_{1}s))\right|\,ds+\eta_{i}^{2}\int_{0}^{t}|e^{i}_{k}(s)|\,ds$
$\displaystyle\leq$
$\displaystyle\eta_{i}L\int^{t}_{0}\left\|{\vec{\bm{\theta}}}(s)-{\vec{\bm{\vartheta}}}(\eta_{i}s)\right\|_{1}\,ds+\eta_{i}^{2}Ct$
($L$-Lipschitz and LABEL:lem:err_const)

Therefore, by Gronwall’s inequality and $\eta_{i}\leq\eta_{*}$, we have

$\left\|{\vec{\bm{\theta}}}(t)-{\vec{\bm{\vartheta}}}(\|\bm{\eta}\|_{1}t)\right\|_{1}\leq\eta_{*}ndL\int^{t}_{0}\left\|{\vec{\bm{\theta}}}(s)-{\vec{\bm{\vartheta}}}(\|\bm{\eta}\|_{1}s)\right\|_{1}\,ds+(\eta_{*})^{2}ndCt\leq(\eta_{*})^{2}ndCte^{{\eta}_{*}ndLt}$

Because ${\vec{\bm{\vartheta}}}(\tau)\in D^{\prime}$, we can pick $\eta_{*}$
small enough so that
${\vec{\bm{\theta}}}(\tau/\|\bm{\eta}\|_{1})={\vec{\bm{\theta}}}_{\lfloor\tau/\|\bm{\eta}\|_{1}\rfloor}\in
D$ and
$\Phi({\vec{\bm{\theta}}}_{\lfloor\tau/\|\bm{\eta}\|_{1}\rfloor})<\inf_{{\vec{\bm{\theta}}}\notin
D}\Phi({\vec{\bm{\theta}}})$.

Now we show the second part that ${\vec{\bm{\theta}}}_{t}\in D$ for all
$t\geq\lfloor\tau/\|\bm{\eta}\|_{1}\rfloor$. First, with
LABEL:lem:potential_dis, we will prove that the potential function is
decreasing for all ${\vec{\bm{\theta}}}_{t}\notin D^{\prime}$ when $\eta_{*}$
small enough. We estimate three terms in LABEL:lem:potential_dis separately.
First, because ${\vec{\bm{\theta}}}^{*}\in D^{\prime}$ and
$\Theta^{n}\setminus D^{\prime}$ is compact, $\min_{{\vec{\bm{\theta}}}\notin
D^{\prime}}\|{\vec{\bm{\xi}}}({\vec{\bm{\theta}}})\|_{1}>0$ exists. Then
$\frac{\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{2\sum_{i}\lambda_{i}\eta_{i}}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}=\Omega(\max_{i}\eta_{i})$
By LABEL:lem:err_const,
$\max_{i}\lambda_{i}\eta_{i}^{2}\max_{i,k,{\vec{\bm{\theta}}}}|g^{i}_{k}({\vec{\bm{\theta}}})|\cdot\|\vec{{\bm{e}}}_{t}\|_{1}=O(\max_{i}\eta_{i}^{2})$.
Finally,
$d^{2}C_{4}\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|^{2}_{1}=O(\max_{i}\eta_{i}^{2})$.
Therefore, there exists $\eta_{*}$ small enough so that the potential function
$\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})<0$ for all
${\vec{\bm{\theta}}}_{t}\notin D^{\prime}$ and $\bm{\eta}$. Therefore
$\Phi({\vec{\bm{\theta}}}_{t})<\min_{{\vec{\bm{\theta}}}\notin
D}\Phi({\vec{\bm{\theta}}})$ for all
$t\geq{\lfloor\tau/\|\bm{\eta}\|_{1}\rfloor}$ which completes the proof. ∎

##  Appendix D Proofs and Details for Lemma LABEL:thm:converge_point

LABEL:lem:potential_conti, shows the value of $\Phi$ is decreasing in eq. 6,
and the decrease rate is lower bounded by the one norm of ${\vec{\bm{\xi}}}$.
Thus, if we can show the error between eq. 3 and eq. 6 is bounded by
$\|{\vec{\bm{\xi}}}\|_{1}$, we have the value of $\Phi$ is also decreasing on
eq. 3. The main challenge is that because
${\vec{\bm{\xi}}}({\vec{\bm{\theta}}}^{*})={\bm{0}}$, we need to control the
error as ${\vec{\bm{\xi}}}$ converges to zero but $\eta_{*}$ is fixed.

We first show three ancillary claims, LABEL:lem:normal, LABEL:lem:err_near and
LABEL:lem:tangent. LABEL:lem:normal show the vanishing components of
${\vec{\bm{\theta}}}_{t}$ decrease rapidly once the dynamic is in $D$.
LABEL:lem:err_near and LABEL:lem:tangent show the supporting component also
decrease once the vanishing components are small enough.

Given $(n,d,{\bm{A}},\bm{\lambda})$, we define the following constants
$C_{1}:=\frac{1}{4}\max_{i,l,{\bm{\theta}}\in\Theta^{n}}|g^{i}_{l}|$,
$C_{2}:=\frac{2}{\min_{i,k}(\theta^{*})^{i}_{k}}$,
$C_{3}:=ed\max(C_{1},C_{2})$, and
$C_{4}:=\max_{\imath}\lambda_{\imath}(\lambda_{\imath}+1)\max_{k,l}A_{k,l}$.
We require the maximum learning rate is bounded by $\eta_{*}$ which satisfies
the following conditions.

$\displaystyle\eta_{*}\max_{i,k,{\vec{\bm{\theta}}}\in\Theta^{n}}|g^{i}_{k}({\vec{\bm{\theta}}})|\leq\frac{1}{2}$
(12)
$\displaystyle\eta_{*}ndC_{3}\max_{{\vec{\bm{\theta}}}}\|{\vec{\bm{\xi}}}({\vec{\bm{\theta}}})\|_{1}\leq
1$ (13)

Additionally, given the bound of learning rate ratio,
$\frac{\max_{i}\eta_{i}}{\min_{i}\eta_{i}}\leq R_{\eta}$, we requires

$R_{\eta}^{2}\eta_{*}^{3}<\frac{\min_{i}\lambda_{i}^{2}}{16\sum_{i}\lambda_{i}}\min\left\\{\frac{4}{C_{3}\max_{i}(\lambda_{i})\max_{{\vec{\bm{\theta}}}}\|\vec{{\bm{g}}}\|_{1}},\frac{1}{d^{2}C_{4}}\right\\}$
(14)

Note that $\frac{\max\eta_{i}^{3}}{\min\eta_{i}^{2}}$ is less then the right
hand side of eq. 14. On the other hand, by LABEL:thm:converge_const, we can
pick $D$ small enough so that the following conditions holds.

$\displaystyle\frac{1}{2}\min_{i\in[n],k\in
S_{i}}(\theta^{*})^{i}_{k}\leq\min_{i\in[n],k\in S_{i},{\vec{\bm{\theta}}}\in
D}\theta^{i}_{k}$ (15)

We first show for all $i$ and $k\in\bar{S}_{i}$, $\theta^{i}_{t,k}$ is
decreasing and converges to zero exponentially fast as $t$ increases. Because
${\vec{\bm{\theta}}}^{*}$ is a proper performative stable,
$\sum_{l}(\theta^{*})^{i}_{l}e^{-\eta_{i}g^{i}_{l}({\vec{\bm{\theta}}}^{*})}=e^{-\eta_{i}\bar{g}^{i}({\vec{\bm{\theta}}}^{*})}>e^{-\eta_{i}g^{i}_{k}({\vec{\bm{\theta}}}^{*})}$
for all $i$ and $k\in\bar{S}_{i}$. We can take $\eta_{*}$, $\epsilon_{1}$, and
$D$ small enough so that for all ${\vec{\bm{\theta}}}\in D$ and all learning
rate profile $\bm{\eta}$ with $\max\eta_{i}\leq\eta_{*}$,

$e^{-\eta_{i}g^{i}_{k}}<(1-\epsilon_{1})\sum_{l}\theta^{i}_{l}e^{-\eta_{i}g^{i}_{l}},i\in[n],k\in\bar{S}_{i}$
(16)

######  Claim D.1 (name = Vanishing components, label=lem:normal).

Given $\eta_{*},\epsilon_{1}$, and $D$ in eq. 16, if
${\vec{\bm{\theta}}}_{t}\in D$ for all $t\geq 0$, for all $i\in[n]$ and $k\in
S_{i}$, $\theta^{i}_{k}(t)$ is decreasing in $t$ and for all $t\geq 0$

$0\leq\theta^{i}_{t,k}\leq\theta^{i}_{0,k}e^{-\epsilon_{1}t}.$

###### Proof of LABEL:lem:normal.

By eq. 16, for all $t\geq 0$,
$\theta^{i}_{t+1,k}=\theta^{i}_{t,k}\frac{\exp(-\eta_{i}g^{i}_{t,k})}{\sum_{l}\theta^{i}_{t,l}\exp(-\eta_{i}g^{i}_{t,l})}\leq(1-\epsilon_{1})\theta^{i}_{t,k}$.
Therefore, $\theta^{i}_{t,k}$ is decreasing, and
$\theta^{i}_{t,k}\leq\theta^{i}_{0,k}e^{-\epsilon_{1}t}$. ∎

######  Claim D.2 (label = lem:err_near).

There exists a constant $C_{3}$ such that for all
${\vec{\bm{\theta}}}\in\Theta^{n}$ with $\delta_{1}>0$ so that
$\|\vec{\bm{\xi}}({\vec{\bm{\theta}}})\|_{1}\geq 2\sqrt{\delta_{1}}$, and
$|\xi^{i}_{k}({\vec{\bm{\theta}}})|\leq\delta_{1}$ for all $i\in[n]$ and
$k\in\bar{S}_{i}$, then

$|e^{i}_{k}({\vec{\bm{\theta}}})|\leq
C_{3}\|{\vec{\bm{\xi}}}({\vec{\bm{\theta}}})\|_{1}^{2},$ (17)

for all $i\in[n]$ and $k\in[d]$.

LABEL:lem:err_near shows if the one norm of ${\vec{\bm{\xi}}}$ is much bigger
than the vanishing components, the error term $\vec{{\bm{e}}}$ can be bounded
by the $\|{\vec{\bm{\xi}}}\|_{1}^{2}$. Moreover, LABEL:lem:normal ensures that
the vanishing components decrease rapidly, so the condition of
LABEL:lem:err_near readily holds.

###### Proof of LABEL:lem:err_near.

Given ${\vec{\bm{\theta}}}$ and $\delta_{1}>0$ that satisfy the condition, we
first show two inequalities to bound
$\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2}$ for supporting and vanishing
component respectively. For a vanishing component $k\in\bar{S}_{i}$,

$\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2}\leq\max_{i,l,{\bm{\theta}}\in\Theta^{n}}|g^{i}_{l}|\cdot|\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})|\leq
4C_{1}\cdot\delta_{1}\leq C_{1}\|{\vec{\bm{\xi}}}\|_{1}^{2}.$ (18)

Then for a supporting component $k\in S_{i}$, with eq. 15 we have

$\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})^{2}\leq\frac{1}{\min_{i,l,{\vec{\bm{\theta}}}\in
D}\theta^{i}_{l}}(\theta^{i}_{k}(g^{i}-g^{i}_{k}))^{2}\leq\frac{2}{\min_{i,k}(\theta^{*})^{i}_{k}}|\xi^{i}_{k}|^{2}\leq
C_{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}.$ (19)

Now we use above two inequalities to approximate eq. 3. For nominator, because
$1+x\leq\exp(x)\leq 1+x+\frac{e}{2}x^{2}$ for all $x\leq 1$,
$\theta^{i}_{k}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{k}))\geq\theta^{i}_{k}+\eta_{i}\theta^{i}_{k}(\bar{g}^{i}-g^{i}_{k})=\theta^{i}_{k}+\eta_{i}\xi^{i}_{k}$.
On the other hand, because $\eta_{i}(\bar{g}^{i}-g^{i}_{k})\leq 1$ by eq. 12,
$\theta^{i}_{k}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{k}))\leq\theta^{i}_{k}+\eta_{i}\xi^{i}_{k}+\frac{e}{2}\theta^{i}_{k}\eta_{i}^{2}(\bar{g}^{i}-g^{i}_{k})^{2}$.
By eqs. 18 and 19, we have

$0\leq\theta^{i}_{k}e^{\eta_{i}(\bar{g}^{i}-g^{i}_{k})}-\theta^{i}_{k}-\eta_{i}\xi^{i}_{k}\leq\frac{e}{2}\max(C_{1},C_{2})\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}$
(20)

For denominator, we sum over eq. 20. Because $\sum_{l}\theta^{i}_{l}=1$ and
$\sum_{l}\theta^{k}_{l}(\bar{g}^{i}-g^{i}_{l})=0$, we have

$0\leq\sum_{l}\theta^{i}_{l}e^{\eta_{i}(\bar{g}^{i}-g^{i}_{l})}-1\leq\frac{ed}{2}\max(C_{1},C_{2})\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}$
(21)

Given $i\in[n]$ and $k\in[d]$, we apply the above equation to eq. 3. For upper
bounds, we have

$\displaystyle\eta_{i}^{2}e^{i}_{k}({\vec{\bm{\theta}}}_{t})=$
$\displaystyle\frac{\theta^{i}_{k}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{k}))}{\sum_{l}\theta^{i}_{l}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{l}))}-\theta^{i}_{t,k}-\eta_{i}\xi^{i}_{t,k}$
$\displaystyle\leq$
$\displaystyle\theta^{i}_{t,k}e^{-\eta_{i}g^{i}_{k}({\vec{\bm{\theta}}}_{t})}-\theta^{i}_{t,k}-\eta_{i}\xi^{i}_{t,k}$
(by eq. 21) $\displaystyle\leq$
$\displaystyle\frac{e\max(C_{1},C_{2})}{2}\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}$
(by eq. 20)

For lower bounds,

$\displaystyle\eta_{i}^{2}e^{i}_{k}({\vec{\bm{\theta}}}_{t})=$
$\displaystyle\frac{\theta^{i}_{k}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{k}))}{\sum_{l}\theta^{i}_{l}\exp(\eta_{i}(\bar{g}^{i}-g^{i}_{l}))}-\theta^{i}_{t,k}-\eta_{i}\xi^{i}_{t,k}$
$\displaystyle\geq$
$\displaystyle\frac{\theta^{i}_{t,k}+\eta_{i}\xi^{i}_{t,k}}{1+\frac{ed\max(C_{1},C_{2})}{2}\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}}-\theta^{i}_{t,k}-\eta_{i}\xi^{i}_{t,k}$
(by eqs. 21 and 20) $\displaystyle\geq$
$\displaystyle-(\theta^{i}_{t,k}+\eta_{i}\xi^{i}_{t,k})\left(\frac{ed\max(C_{1},C_{2})}{2}\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}\right)$
($1/(1+x)\geq 1-x$) $\displaystyle\geq$ $\displaystyle-
ed\max(C_{1},C_{2})\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}$
($\theta^{i}_{t,k}\leq 1$ and $\eta_{i}\xi^{i}_{t,k}\leq 1$ by eq. 12)

Therefore, with $C_{3}:=ed\max(C_{1},C_{2})$ we finish the proof. ∎

######  Claim D.3 (label = lem:tangent).

There exists $\epsilon_{2}>0$ so that for all
${\vec{\bm{\theta}}}_{t}\in\Theta^{n}$ and $\delta_{1}>0$ so that
$\|\vec{\bm{\xi}}({\vec{\bm{\theta}}}_{t})\|_{1}\geq 2\sqrt{\delta_{1}}$, and
$|\xi^{i}_{k}({\vec{\bm{\theta}}}_{t})|\leq\delta_{1}$ for all $i\in[n]$ and
$k\in\bar{S}_{i}$, then
$\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})\leq\epsilon_{2}\|\vec{\bm{\xi}}({\vec{\bm{\theta}}}_{t})\|_{1}^{2}$.

###### Proof for LABEL:lem:tangent.

By LABEL:lem:potential_dis,

$\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})\leq\frac{-\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{2\sum_{i}\lambda_{i}\eta_{i}}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}+\max_{i}\lambda_{i}\eta_{i}^{2}\max_{i,k,{\vec{\bm{\theta}}}}|g^{i}_{k}({\vec{\bm{\theta}}})|\cdot\|\vec{{\bm{e}}}_{t}\|_{1}+d^{2}C_{4}\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|^{2}_{1}.$

We can bound the later two terms by LABEL:lem:err_near. For the second term,
$\|\vec{{\bm{e}}}_{t}\|_{1}\leq ndC_{3}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}$. For
the third term,

$\displaystyle\left\|{\vec{\bm{\theta}}}_{t+1}-{\vec{\bm{\theta}}}_{t}\right\|_{1}\leq$
$\displaystyle\sum_{i,k}\left(\eta_{i}|\xi^{i}_{t,k}|+C_{3}\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}\right)$
$\displaystyle\leq$
$\displaystyle\max_{i}\eta_{i}\|{\vec{\bm{\xi}}}\|_{1}+ndC_{3}\max_{i}\eta_{i}^{2}\|{\vec{\bm{\xi}}}\|_{1}^{2}.$
$\displaystyle\leq$ $\displaystyle 2\max_{i}\eta_{i}\|{\vec{\bm{\xi}}}\|_{1}$
( by eq. 13)

With above inequalities, by eq. 14, we have
$\frac{\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{4\sum_{i}\lambda_{i}\eta_{i}}>\max_{i}\lambda_{i}\eta_{i}^{2}\max_{i,k,{\vec{\bm{\theta}}}}|g^{i}_{k}({\vec{\bm{\theta}}})|ndC_{3}$
and
$\frac{\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{4\sum_{i}\lambda_{i}\eta_{i}}>4d^{2}C_{4}\max_{i}\eta_{i}^{2}$.
Therefore there exists a constant

$\epsilon_{2}:=\frac{\min_{i}\lambda_{i}^{2}\eta_{i}^{2}}{2\sum_{i}\lambda_{i}\eta_{i}}-\max_{i}\lambda_{i}\eta_{i}^{2}\max_{i,k,{\vec{\bm{\theta}}}}|g^{i}_{k}({\vec{\bm{\theta}}})|ndC_{3}-4d^{2}C_{4}\max_{i}\eta_{i}^{2}>0$

so that
$\Phi({\vec{\bm{\theta}}}_{t+1})-\Phi({\vec{\bm{\theta}}}_{t})<-\epsilon_{2}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}$.
∎

###### Proof of LABEL:thm:converge_point.

To prove $\lim_{t\to\infty}{\vec{\bm{\theta}}}_{t}={\vec{\bm{\theta}}}^{*}$,
there are two equivalent ways to measure the progress, besides
$\|{\vec{\bm{\theta}}}_{t}-{\vec{\bm{\theta}}}^{*}\|_{1}$. First because
${\vec{\bm{\theta}}}^{*}$ is an isolated fixed point of eq. 6,
${\vec{\bm{\theta}}}_{t}$ converges to ${\vec{\bm{\theta}}}^{*}$ if and only
if $\lim_{t\to\infty}\vec{\bm{\xi}}({\vec{\bm{\theta}}}_{t})=\vec{{\bm{0}}}$.
On the other hand, because $\Phi$ is strictly convex and and
${\vec{\bm{\theta}}}^{*}$ is the minimum point, ${\vec{\bm{\theta}}}_{t}$
converges to ${\vec{\bm{\theta}}}^{*}$ if and only if
$\lim_{t\to\infty}\Phi({\vec{\bm{\theta}}}_{t})=\min_{{\vec{\bm{\theta}}}}\Phi({\vec{\bm{\theta}}})$.
With these two equivalent conditions, given any $\epsilon>0$, there exists
$\delta>0$ so that
$\|{\vec{\bm{\theta}}}-{\vec{\bm{\theta}}}^{*}\|_{1}<\epsilon$ when

${\vec{\bm{\theta}}}\in
V_{\delta}:=\left\\{{\vec{\bm{\theta}}}:\Phi({\vec{\bm{\theta}}})\leq\max_{{\vec{\bm{\theta}}}^{\prime}:\|\vec{\bm{\xi}}({\vec{\bm{\theta}}}^{\prime})\|_{1}\leq\delta}\Phi({\vec{\bm{\theta}}}^{\prime})\right\\}.$

Therefore, it is sufficient for us to show for all $\delta>0$, there is
$t_{\delta}$ so that ${\vec{\bm{\theta}}}_{t}\in V_{\delta}$ for all $t\geq
t_{\delta}$. With technical LABEL:lem:err_const, LABEL:lem:normal and
LABEL:lem:err_near, our proof has two parts. First we show that the dynamic
hits $V_{\delta}$. Then, the dynamic stays in $V_{\delta}$.

For the first part, given $\delta>0$ and $0<C<1$, by LABEL:lem:normal there
exists $T_{1}$ such that each vanishing component $|\xi^{i}_{t,k}|\leq
C^{2}\delta^{2}/4$ for all $t\geq T_{1}$. Then by LABEL:lem:tangent, there
exists $T_{2}\geq T_{1}$ such that $\|{\vec{\bm{\xi}}}_{T_{2}}\|_{1}\leq
C\delta$. Otherwise, the value of $\Phi$ decreases by a nonzero constant
$\epsilon_{2}\|{\vec{\bm{\xi}}}_{t}\|_{1}^{2}\geq C\epsilon_{2}\delta^{2}>0$
at each round which contradicts that the minimum of $\Phi$ bounded.

For the second part, if $\|{\vec{\bm{\xi}}}_{t}\|_{1}\leq C\delta\leq\delta$
for all $t\geq T_{2}$, then we finish the proof. Otherwise, there exists
$\tau\geq T_{2}$ so that $\|{\vec{\bm{\xi}}}_{\tau}\|_{1}\leq
C\delta<\|{\vec{\bm{\xi}}}_{\tau+1}\|_{1}$. Now we prove that
$\Phi({\vec{\bm{\theta}}}_{\tau+1})\leq\max_{{\vec{\bm{\theta}}}^{\prime}:\|\vec{\bm{\xi}}({\vec{\bm{\theta}}}^{\prime})\|_{1}\leq\delta}\Phi({\vec{\bm{\theta}}}^{\prime})$.
Because the difference between ${\vec{\bm{\theta}}}_{\tau+1}$ and
${\vec{\bm{\theta}}}_{\tau}$ is
$\|{\vec{\bm{\theta}}}_{\tau+1}-{\vec{\bm{\theta}}}_{\tau}\|_{1}\leq\max_{i}\eta_{i}\|{\vec{\bm{\xi}}}_{\tau}\|_{1}+\max_{i}\eta_{i}^{2}\|\vec{{\bm{e}}}_{\tau}\|_{1}\leq
2\max_{i}\eta_{i}\|{\vec{\bm{\xi}}}_{\tau}\|_{1}$ when $\eta_{*}$ is small
enough, and ${\vec{\bm{\xi}}}$ is a $L_{\xi}$-Lipschitz ${\vec{\bm{\theta}}}$
for some constant $L_{\xi}$ in one norm, we have

$C\delta<\|{\vec{\bm{\xi}}}_{\tau+1}\|_{1}\leq\|{\vec{\bm{\xi}}}_{\tau}\|_{1}+\|{\vec{\bm{\xi}}}_{\tau+1}-{\vec{\bm{\xi}}}_{\tau}\|_{1}\leq\|{\vec{\bm{\xi}}}_{\tau}\|_{1}+2L_{\xi}\max_{i}\eta_{i}\|{\vec{\bm{\xi}}}_{\tau}\|_{1}\leq\delta,$
(22)

when $C$ is small enough so that $C(1+2L_{\xi}\max_{i}\eta_{i})\leq 1$.
Therefore, $\|{\vec{\bm{\xi}}}_{\tau+1}\|_{1}\leq\delta$ and
$\Phi({\vec{\bm{\theta}}}_{\tau+1})\leq\max_{{\vec{\bm{\theta}}}^{\prime}:\|\vec{\bm{\xi}}({\vec{\bm{\theta}}}^{\prime})\|_{1}\leq\delta}\Phi({\vec{\bm{\theta}}}^{\prime})$.
Finally, because $|\xi^{i}_{t,k}|\leq C^{2}\delta^{2}/4$ for all
$t\geq\tau+1$, by LABEL:lem:tangent, the potential function is decreasing for
all $t\geq\tau+1$, unless $\|{\vec{\bm{\xi}}}\|_{t}\leq C\delta$. Both make
the potential function less than
$\max_{{\vec{\bm{\theta}}}^{\prime}:\|\vec{\bm{\xi}}({\vec{\bm{\theta}}}^{\prime})\|_{1}\leq\delta}\Phi({\vec{\bm{\theta}}}^{\prime})$
which completes the proof. ∎

##  Appendix E Proof and Detail for Theorem LABEL:thm:chaos_one

###### Proof of LABEL:lem:three.

Define $P_{L}(x):=\alpha(L)(x-\beta(L))$ which is increasing for all $L$
because $\alpha(L)>0$. With $P_{L}$,
$f_{\alpha(L),\beta(L)}(x)=\frac{x}{x+(1-x)\exp(P_{L}(x))}$. Take
$x_{1}(L)=x_{1}:=1-1/\alpha(L)$,
$x_{2}(L)=x_{2}:=f_{\alpha(L),\beta(L)}(x_{1}(L))$, and
$x_{3}(L)=x_{3}:=f_{\alpha(L),\beta(L)}(x_{2}(L))$. We will define $x_{0}(L)$
later. We will omit $L$ and use $x_{1},x_{2}$, and $x_{3}$.

To define $x_{0}(L)$, we set $y(L):=\beta(L)/2$, and want to show

$f_{\alpha(L),\beta(L)}(y)>x_{1},$ (23)

which is equivalent to $(\alpha(L)-1)(1-y(L))\exp(P_{L}(y(L)))<y(L)$. When $L$
is large enough, we have
$\beta(L)\in(\frac{2\beta_{\infty}}{3},\frac{4\beta_{\infty}}{3})$.
Additionally because $\alpha(L)>0$, we have
$P_{L}(y(L))=-\frac{1}{2}\alpha(L)\beta(L)<-\frac{1}{3}\alpha(L)\beta_{\infty}$.
Therefore, we have
$(\alpha(L)-1)(1-y(L))e^{P_{L}(y(L))}\leq\alpha(L)e^{-\alpha(L)\frac{\beta_{\infty}}{3}}<\frac{\beta_{\infty}}{3}<y(L)$
when $L$ is large enough, and prove eq. 23. On the other hand, because
$\beta(L)<\frac{4}{3}\beta_{\infty}$ and $P_{L}(\beta(L))=0$, we have
$f_{\alpha(L),\beta(L)}(\beta(L))=\beta(L)<\frac{1}{2}(\beta_{\infty}+1)$.
Moreover, $\frac{1}{2}(\beta_{\infty}+1)<1-\frac{1}{\alpha(L)}$, holds when
$L$ is large enough. These two imply

$f_{\alpha(L),\beta(L)}(\beta(L))=\beta(L)<x_{1}(L).$ (24)

Combining eqs. 23 and 24, by intermediate value theorem, there exists $x_{0}$
such that

$f_{\alpha(L),\beta(L)}(x_{0})=x_{1}\text{ with }y<x_{0}<\beta(L)<x_{1}.$ (25)

Now we show $x_{3}<x_{0}$. With $1-x_{1}(L)=1/\alpha(L)$ and $0<x_{1}<1$, we
have
$x_{2}=f_{\alpha(L),\beta(L)}(x_{1})=\frac{x_{1}}{x_{1}+\alpha(L)^{-1}\exp(P_{L}(x_{1}))}\leq\frac{\alpha(L)}{\exp(P_{L}(x_{1}))}$.
Because $\beta_{\infty}<1/2$, when $L$ is large enough,
$x_{1}(L)=1-\frac{1}{\alpha(L)}>\frac{1}{4}(2\beta(L)+3)$ and, thus,
$P_{L}(x_{1})>\alpha(L)\left(\frac{3}{4}-\frac{\beta(L)}{2}\right)$.
Therefore, we have

$x_{2}\leq\alpha(L)\exp\left(-\alpha(L)\left(\frac{3}{4}-\frac{\beta(L)}{2}\right)\right)$
(26)

Finally, because $P_{L}(x_{2})\geq P_{L}(0)=-\beta(L)$, we get

$\displaystyle x_{3}=$ $\displaystyle
f_{\alpha(L),\beta(L)}(x_{2})\leq\frac{x_{2}}{x_{2}+(1-x_{2})\exp(-\alpha(L)\beta(L))}$
$\displaystyle=$
$\displaystyle\frac{x_{2}\exp(\alpha(L)\beta(L))}{1+x_{2}(\exp(\alpha(L)\beta(L))-1)}$
$\displaystyle\leq$ $\displaystyle x_{2}\exp(\alpha(L)\beta(L))$ (since
$\exp(\alpha(L)\beta(L))>1$ when $L$ is large) $\displaystyle\leq$
$\displaystyle\alpha(L)\exp\left(\alpha(L)\left(\beta(L)-\left(\frac{3}{4}-\frac{\beta(L)}{2}\right)\right)\right)$
(eq. 26) $\displaystyle=$
$\displaystyle\alpha(L)\exp\left(\frac{3\alpha(L)}{2}\left(\beta(L)-\frac{1}{2}\right)\right)$

Finally, because $\beta_{\infty}<1/2$, $x_{3}$ converges to $0$ when $L$ is
large enough. Therefore,

$x_{3}<y<x_{0}.$ (27)

By eqs. 25 and 27, we have $x_{3}<x_{0}<x_{1}$ which completes the proof. ∎