Abstract
As data-driven methods are deployed in real-world settings, the processes that generate the observed data will often react to the decisions of the learner. For example, a data source may have some incentive for the algorithm to provide a particular label (e.g. approve a bank loan), and manipulate their features accordingly. Work in strategic classification and decision-dependent distributions seeks to characterize the closed-loop behavior of deploying learning algorithms by explicitly considering the effect of the classifier on the underlying data distribution. More recently, works in performative prediction seek to classify the closed-loop behavior by considering general properties of the mapping from classifier to data distribution, rather than an explicit form. Building on this notion, we analyze repeated risk minimization as the perturbed trajectories of the gradient flows of performative risk minimization. We consider the case where there may be multiple local minimizers of performative risk, motivated by situations where the initial conditions may have significant impact on the long-term behavior of the system. We provide sufficient conditions to characterize the region of attraction for the various equilibria in this settings. Additionally, we introduce the notion of performative alignment, which provides a geometric condition on the convergence of repeated risk minimization to performative risk minimizers.
Introduction
In classical machine learning, we typically assume that data is drawn from a fixed, static distribution. However, in many real-world applications—such as credit scoring, insurance, or social media recommendation—the deployment of a model changes the behavior of the agents it interacts with, thereby shifting the underlying data distribution. This phenomenon, known as performative prediction, creates a feedback loop that can lead to complex dynamical behavior.
While previous research has often focused on finding a single, global "performatively stable" point, many practical systems are non-convex and exhibit multiple local equilibria. In such cases, the initial state of the model (initialization) determines which equilibrium the system will eventually settle into. This paper, presented at AISTATS 2023, provides a theoretical framework to map these "Regions of Attraction" and introduces conditions for stable convergence.
Methodology: Learning as a Dynamical System
The authors analyze the learning process through the lens of Control Theory and Dynamical Systems. By modeling discrete learning updates as continuous gradient flows, they can treat standard algorithms like Repeated Risk Minimization (RRM) or Repeated Gradient Descent (RGD) as perturbed versions of an ideal Performative Risk Minimization (PRM) flow.
Key components of their analysis include:
- Perturbation Analysis: Quantifying the gap between the ideal path of minimizing total performative risk and the actual path taken by retraining on new data.
- Lyapunov Functions: Mathematical tools used to prove that once a model enters a specific region around an equilibrium (the Region of Attraction), it is guaranteed to stay there and converge toward it.
- Performative Alignment: A novel geometric condition. It suggests that if the "push" from the distribution shift aligns sufficiently with the "pull" of the risk gradient, the model will remain stable even in complex, non-convex landscapes.
Synthetic Validation
To validate their theoretical findings, the authors employed two synthetic environments that capture the essence of performative feedback loops.
Bernoulli Distribution Model
This model represents "echo chambers," where a model's decision influences a binary outcome. The non-convexity of the resulting performative risk leads to multiple stable points, illustrating how initialization acts as a self-fulfilling prophecy.
Adversarial Agents Model
In this simulation, agents actively manipulate their features to trick a linear classifier. This creates a complex feedback loop between the classifier's parameters and agent behavior, resulting in multiple local minima in the performative risk surface.
Key Results and Insights
- Characterizing the Region of Attraction: The paper provides a concrete formula (Theorem 1) for the radius within which a model is guaranteed to converge exponentially fast to a local performative minimizer.
- RGD as an Inexact Method: The authors highlight that repeated risk minimization is fundamentally "inexact" because it ignores the derivative of the distribution shift. Despite this, they show that stability is achievable if the distribution shift isn't too sensitive.
- Alignment over Curvature: While traditional stability analysis relies on strong convexity (curvature), this work demonstrates that Performative Alignment (the direction of gradients) is often a more critical factor for stability in performative settings.
Conclusion and Future Work
This work provides a rigorous foundation for understanding the long-term behavior of learning algorithms in reactive environments. However, applying these results in practice remains challenging because the exact mapping of the distribution shift is often a "black box." Future research is needed to estimate these regions of attraction with limited information and to extend the continuous-time analysis to handle the high-variance noise inherent in discrete stochastic updates.
Summary updated