Performative Stability in Nearly the Minimum Number of Deployments

Paper: 2609.14065 Authors: Gabriele Farina, Juan Carlos Perdomo Categories: cs.LG, cs.GT

The Gap

When algorithmic predictions inform people’s decisions, the models we deploy are performative and actively shape the data we see. A model predicting which applicants will default changes who is approved, which changes who defaults — so the distribution the model is trained on is partly a consequence of the model.

That creates a question about the target itself: if different predictive models induce different distributions, is it possible to efficiently learn a prediction rule that is optimal for the distribution that it induces? The solution concept is performative stability — a predictor that is optimal for its own induced distribution rather than for a distribution that existed before it.

And the learning problem is unlike supervised learning in a structural way: the learner must deploy different predictors and observe their induced distributions. In supervised learning the distribution is fixed and data can be collected without consequence. Here every observation requires deploying a model into the world, so the number of deployments is the scarce resource — and it is the resource any algorithm must minimise.

   PREDICTIONS THAT SHAPE THE DATA THEY PREDICT

   when algorithmic predictions INFORM PEOPLE'S DECISIONS,
   THE MODELS WE DEPLOY ARE PERFORMATIVE AND ACTIVELY SHAPE THE DATA
   WE SEE
     -> a model predicting which applicants will default changes WHO IS
        APPROVED, which changes WHO DEFAULTS
     -> the distribution the model is trained on is PARTLY A CONSEQUENCE
        OF THE MODEL
        |
        v
   [A QUESTION ABOUT THE TARGET ITSELF]
     IF DIFFERENT PREDICTIVE MODELS INDUCE DIFFERENT DISTRIBUTIONS,
     is it possible to EFFICIENTLY LEARN a prediction rule that is
     OPTIMAL FOR THE DISTRIBUTION THAT IT INDUCES?
       -> the solution concept is PERFORMATIVE STABILITY:
          a predictor OPTIMAL FOR ITS OWN INDUCED DISTRIBUTION rather
          than for a distribution that EXISTED BEFORE IT

   [AND THE LEARNING PROBLEM IS STRUCTURALLY UNLIKE SUPERVISED LEARNING]
     THE LEARNER MUST DEPLOY DIFFERENT PREDICTORS AND OBSERVE THEIR
     INDUCED DISTRIBUTIONS
       <- in supervised learning the distribution is FIXED and data can
          be collected WITHOUT CONSEQUENCE
       <- here EVERY OBSERVATION REQUIRES DEPLOYING A MODEL INTO THE
          WORLD
       -> so the NUMBER OF DEPLOYMENTS is THE SCARCE RESOURCE
       -> and it is the resource ANY ALGORITHM MUST MINIMISE

The Increment

One sentence: Before this paper, finding a performatively stable predictor required many deployments or assumptions about how predictions shape distributions; after it, a procedure reaches stability in nearly the minimum number of deployments with no such assumptions.

Core Mechanism

The main result is an algorithmic procedure that, in the high-accuracy regime, finds a performatively stable model in nearly the minimum number of model deployments without making any assumptions regarding how predictions shape distributions.

Three parts of that sentence are each load-bearing, and the third is the strongest.

“Nearly the minimum number of model deployments” is the right optimality target, because deployments are the scarce resource. Not sample complexity in the abstract — deployments specifically — which is what makes the result about the actual cost of learning in this setting.

“Without making any assumptions regarding how predictions shape distributions” is what separates this from earlier work. Prior approaches achieved stability under conditions on the performative effect — for instance that it is small or well-behaved. Assuming the feedback loop is mild is assuming away part of the problem, since the interesting cases are where it is not.

And the improvement is exponential: the procedure succeeds at finding a randomized performatively stable predictor using exponentially fewer model deployments than prior approaches. The qualifier randomized is substantive rather than incidental — it is the relaxation that makes the efficiency possible, and it sets up the second contribution.

That second contribution is a derandomization result, and its structure is the frankest part of the paper: it shows how this randomized notion of stability can be derandomized into a single predictor satisfying the prior deterministic notion if one is willing to assume that the loss is well-conditioned and that performative effects are weak, as in early work in this area. Read as a trade-off statement, this is precise about what was gained and what it cost. The efficient procedure is randomized; converting it to a single deterministic predictor requires bringing back the assumptions that the main result avoided. The paper does not claim the derandomization is free — it states the price, which is the honest form for a result of this shape.

And the technical source is named: the results come from building on an underexplored technical connection between performative stability and expected variational inequalities. Naming the connection is useful in itself, since it suggests the machinery may transfer to other performative problems — the connection was available and unexploited.

   THE MAIN RESULT
     an ALGORITHMIC PROCEDURE that, IN THE HIGH-ACCURACY REGIME,
     finds a PERFORMATIVELY STABLE MODEL
     IN NEARLY THE MINIMUM NUMBER OF MODEL DEPLOYMENTS
     WITHOUT MAKING ANY ASSUMPTIONS REGARDING HOW PREDICTIONS SHAPE
     DISTRIBUTIONS

   THREE PARTS, EACH LOAD-BEARING, THE THIRD STRONGEST

     [1] "NEARLY THE MINIMUM NUMBER OF MODEL DEPLOYMENTS"
           <- the RIGHT OPTIMALITY TARGET, because DEPLOYMENTS ARE THE
              SCARCE RESOURCE
           <- NOT sample complexity in the abstract -- DEPLOYMENTS
              SPECIFICALLY
           -> which makes the result about THE ACTUAL COST OF LEARNING
              IN THIS SETTING

     [2] "WITHOUT MAKING ANY ASSUMPTIONS REGARDING HOW PREDICTIONS SHAPE
         DISTRIBUTIONS"
           <- this SEPARATES IT FROM EARLIER WORK: prior approaches
              achieved stability UNDER CONDITIONS ON THE PERFORMATIVE
              EFFECT (that it is SMALL or WELL-BEHAVED)
           <- assuming the FEEDBACK LOOP IS MILD is ASSUMING AWAY PART
              OF THE PROBLEM
           -> since THE INTERESTING CASES ARE WHERE IT IS NOT

     [3] AND THE IMPROVEMENT IS EXPONENTIAL
           the procedure finds a RANDOMIZED performatively stable
           predictor using EXPONENTIALLY FEWER model deployments than
           prior approaches
           <- the qualifier "RANDOMIZED" is SUBSTANTIVE rather than
              incidental: it is the RELAXATION that makes the EFFICIENCY
              POSSIBLE
           -> and it SETS UP THE SECOND CONTRIBUTION

   [THE SECOND CONTRIBUTION: DERANDOMIZATION, AND ITS PRICE IS STATED]
     it shows how this RANDOMIZED notion of stability can be
     DERANDOMIZED INTO A SINGLE PREDICTOR satisfying the PRIOR
     DETERMINISTIC NOTION
     IF one is willing to assume that
       THE LOSS IS WELL-CONDITIONED
       PERFORMATIVE EFFECTS ARE WEAK, as in EARLY WORK IN THIS AREA
       <- read as a TRADE-OFF STATEMENT, this is PRECISE about WHAT WAS
          GAINED AND WHAT IT COST
       <- the EFFICIENT procedure is RANDOMIZED; converting it to a
          SINGLE DETERMINISTIC predictor REQUIRES BRINGING BACK THE
          ASSUMPTIONS THE MAIN RESULT AVOIDED
       <- the paper does NOT claim the derandomization is FREE -- it
          STATES THE PRICE, the honest form for a result of this shape

   [AND THE TECHNICAL SOURCE IS NAMED]
     the results come from building on an UNDEREXPLORED TECHNICAL
     CONNECTION BETWEEN PERFORMATIVE STABILITY AND EXPECTED VARIATIONAL
     INEQUALITIES
       <- naming the connection is useful IN ITSELF: it suggests the
          machinery MAY TRANSFER to OTHER PERFORMATIVE PROBLEMS
       <- the connection was AVAILABLE and UNEXPLOITED

Think of it as learning where to set a subsidy when the setting changes behaviour. You want a level that is right for the economy your level creates — and every trial means actually setting the subsidy and living with the consequences, which is why the number of trials is the cost that matters. Two properties of the procedure are what you would want. It does not require you to assume in advance that people barely respond to the subsidy, because assuming a mild response is assuming away the case you are worried about. And when you eventually want one fixed number rather than a randomised policy, the conversion is available — but only if you accept assumptions that the efficient version did not need, which the paper states rather than glosses.

Key Concepts

• Performativity and induced distributions: the deployed model shapes the data, so the target is optimality for its own induced distribution. It is what makes the learning problem structurally different from supervised learning.
• Deployments as the scarce resource: every observation requires putting a model into the world. It is why “nearly the minimum number of deployments” is the right optimality target.
• Assumption-free stability: no conditions on how predictions shape distributions. Assuming a mild performative effect would exclude the cases the problem is about.
• Randomization as the enabling relaxation: the exponential improvement is for a randomized notion of stability, which is what makes the efficiency attainable.
• Derandomization with a stated price: recovering a single deterministic predictor requires well-conditioned loss and weak performative effects. Naming the cost rather than presenting derandomization as free is what keeps the trade-off legible.
• The connection to expected variational inequalities: the technical route, previously unexploited, which may transfer to other performative problems.

Framework Shift

Before (stability under assumptions, or many deployments):
  learn a predictor optimal for its induced distribution
  -> prior approaches assumed performative effects weak or small
  -> or required many model deployments
  -> the interesting regime, strong feedback, was assumed away

After (assumption-free, nearly minimal deployments):
  a procedure finds a randomized performatively stable predictor
  -> exponentially fewer deployments than prior approaches
  -> no assumptions about how predictions shape distributions
  -> derandomizing to a single predictor costs well-conditionedness
     and weak performative effects

From assuming the feedback loop is mild so that stability becomes tractable, to reaching stability without such assumptions in nearly the minimum number of deployments, the core shift is that the efficiency of learning can come from relaxing the solution concept rather than from restricting the problem.

Expert Assessment

Problem choice: Excellent, and the framing of the cost is the contribution: recognising that deployments, not samples, are the scarce resource turns the question into one with a well-defined optimality target. And refusing to assume mild performative effects keeps the problem in the regime that motivates it.

Method maturity: The main result is strong on the three axes that matter — the optimality target is the right one, the assumption set is empty, and the improvement is exponential. The derandomization contribution is well handled: presenting it as requiring the assumptions the main result avoided, with the specific conditions named, is the honest form for a trade-off. Naming the technical connection to expected variational inequalities is a contribution in itself, since it points the machinery at other performative problems.

Experimental integrity: This is a theory contribution, so the reading is of the high-accuracy regime and the solution concept. The regime qualifier is real — the result holds asymptotically, and behaviour in the low-accuracy regime is not addressed — and the randomized solution concept is a genuine relaxation, meaning a practitioner wanting a single deployed model is in the derandomization case with its assumptions. The paper states both boundaries, which keeps the result’s scope clear rather than overclaiming applicability.

Writing quality: The abstract separates the assumption-free randomized result from the conditional derandomization, which is exactly the structure a reader needs to see what applies to their situation. Because the practical question is how many deployments “nearly the minimum” means, a worked instance with the deployment count compared against a prior method would make the exponential claim concrete.

Verdict: strong accept — it reaches performative stability without assumptions about the feedback loop in nearly the minimum number of deployments, states the price of derandomization rather than hiding it, and opens a technical connection likely to transfer.

Takeaways

• Count the right resource. When every observation requires deploying a model into the world, deployments rather than samples are the cost to minimise.
• Check whether an assumption removes the interesting case. Assuming performative effects are mild excludes exactly the feedback loops that motivated the problem.
• Ask what a relaxation costs. An efficient result for a randomized solution concept may require assumptions to convert into a single deployable model.
• Note an unexploited technical connection. Identifying one is a contribution, because the machinery may transfer to other problems in the same class.