The Reflexivity Threshold: A Phase Transition for Multi-Agent Performative Prediction

AI summary

Overview

Research area: Machine learning theory — specifically performative prediction, multi-agent learning dynamics, and spectral analysis of networked learners (arXiv:2610.29577v1 [cs.LG], 21 Oct 2026).

Technical level: Advanced. The paper is a pure theory contribution requiring comfort with Perron–Frobenius theory, fixed-point/contraction arguments, and information-theoretic lower bounds (KL divergence, Pinsker's inequality, the two-point method). There are no datasets, benchmarks, or empirical tables.

Scope: The paper establishes upper and lower bounds showing that a single spectral quantity — the spectral radius of a "reflexivity matrix" built from per-agent gradient sensitivities and curvature constants — sharply separates stable multi-agent retraining from unavoidable learning failure.

What This Paper Is About

When a learning system is deployed, its predictions can change the data distribution that future models are trained on — this is performative prediction. In real systems, many learners interact: one agent's deployment shifts the environment, which shifts another agent's retraining problem, and so on through a network of feedback. The paper asks whether there is a general threshold that tells you when repeated retraining across such a network will settle to a stable equilibrium, and when it is doomed to fail no matter what decentralized algorithm the agents use. The authors answer with a matrix that records "who affects whom, and how strongly," and prove a phase transition at spectral radius one.

Key Contributions

1. The reflexivity matrix Γ. They define a k×k nonnegative matrix with entries Γ_ij := a_ij / μ_i, where a_ij is how strongly agent j's deployment perturbs agent i's gradient and μ_i is agent i's strong-convexity (curvature) constant. This replaces the scalar contraction constant used in prior multi-agent work with a structure that preserves pairwise feedback routing.

2. An entrywise best-response sensitivity bound (Theorem 2). They prove ||B_i(w) − B_i(w')|| ≤ Σ_j (a_ij/μ_i) ||w_j − w'_j||, which reduces nonlinear retraining dynamics with general strongly convex losses to a linear comparison through Γ, making Perron–Frobenius theory applicable.

3. The subcritical side (Theorem 4, Corollaries 5 and 6). If ρ(Γ) < 1, retraining is a contraction in a Perron–Frobenius weighted norm ||·||_q, yielding a unique performatively stable equilibrium, geometric convergence from any initialization, and cumulative dynamic excess loss bounded uniformly in the time horizon.

4. The supercritical side (Theorem 8). For a rank-one family with ρ(Γ) = 1 + ε, they construct instances where every decentralized local-information learner incurs expected cumulative excess loss that grows linearly, Ω(Δ²T), over horizons T = O(1/ε). Together, the two sides identify ρ(Γ) = 1 as a sharp boundary, and the single-agent scalar threshold is recovered as the special case k = 1.

Main Findings

• The threshold sits at spectral radius one. Γ measures the largest asymptotic amplification factor of the feedback network. Below ρ(Γ) < 1, cross-agent feedback dissipates and learning is stable; above it, the positive guarantee provably cannot be extended.

• Subcritical regime: geometric convergence to a unique equilibrium. For any α in (ρ(Γ), 1) one can choose positive weights q with Γq ≤ αq, so the contraction factor can be made arbitrarily close to ρ(Γ). Iterates satisfy ||w_t − w*||_q ≤ α^t ||w_0 − w*||_q for every t ≥ 0, from any initialization, with iteration complexity O(log(||w_0 − w*||_q/δ) / (−log α)) to accuracy δ.

• Subcritical regime: cumulative excess loss is O(1), not O(T). Under an added smoothness assumption (L_i-smoothness in each agent's own action), the bound is Reg~_T ≤ [C/(1−α²)] ||w_0 − w*||_q² for every T ≥ 1, where C depends only on Γ, q, and {L_i}. The bound depends on initialization and contraction factor but not on the horizon.

• Supercritical regime: linear loss for every decentralized learner. In the hard family, agents use quadratic loss, d_i = 1, μ_i = 1, and Γ_ε := (1+ε) v vᵀ with unit nonnegative v, so ρ(Γ_ε) = 1 + ε. With noise variance σ_ε² := 8Δ²/ε and observations Y_t = νΔv + Γ_ε w_t + ξ_t (hidden binary parameter ν), the two equilibria sit at ∓(Δ/ε)v, a separation of 2Δ/ε.

• The lower bound is information-theoretic, not algorithmic. Theorem 8 states that for absolute constants c_0, c_1 > 0, every decentralized local-information learner A satisfies ½E_+[Reg_T^+] + ½E_−[Reg_T^−] ≥ c_1 Δ² T for every T ≤ c_0/ε, and hence sup_ν E_ν[Reg_T^ν] ≥ c_1 Δ² T. No agent observes the full system state; the lower bound holds regardless of the algorithm used within each agent.

• The key technical mechanism is an exact cancellation. The per-round KL divergence between the two environments is ε/4 (using ||v|| = 1 and σ_ε² = 8Δ²/ε), so the environments stay statistically indistinguishable over the critical horizon and the optimal equal-prior testing error is bounded below by an absolute constant p_0 > 0. The factor ε from the contraction of (I − Γ_ε) along v cancels exactly against the factor 1/ε from the equilibrium separation — which is why the obstruction survives as ε → 0.

• The matrix condition strictly improves on scalar aggregates. In the comparison with Narang et al. (2023) — scalar agents, quadratic loss, deterministic observations z = Cw — their condition is ||C||_F < 1 while the paper's is ρ(C) < 1, and ρ(C) ≤ ||C||_F always. For C = cP with P a cyclic permutation matrix, ρ(C) = c but ||C||_F = c√k, so for k^{-1/2} < c < 1 the matrix condition certifies convergence and the scalar aggregate condition does not.

• Illustrative simulation. Figure 1 plots the number of retraining steps to reach ||w_t − w*||_q ≤ δ, showing convergence slowing sharply as ρ(Γ) approaches 1 from below; only subcritical values are plotted, with a computational cap of 10,000 iterations and a displayed vertical range up to 1,000. A second panel shows normalized distance to equilibrium on a log scale: subcritical instances contract geometrically, plotted supercritical instances move away, and a non-normal subcritical curve shows transient growth before contraction.

• What is not reported. The paper reports no dataset sizes, no standard benchmark tasks, and no empirical comparisons to competing methods; the work is analytical, with the figure serving as illustration. Setup details are deferred to Appendix B, and the lower-bound proof to Appendix A; the supplied text is truncated before those appendices and before the paper's conclusion.

Methodology in Plain English

The authors start from two assumptions about each agent: its objective is strongly convex in its own action (curvature μ_i, meaning resistance to perturbation), and its gradient shifts by at most a weighted sum of everyone's deployment changes (sensitivities a_ij). A third assumption makes the feasible sets all of ℝ^{d_i} so that standard fixed-point theory applies.

The core move is a three-line argument: at an optimum the gradient is zero; strong convexity converts a difference in best responses into a difference in gradients; gradient sensitivity converts that back into a weighted sum of deployment changes. Dividing by μ_i yields a linear, entrywise bound — the matrix Γ. All the nonlinearity and all the agent coupling is now captured by a nonnegative matrix.

From there, standard spectral theory does the work. When the largest eigenvalue of Γ is below one, there exist positive weights that make the whole system a contraction, so a unique equilibrium exists and iterates converge geometrically — and a smoothness argument turns that geometric decay into a cumulative loss that stops growing.

For the negative side, the authors cannot just say "contraction fails." A learner with enough data might still recover the right equilibrium, so they must prove no algorithm can succeed. They build a deliberately simple world where amplification comes from one direction only: a rank-one Γ with spectral radius 1 + ε, a hidden two-valued state of the world, Gaussian observations with variance scaled as 8Δ²/ε, and two equilibria pushed far apart (distance 2Δ/ε). The noise is scaled so that the two worlds look statistically identical over the relevant horizon (per-round KL of ε/4), while being wrong about the world costs Δ²/2 per round. Averaging over the two worlds with a testing lower bound delivers the linear-in-T loss.

Why This Matters

Impact on research. Prior multi-agent performative prediction theory collapses cross-agent feedback into a scalar contraction constant, which discards the network's routing structure. This paper shows that the scalar view is genuinely lossy: there are systems the matrix certificate proves stable that the scalar aggregate condition cannot certify, with an explicit cyclic-permutation example and the k^{-1/2} < c < 1 range. It also pairs the upper bound with a matching worst-case lower bound, a combination the authors argue is absent from the closest prior strands (scalar contraction conditions, spectral conditions specific to linear-quadratic multiplex models, and dynamical-chaos transitions). It further distinguishes itself from Farina and Perdomo (2026), whose no-regret result gives approximate stability of a mixture over joint deployment histories without regularity assumptions, whereas this paper gives geometric convergence of the last iterate to a unique equilibrium under curvature and sensitivity assumptions.

Real-world applications (the paper itself names the first two):

• Credit scoring: a deployed scoring model changes how applicants behave, shifting the distribution the next model is trained on.
• Algorithmic trading: a strategy can move the price data on which future strategies are trained.
• Platforms with competing recommenders or pricing algorithms, where each deployed model perturbs the data other models learn from — the reflexivity matrix is a diagnostic for whether the fleet will settle or oscillate.
• Federated or multi-operator learning deployments, where the practical question is whether independently retraining parties converge without central coordination.

Industry relevance. The threshold is a design target, not just an analysis result. Teams can estimate sensitivities and curvatures, assemble Γ, and check a single number before deploying a retraining pipeline — and the k^{-1/2} < c < 1 example suggests the check can green-light systems a cruder aggregate test would reject. The supercritical result also says something sobering for engineering practice: above the threshold, no amount of cleverness in the local retraining rule fixes the problem, so the intervention must be structural (reduce coupling, raise curvature) rather than algorithmic.

Future Directions

• Relaxing the unconstrained-domain assumption. Assumption 3 (𝒲_i = ℝ^{d_i}) is what enables Banach's theorem. Extending the threshold analysis to constrained, compact, or nonconvex feasible sets is a natural open problem the setup invites.

• Tightening the supercritical construction. The lower bound is proved for a rank-one family with a specific noise scaling (σ_ε² = 8Δ²/ε) and horizon T = O(1/ε). Whether linear loss persists for general Γ above the threshold, and how the constants c_0, c_1 depend on problem geometry, is left open by the paper as supplied.

• Beyond worst case. The lower bound concerns the worst-case learner. Characterizing which specific algorithms (or which additional observation structure, such as partial communication between agents) escape the obstruction above ρ(Γ) = 1 would turn the impossibility into a design guide.

• Bridging to the no-regret view. Reconciling geometric last-iterate convergence below the threshold with the mixture-based approximate stability of Farina and Perdomo (2026) — and determining which guarantee is achievable in which regime — is a clear next step that the related-work discussion sets up but does not resolve.

Target Audience

Researchers in machine learning theory and algorithmic game theory working on performative prediction, decision-dependent distributions, or learning in games; PhD students and advanced graduate students comfortable with spectral graph theory and minimax lower bounds; and theoretically minded practitioners in credit, trading, or platform ML who need a principled, cheap-to-compute stability criterion before committing to a multi-model retraining pipeline. Readers seeking empirical benchmarks or off-the-shelf algorithms will not find them here — the contribution is a boundary theorem, not a method.

Authors’ abstract

Many learning systems are performative: once deployed, their predictions change the data distribution on which future models are trained. In multi-agent settings, this feedback is routed through a network of interacting learners, so stability depends not only on the strength of performativity but also on who affects whom. We study repeated retraining in multi-agent performative prediction and identify a spectral threshold that separates stable learning from worst-case learning obstruction. Prior work often collapses cross-agent feedback into a scalar contraction constant, missing this network structure. We instead introduce the reflexivity matrix $Γ$, which records how strongly one agent's deployment can move another agent's best response, defined from per-agent gradient sensitivities and curvature parameters. The threshold occurs when the spectral radius of this matrix crosses one. Below the threshold, repeated retraining converges geometrically to a unique performatively stable equilibrium, with cumulative excess loss bounded uniformly in the time horizon. Above the threshold, we construct noisy supercritical instances in which every local-information learner incurs expected cumulative excess loss growing linearly for horizons up to order $1/(ρ(Γ)-1)$. Together, these results characterize the threshold behavior through upper and lower bounds and recover the single-agent scalar threshold from prior work as a special case.