Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 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.
main_review: # Main Review

The paper is clearly written and its main theorems are supported by proofs and numerical simulations.
The strength of the paper is that it extends 
a relatively new model (2020) to a cooperative multi-agent setting. 
The extension to the multi-agent case has both positive 
and negative results 
(convergence and chaos),
and the authors provide theoretical justification for both occurances by leveraging 
past work on learning in potential games.
These results are already known for other classes of conjestion games, so the authors support the 
previous literature 
by showing that they are also true for constrained linear models in this class of problems.

We agree with the authors that this work only scratches the surface of the in multi-agent performative prediction. 
The model is an original and novel contribution (to the best of my knowledge), but the results are confirmatory. The results are mostly shown by previous work already since the model trivially has a potential function. So it is unclear to me if the work is significant for this venue.
I also think some commentary on stability concept (the second part of definition 2.1) would be helpful towards motivating the significance of the work.
How does the multi-agent stability concept differ from the stability concept in (Perdomo 2020)? 
Can you point to the differences (existence, uniqueness or stability..) 
or what makes this class much more challenging to solve? This could be useful for future work in understanding when chaos occurs, for example.

The quality of the paper can be improved in some minor ways, especially by paying attention to details. 
For example, the last equation on page 3, the pipe operator in the lefthand side is undefined. 
Also, the use of \theta_0 is different in section 2.1 and 2.2, and I think it can be confusing.
Section 2.3 just consists of a definition and nothing else. Can you explain it or at the very least provide a reference?
There is a typo in the last sentence of section 3.
Pay attention to capitalization, and espeically in the reference list, where many typos can be found.

(A minor comment on style: 
there is a missed opportunity to 
maintain the parallelism 
of "convergence to chaos" in your title
in Figure 1 by 
sorting the figures in that order, ie putting (a) and (d) in the rightmost column.)

summary_of_the_review: 

Overall the paper has a central point by presenting a framework of multi-agent learning. The model is cooperative, so a potential function exists and learning converges for slow learning rate regime. 
A discussion section is lacking, in particular with regard to the significance of the work and results. 
What insights can be provided by the analysis from the paper?
Currently the conclusion section include mostly a list of future applications. 

The claims in the paper are supported and correct to the best of my knowledge. The significance of the results is debatable but the model is indeed novel. The empirical data shows an example of chaos and two examples of convergence, with and without noise. In my opinion, the model is novel enough for me to recommend a 6, but the technical results are expected and perhaps maybe that can push it to below the acceptance threshold.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a multiagent extension of the performative prediction framework in which multiple agents try to predict the same outcome, which influences the outcome they want to predict. The paper then shows scenarios and conditions for stability and for chaotic behaviour.

main_review: Strengths:
The framework of performative predictions is very interesting, with potential applications that are beyond the standard supervised learning methods. Its extension to a multiagent setting widens the  applicability of the framework in the real world.
The paper studies the emergence of instabilities both theoretically and empirically.

Weaknesses:
1. I am not convinced by some of the derivations:
1.1. Proof of Prop 3.1 should be very simple but it is confusing. The authors refer to the "KKT condition" --which is itself confusing as the KKT are a set of conditions that have to hold together, not just one--, but it is not clear which one of the KKT conditions is referred by the inequality on the partial derivatives. What does it mean that the partial derivative on one component, $k$, is less or equal than the partial derivative in another component, $l$?
1.2. In the second part of the proof of Prop 3.1, the authors use the positive definite Hessian to prove strict convexity, do they mean strong convexity?
1.3. A performative optimal point (Def 2.1) is just a Pareto solution of the multiobjective problem (indeed it could probably be generalised to any convex combination of each agent's losses). On the other hand, performative stability is a global solution of the objective problem, and is a much stronger condition than the Performative (Pareto) optimality. Indeed, it is trivial to show that the former implies the latter, so I don't understand the comment before Prop. 3.2.
1.4. In Eq. (4), the authors define the fixed point of (3) as the average gradient. Why is so? The argument at the end of page 5, in which they multiply numerator and denominator by the average gradient seems rather loose, since you could multiply both factors by any other value and still claim that this value is the convergence point. I think they have to formally prove that:
$\lim_{k \rightarroy \infty} g_k^i(\theta) = \overline{g}^i(\theta) \in \Re^d$.
Perhaps this apparently circular reasoning can be easily fixed by proving Theorem 4.1 before Eq. (4). 

2. Discussion of connection with related approaches is missing. 
2.1. The proposed approach reminds me of the replicator dynamics from evolutionary game theory, for which the emergence of chaos has also been studied. 
2.2. In order to prove performative stability, could the authors rely on the strong-monotonicity of the gradient and well known results for finite-dimensional variational inequality theory (see, e.g., Scutari et al., 2010)?
2.3. Conditions on the learning rate for the chaotic behaviour of gradient descent have been studied in the literature. How the current results relate to these previous results? 

3. The simulations show oscillatory behaviour, but it is not clear from the experiments that this is actually chaotic behaviour. I would have expected to see at least sensitivity to initial conditions, and ideally negative Lyapunov exponents computed from the time series.


Minor comment:
It is clear that the algorithm will converge for small enough learning rate, and it can oscillate or diverge beyond that threshold. Some motivation on why it is important to study the chaotic behaviour in particular would help to appreciate the impact of this work.


(Scutari et al., 2010), Gesualdo Scutari, Daniel P. Palomar, Francisco Facchinei, and Jong-Shi Pang, "Convex Optimization, Game Theory, and Variational Inequality Theory", IEEE Signal Processing Magazing 35, May 2010

summary_of_the_review: The extension of the performative predictions framework to multiagent systems is an interesting problem. and even the scenario under study with linear predictors and MSE loss greatly simplifies the analysis, I appreciate this is a first step.
This is mainly a theoretical paper, but some of the mathematical derivations have raised some questions.

Metareview
----------------
The authors have responded to most of my comments clearing my concerns on the derivations. I think that an experiment showing sensitivity to initial conditions is missing. Although the novelty seems incremental with respect to previous works, there are a few small innovations, so I am increasing my score to 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 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.
main_review: strengths:

(1) The problems and settings are presented clearly, the results and intuitions are also explained without obscurity. The paper is well written and easy to follow.

(2) The results look correct and good as far as I have checked. As claimed, this is the first time "where such formal chaotic results are established in settings related to performative prediction and supervised learning more generally". I think this paper makes a reasonable contribution.

weakness:

(1) The technical novelty and difficulty seem restricted to me.

(1a) The first main result of "using small learning rate EGD is stable" is kind of a standard result as expected, and also the techniques are based on standard analysis (potential functions and approximating continuous gradient flows).

(1b) The second main result of "using large enough learning rate EGD is Li-Yorke chaotic" is also similar to existing work, e.g., the observation of EGD is chaotic in other games (Palaiopanos et al., 2017). The analysis is based on similar idea of constructing a recurrent behaviour with period three. 

As far as I can see, the main difference and novelty is to apply those relevant techniques in performative prediction, which is a bit different with traditional supervised learning. However, performative prediction itself is also a special kind of game / reinforcement learning, which makes the contribution seem not very insightful given we have existing observation of EGD is chaotic in other game settings.
summary_of_the_review: Overall, I think this paper makes a reasonable contribution, showing that the behaviours of using exponentiated gradient descent differ with using different learning rates. However, given there already exist observations and results about exponentiated gradient descent could be chaotic in several game settings, and the performative prediction studied in this paper is also a special game setting, I consider the contributions and technical novelty in this work on an incremental level.


----update----

I would like to thank the authors for the feedback. My main concerns are addressed and thus I would increase my score.
review_title: null

Meta-review: In this paper, the authors extend the performative prediction framework of Perdomo et al. (2020) to a multi-agent, game-theoretic setting, and they examine how and when multi-agent performative learning may lead to performative stability/optimality.

The authors' results and contributions can be summarized as follows:
- They consider a multi-agent location-scale distribution map with parameters constrained in a simplex, and they study the dynamics of an exponentiated gradient descent algorithm (EGDA for short) inspired by Kivinen and Warmuth (1997).
- If the learning rate is small enough, the authors show that EGDA converges to a performatively stable point (under the same assumptions that guarantee existence of a convex potential).
- On the other hand, if the learning rate is large, the algorithm behaves chaotically.

The reviewers' initial assessment was mixed, but after the authors' rebuttal, some concerns were partially addressed and the scores of the paper were upgraded to borderline positive. On a point-by-point basis, the authors' result on the convergence of EGDA with a small learning rate was appreciated by the reviewers, but it was not otherwise deemed significant enough relative to existing convergence results for gradient methods. Instead, most of the discussion centered on the authors' result on chaos (Theorem 4.6), which was viewed as the most significant contribution of the paper. However, continued discussion between committee members revealed that this result follows directly from Theorem 3.11 and Corollary 3.12 of the arxiv preprint "A family of chaotic maps from game theory" by T. Chotibut, F. Falniowski, M. Misiurewicz, and G. Piliouras <https://arxiv.org/abs/1807.06831>, which is not discussed in the paper. [As was pointed out, the update map (7) of the paper coincides with the update rule (7) of the arxiv preprint, and the proof techniques are likewise identical.]

This overlap with previous work was considered a "big omission" and it pushed the paper below the acceptance threshold. In the end, the paper was not supported by any of the reviewers, so a "reject" recommendation was made.
Decision: Reject