Strategic Distribution Shift of Interacting Agents via Coupled Gradient Flows

Summary

The authors consider a the problem where the change in a distribution for an objective can be modeled as a set of coupled nonlinear parabolic PDEs. These methods have nonlocal interactions and describe a model of the influence of the model on the population and vice-versa. Additionally, these correspond to the evolution of the measures associated with the Wasserstein gradient flow that minimizes a set of defined energy functionals, which relate to the original optimization problem. Such equations have been well studied in terms of the granular media equation and a wide theory has been devoted to existence and uniqueness of their solution. Two scenarios are considered: one with cooperation and another with an adversarial behavior of the population. The main results of the paper are convergence rates to the steady state for the coupled PDEs. The behavior of both the optimization algorithm and the population are studied in some numerical experiments at the end of the paper. The numerical experiments illustrate the importance of considering such a model rather than relying on more simple summary statistics for notions of distributional shift.

Strengths

The proposed model is a very elegant model for describing distribution shift and the feedback mechanisms between the shift in population and objective functions. It provides a much richer class of perturbations than what is generally seen in the literature in cases such as distributionally robust optimization or in adversarial optimization. The model also has implications in providing additional distribution information (beyond low order moments) at equilibrium. The authors show the importance of this where different geometries of the distribution can imply different effects on the population distribution. Overall, the paper is well written, provides nice ideas, and describes a more unique take on the problem of distribution shifts.

Weaknesses

The numerical evaluation is a bit limited, but I think that’s not a problem since most of the results are theoretical. Still, it would be nice to see some more concrete applications of the theory by simulating the PDEs described, where, for example, all components are not simulated. It also appears that this may be difficult to apply to real world scenarios as the authors alluded in their limitations. A real application where all components need to be estimated was not discussed, but that's beyond the scope of the paper. Some of the assumptions are somewhat strong, but these are usually made to provide convergence and existence of solutions of these PDEs. In that regard, processes that satisfy these assumptions may not be entirely general, but that’s not a big deal since the authors clearly constrain their analysis based on the assumptions they make.

Questions

The second equation should be the argmin of x \in R^d? Is there intuition on how the different functionals could be estimated e.g. for a particular application? Or is it assumed that these are already known? Related to the previous question, how difficult would it be to apply to a real scenario, beyond the simulations the authors provided? This may not be a focus of the paper, but seems like something worth discussing. Could particle methods be used to solve the problem in high dimensions as is sometimes done in high dimensional cases? For example, this was explored in [1] and I was wondering if it could be applied in this scenario by approximating the associated McKean-Vlasov process (there might be an issue with some of the terms in the PDEs)? [1] Crucinio et al, Solving Fredholm Integral Equations of the First Kind via Wasserstein Gradient Flows, 2022

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The authors sufficiently discuss limitations of their work.

Summary

This paper studies the long-term behavior of a dynamical system where there are distribution shifts in response to algorithmic decision-making. The authors derive PDEs to capture distributional changes and describe the result of the algorithm for both the coorperative setting and the competitive setting. Under certain regularization conditions, it is shown that the PDEs converge to unique steady-state distribution. Finally, some numerical simulations are conducted to iilustrate the problem.

Strengths

1. The paper is well-written and not hard to read. All definitions, theoretical results and experiments are accompanied by explanations when necessary. Moreover, the authors motivate the problem of interest in a very convincing way. 2. The paper is technically solid. The process of interaction between algorithm and population is rigorously modelled and its asymptotic behavior is characterized.

Weaknesses

The authors do not include many discussions on the insights provided by the theoretical findings. This is probably because the limit distribution of the PDEs are difficult to characterize. Moreover, the setting considered is over-simplified since it only contains one agent. Given that this paper is kind of a first step towards mathematical analysis of algorithm interaction, I think these flaws are totally acceptable and can be left for future work.

Questions

1. Many real-world applications involve discrete rather than continuous time. Is it possible to generalize the analysis in this paper to discrete time setting? 2. Is it reasonable to assume that $f_1,f_2$ are convex?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have adequately addressed the limitations and potential negative societal impact of their work.

Summary

This paper presents a framework for analyzing dynamics of distribution shift that captures feedback loop between learning algorithms and the distributions that they are deployed on using a coupled differential equations model. The paper considers both co-operative and competitive settings and suggests that a learner updated with gradient descent converges to steady state both in finite and infinite dimensions (in terms of model parameters).

Strengths

The paper presents a rigorous treatment of the problem and presents general results, although I am not an expert in this area and cannot present a rating with any meaningful confidence.

Weaknesses

The paper works with several assumptions that I do not see a clear cut comparison of how these assumption compares against prior work, so it is unclear how general these results are.

Questions

One way to make the paper appeal to a general audience is to have a discussion surrounding claims and assumptions comparing this work against prior results in the literature.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

n/a

Summary

The paper proposes a new framework for analyzing the interaction and feedback loop between learning algorithms and the distributions on which they are deployed. The framework in the paper is more general than prior models, allowing to capture more complex interactions and shifts in the algorithm and distribution. This is done using a partial differential equation that modifies the algorithm\distribution in a way that optimizes its cost with respect to the choice of distribution\algorithm. Under several assumptions which include strong convexity, the authors were able to prove that gradient flow converges and provide fast convergence rates. The authors are provide experimental results for a simple 1-dimensional setting which demonstrate that their framework can explain general phenomenon which are not explained by prior models, such as polarization.

Strengths

The paper is well-written and easy to follow. Moreover, as mentioned above, the framework in the paper offers several advantages compared to prior frameworks, allowing to capture more complex interactions and shifts of the distribution. This model is therefore able (via simple examples) to theoretically explain forms of distribution shifts which we see in practice such as polarization.

Weaknesses

1. While the framework allows for complex forms of shifts of the model and distribution, the analysis assumes that the model\distribution changes to be the exact minimizer of a certain cost function. This may be a little strict in general. Can the same analysis work when the shifts are approximate minimizers for the cost function? 2. Extreme timescale setting: the analysis in the paper only considers two extreme timescale settings: (i) the algorithm responds much faster than the population, and (ii) the population responds much faster than the algorithm. This is somewhat strict and doesn’t allow for intermediate changes in the algorithm\distribution. 3. Assumptions: the paper has many assumptions, some of which are less common. The authors should give some motivation and justification for their assumptions, and provide examples where all of these assumptions hold. 4. The experiments are a little simple (1-dimensional classifiers) and it would be more interesting to see an example which is more relevant in practice. This is perhaps one of the limitations of this framework: even though it is able to capture more complex structures of shifts, it is harder to simulate for more sophisticated examples and models (e.g. high dimensional classifiers, other timescale settings, and so on). The authors should therefore also discuss the limitation of their framework compared to existing ones. 5. Experimental discussion: the experimental section jumps too fast to the experiments without explaining the objectives of these experiments or discussing its connections to the previous theoretical results. The authors should explain their main objectives in this setting, discuss connection to the theory in the previous section, and also compare to existing prior work (e.g. show how the example in section 4.1 cannot be captured by prior frameworks).

Questions

See above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above.

Response

Thanks for the detailed response; I'm still recommending to accept the paper.

Re. author response

Thanks to the authors for their response. I do not have any other questions, and will retain my score as is.