Editor:
Introduction
Conformal prediction provides distribution-free coverage guarantees: given exchangeable calibration data, one can construct prediction sets C ( x ) ⊆ Y C(x) \subseteq\mathcal{Y} C ( x ) ⊆ Y P ( Y ∈ C ( X ) ) ≥ 1 − α \mathbb{P}(Y \in C(X)) \ge1-\alpha P ( Y ∈ C ( X )) ≥ 1 − α [36 , 31 , 19 , 1 ] ). This guarantee requires no assumptions on the data-generating distribution beyond exchangeability; informally, the test point must come from the same data-generating process as the calibration data ([35 , 18 ] ).
In many applications, this assumption fails because deployment changes behavior and hence the data distribution. A lending rule affects who receives credit and thus the future distribution of defaults on which the rule is later retrained; a recidivism predictor affects sentencing and thus the future distribution of reoffending; a treatment-allocation rule affects who receives care and thus the future distribution of health outcomes. In such settings, the distribution is endogenous : it depends on the deployed predictor. The performative prediction framework (Perdomo et al. [27 ] ; Mendler-Dünner et al. [22 ] ; Miller et al. [24 ] ; Izzo et al. [13 ] ; Brown et al. [4 ] ; Jagadeesan et al. [14 ] ; Hardt et al. [11 ] ) formalizes this through a map D : F → Δ ( X × Y ) D:\mathcal{F}\to\Delta(\mathcal{X}\times\mathcal{Y}) D : F → Δ ( X × Y ) f f f D ( f ) D(f) D ( f ) D ( f ) D(f) D ( f )
If f ⋆ f^\star f ⋆
P ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ⋆ ( X ) ) ≥ 1 − α . (1) \mathbb{P}_{(X,Y)\sim D(f^\star)}\left(Y\in C_{f^\star}(X)\right)\ge1-\alpha. \tag*{(1)} P ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ⋆ ( X ) ) ≥ 1 − α . (1) We call this equilibrium-valid coverage . Equilibrium is the relevant operating point because deployed systems are retrained until they stabilize, and coverage is needed at that stable distribution. This viewpoint aligns with prior work on retraining dynamics, optimization to stable points, performative risk minimization, and state-dependent feedback (Perdomo et al. [27 ] ; Mendler-Dünner et al. [22 ] ; Miller et al. [24 ] ; Izzo et al. [13 ] ; Brown et al. [4 ] ; Jagadeesan et al. [14 ] ).
Research question. In performative environments, what coverage guarantees can conformal prediction provide at performative equilibrium? Under what conditions on the feedback map are such guarantees achievable, and what finite-sample complexity do they require?
Contributions. We answer these questions in five steps: we identify a feasibility threshold, establish minimax lower and upper bounds, prove a transfer theorem that converts convergence to equilibrium into coverage at equilibrium, apply the theory with simple retraining-based algorithms, and validate the predicted theory empirically.
Impossibility (phase transition at L ≥ 1 L\ge1 L ≥ 1 If L ≥ 1 L\ge1 L ≥ 1 nontrivial equilibrium-valid coverage over all L L L 1 − α 1-\alpha 1 − α
Minimax rate (Theorem 3.2). When L < 1 L<1 L < 1 τ \tau τ C ( x ) = Y C(x)=\mathcal{Y} C ( x ) = Y n n n Ω ~ ( 1 / ( ( 1 − L ) n ) ) \tilde{\Omega}(1/((1-L)\sqrt{n})) Ω ~ ( 1/ (( 1 − L ) n )) β \beta β γ \gamma γ ρ = L β / γ < 1 \rho=L\beta/\gamma<1 ρ = L β / γ < 1 O ~ ( 1 / ( ( 1 − ρ ) n ) ) \tilde{O}(1/((1-\rho)\sqrt{n})) O ~ ( 1/ (( 1 − ρ ) n )) β / γ = O ( 1 ) \beta/\gamma=O(1) β / γ = O ( 1 ) O ~ ( 1 / ( ( 1 − L ) 3 / 2 n ) ) \tilde{O}(1/((1-L)^{3/2}\sqrt{n})) O ~ ( 1/ (( 1 − L ) 3/2 n )) L < 1 L<1 L < 1
Coverage transfer theorem (Theorem 2.8). If a learning or retraining procedure returns a predictor within ε \varepsilon ε L L L L ε L\varepsilon L ε
4. Achievability via simple retraining (Theorems 4.1 –4.4 ). Combining Theorem 2.8 with standard retraining yields equilibrium-valid coverage when L < 1 L < 1 L < 1 O ~ ( 1 / ( ( 1 − L ) 3 / 2 n ) ) \widetilde{O}(1/((1-L)^{3/2}\sqrt{n})) O ( 1/ (( 1 − L ) 3/2 n )) L < 1 L < 1 L < 1 n n n L L L β / γ = O ( 1 ) \beta/\gamma= O(1) β / γ = O ( 1 )
The price of performativity. The factor 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 price of performativity . It quantifies how endogenous distribution shift inflates the data required to achieve a fixed excess miscoverage level. Relative to the non-performative setting, the required sample size grows by a factor of order 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 L = 0.5 L = 0.5 L = 0.5 4 × 4\times 4 × L = 0.9 L = 0.9 L = 0.9 100 × 100\times 100 × L → 1 L \to1 L → 1 L ≥ 1 L \ge1 L ≥ 1
Paper outline. Section 2 formalizes equilibrium-valid coverage, the L L L L ≥ 1 L \ge1 L ≥ 1 L < 1 L < 1 L < 1 L ϵ L\epsilon L ϵ L = 1 L = 1 L = 1
Framework and the Transfer Principle
We first recall the performative prediction framework and then introduce the objects used in our analysis.
Performative Prediction
Let X \mathcal{X} X Y \mathcal{Y} Y F \mathcal{F} F f : X → Y f:\mathcal{X}\to\mathcal{Y} f : X → Y [27 ] , a distribution map D : F → Δ ( X × Y ) D:\mathcal{F}\to\Delta(\mathcal{X}\times\mathcal{Y}) D : F → Δ ( X × Y ) f f f D ( f ) D(f) D ( f ) ( X , Y ) (X,Y) ( X , Y ) D f D_f D f
Definition 2.1 (Performative stability [27 ] ). A predictor f ⋆ ∈ F f^\star\in\mathcal{F} f ⋆ ∈ F
f ⋆ ∈ arg min f ∈ F E ( X , Y ) ∼ D ( f ) [ ℓ ( f ( X ) , Y ) ] . f^\star\in\underset{f\in\mathcal{F}}{\arg\min}\ \mathbb{E}_{(X,Y)\sim D(f)}[\ell(f(X),Y)]. f ⋆ ∈ f ∈ F arg min E ( X , Y ) ∼ D ( f ) [ ℓ ( f ( X ) , Y )] . The key parameter in our analysis is L L L
Definition 2.2 (L L L D ( ⋅ ) D(\cdot) D ( ⋅ ) L L L f , g ∈ F f,g \in\mathcal{F} f , g ∈ F
TV ( D ( f ) , D ( g ) ) ≤ L ⋅ d F ( f , g ) . \operatorname{TV}(D(f),D(g)) \le L\cdot d_{\mathcal{F}}(f,g). TV ( D ( f ) , D ( g )) ≤ L ⋅ d F ( f , g ) . where TV \operatorname{TV} TV d F d_{\mathcal{F}} d F F \mathcal{F} F
TV-sensitivity is the right assumption for our transfer result because total variation satisfies TV ( P , Q ) = sup A ∣ P ( A ) − Q ( A ) ∣ \operatorname{TV}(P,Q)=\sup_A\lvert P(A)-Q(A)\rvert TV ( P , Q ) = sup A ∣ P ( A ) − Q ( A )∣ A = { ( x , y ) : s ( x , y ; f ) ≤ q } A=\{(x,y):s(x,y;f)\le q\} A = {( x , y ) : s ( x , y ; f ) ≤ q } D ( f ^ ) D(\hat{f}) D ( f ^ ) D ( f ∗ ) D(f^*) D ( f ∗ )
Standing assumptions. Throughout this section and § 4 , we assume the distribution map D ( ⋅ ) D(\cdot) D ( ⋅ ) L L L f ∗ f^* f ∗ s s s
Equilibrium-Valid Coverage
A nonconformity score s : X × Y × F → R s:\mathcal{X}\times\mathcal{Y}\times\mathcal{F}\to\mathbb{R} s : X × Y × F → R ( x , y ) (x,y) ( x , y ) f f f q q q C f ( x ) = { y ∈ Y : s ( x , y ; f ) ≤ q } C_f(x)=\{y\in\mathcal{Y}:s(x,y;f)\le q\} C f ( x ) = { y ∈ Y : s ( x , y ; f ) ≤ q } s s s
The guarantee in (1) requires validity under the equilibrium distribution D ( f ∗ ) D(f^*) D ( f ∗ )
Definition 2.3 (Nontrivial Prediction Set). A prediction set mapping C : X → 2 Y C:\mathcal{X}\to2^{\mathcal{Y}} C : X → 2 Y C ( x ) ≠ Y C(x)\ne\mathcal{Y} C ( x ) = Y x ∈ X x\in\mathcal{X} x ∈ X
Definition 2.4 (Excess Miscoverage). Given a target miscoverage level α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) prediction set C f C_f C f P P P
ExMisc ( C f , P ) = max { 0 , P P ( Y ∉ C f ( X ) ) − α } . \operatorname{ExMisc}(C_f,P)=\max\{0,\mathbb{P}_P(Y\notin C_f(X))-\alpha\}. ExMisc ( C f , P ) = max { 0 , P P ( Y ∈ / C f ( X )) − α } . Definition 2.5 (Marginal Excess Miscoverage). For a calibration-dependent procedure producing C S C_S C S S S S P P P
ExMisc ‾ ( C , P ) = max { 0 , E S [ P P ( Y ∉ C S ( X ) ) ] − α } . \overline{\operatorname{ExMisc}}(C,P)=\max\left\{0,\mathbb{E}_S[\mathbb{P}_P(Y\notin C_S(X))]-\alpha\right\}. ExMisc ( C , P ) = max { 0 , E S [ P P ( Y ∈ / C S ( X ))] − α } . The nontriviality condition excludes the vacuous solution C ( x ) = Y C(x)=\mathcal{Y} C ( x ) = Y Y \mathcal{Y} Y Theorem 3.1 ), and that result continues to hold under any stronger informativeness criterion. For the minimax rate (Theorem 3.2 ), however, a purely qualitative condition is too weak: on a non-singleton X \mathcal{X} X Y \mathcal{Y} Y
Definition 2.6 (τ \tau τ τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] prediction-set procedure producing C S C_S C S from a calibration sample S S S τ \tau τ P P P
Inf ( C , P ) : = E S [ P X ∼ P X ( C S ( X ) ≠ Y ) ] ≥ τ . \operatorname{Inf}(C,P):=\mathbb{E}_S\left[\mathbb{P}_{X\sim P_X}(C_S(X)\ne\mathcal{Y})\right]\ge\tau. Inf ( C , P ) := E S [ P X ∼ P X ( C S ( X ) = Y ) ] ≥ τ . where P X P_X P X X X X P P P
Setting τ → 0 + \tau\to0^+ τ → 0 + 1 − α 1-\alpha 1 − α
Interaction model. The learning process proceeds over multiple rounds. At round t t t f t f_t f t n t n_t n t D ( f t ) D(f_t) D ( f t ) n = ∑ t n t n = \sum_t n_t n = ∑ t n t
Minimax formulation. We evaluate performance in a minimax sense. An algorithm interacts with an unknown distribution map D D D L L L f ⋆ f^\star f ⋆ D D D s : X × Y × F → [ 0 , 1 ] s : \mathcal{X} \times\mathcal{Y} \times\mathcal{F} \to[0,1] s : X × Y × F → [ 0 , 1 ] F \mathcal{F} F d F d_{\mathcal{F}} d F L L L
Without an informativeness constraint the minimax problem is vacuous: the constant procedure C ( x ) = Y C(x) = \mathcal{Y} C ( x ) = Y D D D s s s τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ]
A τ = { algorithms : Inf ( C f ^ , D ( f ⋆ ) ) ≥ τ for every admissible ( D , s ) } \mathcal{A}_{\tau} = \{\text{algorithms} : \operatorname{Inf}(C_{\hat{f}},D(f^\star)) \ge\tau\text{ for every admissible } (D,s)\} A τ = { algorithms : Inf ( C f ^ , D ( f ⋆ )) ≥ τ for every admissible ( D , s )} be the class of τ \tau τ τ \tau τ
M τ ( n , L , F ) = inf alg ∈ A τ sup D , s ExMisc ‾ ( C f ^ , D ( f ⋆ ) ) . \mathcal{M}_{\tau}(n,L,\mathcal{F}) = \inf_{\operatorname{alg} \in\mathcal{A}_{\tau}} \sup_{D,s} \overline{\operatorname{ExMisc}}(C_{\hat{f}},D(f^\star)). M τ ( n , L , F ) = alg ∈ A τ inf D , s sup ExMisc ( C f ^ , D ( f ⋆ )) . In words, the learner seeks an informative algorithm that minimizes worst-case equilibrium marginal excess miscoverage over all L L L n n n F \mathcal{F} F L L L
This objective underlies our lower bound Theorem 3.2 and matching upper bounds (Theorems 4.1 –4.4 ).
Coverage Transfer Theorem
The following lemma turns distributional mismatch into a coverage penalty.
Lemma 2.7 (Coverage Decomposition). Fix predictors h , g ∈ F h, g \in\mathcal{F} h , g ∈ F S ∼ D ( g ) m S \sim D(g)^m S ∼ D ( g ) m C h , S C_{h,S} C h , S s ( ⋅ ; h ) s(\cdot;h) s ( ⋅ ; h ) S S S
P S , ( X , Y ) ∼ D ( h ) ( Y ∈ C h , S ( X ) ) ≥ 1 − α − TV ( D ( h ) , D ( g ) ) . \mathbb{P}_{S,(X,Y)\sim D(h)}(Y \in C_{h,S}(X)) \ge1-\alpha-\operatorname{TV}(D(h),D(g)). P S , ( X , Y ) ∼ D ( h ) ( Y ∈ C h , S ( X )) ≥ 1 − α − TV ( D ( h ) , D ( g )) . (Proof in Appendix C.) Split conformal calibration on S S S 1 − α 1-\alpha 1 − α D ( g ) D(g) D ( g ) D ( h ) D(h) D ( h )
The independence condition is standard in split conformal prediction: conditional on h h h S S S 1 − α 1-\alpha 1 − α S S S h h h S S S
Theorem 2.8 (Coverage Transfer Theorem). *Assume the distribution map D ( ⋅ ) D(\cdot) D ( ⋅ ) L L L d F d_{\mathcal{F}} d F L < 1 L < 1 L < 1 f ^ \hat{f} f ^ d F ( f ^ , f ⋆ ) ≤ ϵ d_{\mathcal{F}}(\hat{f},f^\star) \le\epsilon d F ( f ^ , f ⋆ ) ≤ ϵ C f ^ C_{\hat{f}} C f ^
split conformal calibration using a held-out calibration sample S ∼ D ( f ^ ) m S \sim D(\hat{f})^m S ∼ D ( f ^ ) m f ^ \hat{f} f ^
P S , ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ^ , S ( X ) ) ≥ 1 − α − L ϵ . \mathbb{P}_{S,(X,Y)\sim D(f^\star)}\left(Y \in C_{\hat{f},S}(X)\right) \ge1-\alpha-L\epsilon. P S , ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ^ , S ( X ) ) ≥ 1 − α − L ϵ . Equivalently,
max { 0 , P S , ( X , Y ) ∼ D ( f ⋆ ) ( Y ∉ C f ^ , S ( X ) ) − α } ≤ L ϵ . \max\left\{0,\mathbb{P}_{S,(X,Y)\sim D(f^\star)}\left(Y \notin C_{\hat{f},S}(X)\right)-\alpha\right\} \le L\epsilon. max { 0 , P S , ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ / C f ^ , S ( X ) ) − α } ≤ L ϵ . Proof sketch. Step 1 (validity under D ( f ^ ) D(\hat{f}) D ( f ^ ) D ( f ^ ) D(\hat{f}) D ( f ^ ) f ^ \hat{f} f ^
P S , ( X , Y ) ∼ D ( f ^ ) ( Y ∈ C f ^ , S ( X ) ) ≥ 1 − α . \mathbb{P}_{S,(X,Y)\sim D(\hat{f})}\left(Y \in C_{\hat{f},S}(X)\right) \ge1-\alpha. P S , ( X , Y ) ∼ D ( f ^ ) ( Y ∈ C f ^ , S ( X ) ) ≥ 1 − α . Step 2 (transfer to D ( f ⋆ ) D(f^\star) D ( f ⋆ ) S S S
A S = { ( X , Y ) : Y ∈ C f ^ , S ( X ) } . A_S=\{(X,Y):Y \in C_{\hat{f},S}(X)\}. A S = {( X , Y ) : Y ∈ C f ^ , S ( X )} . This is the event that the prediction set constructed from S S S
P ( X , Y ) ∼ D ( f ⋆ ) ( A S ) ≥ P ( X , Y ) ∼ D ( f ^ ) ( A S ) − TV ( D ( f ^ ) , D ( f ⋆ ) ) . \mathbb{P}_{(X,Y)\sim D(f^\star)}(A_S) \ge\mathbb{P}_{(X,Y)\sim D(\hat{f})}(A_S)-\operatorname{TV}(D(\hat{f}),D(f^\star)). P ( X , Y ) ∼ D ( f ⋆ ) ( A S ) ≥ P ( X , Y ) ∼ D ( f ^ ) ( A S ) − TV ( D ( f ^ ) , D ( f ⋆ )) . This holds for every realization of S S S S S S
P S , ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ^ , S ( X ) ) ≥ 1 − α − TV ( D ( f ^ ) , D ( f ⋆ ) ) . \mathbb{P}_{S,(X,Y)\sim D(f^\star)}\left(Y \in C_{\hat{f},S}(X)\right) \ge1-\alpha-\operatorname{TV}(D(\hat{f}),D(f^\star)). P S , ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ^ , S ( X ) ) ≥ 1 − α − TV ( D ( f ^ ) , D ( f ⋆ )) . By L L L
TV ( D ( f ^ ) , D ( f ⋆ ) ) ≤ L d F ( f ^ , f ⋆ ) ≤ L ϵ . \operatorname{TV}(D(\hat{f}),D(f^\star)) \le Ld_{\mathcal{F}}(\hat{f},f^\star) \le L\epsilon. TV ( D ( f ^ ) , D ( f ⋆ )) ≤ L d F ( f ^ , f ⋆ ) ≤ L ϵ . Combining the two steps proves the claim.
Example: Lending
We illustrate L L L
A bank chooses a credit threshold θ ∈ [ 0 , 1 ] \theta\in[0,1] θ ∈ [ 0 , 1 ] X ≥ θ X \ge\theta X ≥ θ
P ( Y = 1 ∣ X = x ) = g ( x , θ ) , g ( x , θ ) = g 0 ( x ) + λ 1 [ x ≥ θ ] , \mathbb{P}(Y=1\mid X=x)=g(x,\theta),\qquad g(x,\theta)=g_0(x)+\lambda\mathbf{1}[x\ge\theta], P ( Y = 1 ∣ X = x ) = g ( x , θ ) , g ( x , θ ) = g 0 ( x ) + λ 1 [ x ≥ θ ] , where λ \lambda λ
The distribution of scores X X X θ \theta θ θ \theta θ θ ′ \theta' θ ′
X ∈ [ min ( θ , θ ′ ) , max ( θ , θ ′ ) ] . X \in[\min(\theta,\theta'),\max(\theta,\theta')]. X ∈ [ min ( θ , θ ′ ) , max ( θ , θ ′ )] . The total variation distance between D ( θ ) D(\theta) D ( θ ) D ( θ ′ ) D(\theta') D ( θ ′ )
TV ( D ( θ ) , D ( θ ′ ) ) ≤ λ P ( X ∈ [ min ( θ , θ ′ ) , max ( θ , θ ′ ) ] ) . \operatorname{TV}(D(\theta),D(\theta')) \le\lambda\mathbb{P}\left(X \in[\min(\theta,\theta'),\max(\theta,\theta')]\right). TV ( D ( θ ) , D ( θ ′ )) ≤ λ P ( X ∈ [ min ( θ , θ ′ ) , max ( θ , θ ′ )] ) . If the score distribution has density bounded by B B B
P ( X ∈ [ θ ′ , θ ] ) ≤ B ∣ θ − θ ′ ∣ , \mathbb{P}(X \in[\theta', \theta]) \le B|\theta-\theta'|, P ( X ∈ [ θ ′ , θ ]) ≤ B ∣ θ − θ ′ ∣ , so
TV ( D ( θ ) , D ( θ ′ ) ) ≤ λ B ∣ θ − θ ′ ∣ . \operatorname{TV}(D(\theta),D(\theta')) \le\lambda B|\theta-\theta'|. TV ( D ( θ ) , D ( θ ′ )) ≤ λ B ∣ θ − θ ′ ∣. Thus the distribution map is L L L L = λ B L=\lambda B L = λ B λ \lambda λ B B B θ \theta θ L L L λ B < 1 \lambda B<1 λ B < 1
Strategic Classification
Strategic classification [10 , 6 , 25 , 23 , 20 ] provides a natural instance of performative prediction. A population of agents has features X ∈ X X \in\mathcal{X} X ∈ X Y ∈ { 0 , 1 } Y \in\{0,1\} Y ∈ { 0 , 1 } f f f x x x x ′ = Δ ( x ; f ) x'=\Delta(x;f) x ′ = Δ ( x ; f ) c ( x , x ′ ) c(x,x') c ( x , x ′ ) D ( f ) D(f) D ( f )
Sensitivity from manipulation costs. If agents’ best-response functions are Lipschitz in f f f D ( ⋅ ) D(\cdot) D ( ⋅ ) L L L L = sup x Lip ( Δ ( x ; ⋅ ) ) L=\sup_x \operatorname{Lip}(\Delta(x;\cdot)) L = sup x Lip ( Δ ( x ; ⋅ )) L L L L L L
Interpretation. L ≥ 1 L \ge1 L ≥ 1 Theorem 3.1 ) establishes that nontrivial prediction sets are impossible in this regime. L < 1 L<1 L < 1 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 L = 0.7 L=0.7 L = 0.7 11 × 11\times 11 ×
Worked example. Let X = R d \mathcal{X}=\mathbb{R}^d X = R d Y = { 0 , 1 } \mathcal{Y}=\{0,1\} Y = { 0 , 1 } f θ ( x ) = 1 [ θ ⊤ x ≥ 0 ] f_\theta(x)=1[\theta^\top x\ge0] f θ ( x ) = 1 [ θ ⊤ x ≥ 0 ]
Δ ( x ; θ ) = arg min x ′ − θ ⊤ x ′ + c ∥ x ′ − x ∥ 2 . \Delta(x;\theta)=\underset{x'}{\operatorname{arg\,min}}\ -\theta^\top x' + c\lVert x'-x\rVert^2. Δ ( x ; θ ) = x ′ arg min − θ ⊤ x ′ + c ∥ x ′ − x ∥ 2 . Setting the gradient to zero gives x ′ = x + θ / ( 2 c ) x'=x+\theta/(2c) x ′ = x + θ / ( 2 c ) θ \theta θ 1 / c 1/c 1/ c c c c L L L c c c L L L
When c c c L < 1 L<1 L < 1
This strategic-classification perspective motivates our semi-synthetic experiment in § 5.1 . There we vary the feedback strength in a lending-related dataset to illustrate the role of L L L
Main Results: A Phase Transition at L = 1 L = 1 L = 1
Our main results show a sharp phase transition at L = 1 L = 1 L = 1 L ≥ 1 L \ge1 L ≥ 1 L < 1 L < 1 L < 1 Θ ~ ( 1 / ( 1 − L ) 2 ) \widetilde{\Theta}(1/(1-L)^2) Θ ( 1/ ( 1 − L ) 2 )
Impossibility When L ≥ 1 L \ge1 L ≥ 1
When L ≥ 1 L \ge1 L ≥ 1
Theorem 3.1 (Impossibility for L ≥ 1 L \ge1 L ≥ 1 L ≥ 1 L \ge1 L ≥ 1 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) n ∈ N n \in\mathbb{N} n ∈ N n n n L L L f ⋆ f^\star f ⋆
(a) Equilibrium-valid coverage:
P ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ^ ( X ) ) ≥ 1 − α ; \mathbb{P}_{(X,Y)\sim D(f^\star)}\left(Y \in C_{\hat{f}}(X)\right) \ge1-\alpha; P ( X , Y ) ∼ D ( f ⋆ ) ( Y ∈ C f ^ ( X ) ) ≥ 1 − α ; (b) Nontriviality:
P X ∼ D X ( f ⋆ ) ( C f ^ ( X ) ≠ Y ) > 0 , \mathbb{P}_{X\sim D_X(f^\star)}\left(C_{\hat{f}}(X) \ne\mathcal{Y}\right) > 0, P X ∼ D X ( f ⋆ ) ( C f ^ ( X ) = Y ) > 0 , where D X ( f ⋆ ) D_X(f^\star) D X ( f ⋆ ) X X X D ( f ⋆ ) D(f^\star) D ( f ⋆ )
Equivalently, for every such algorithm, there exists an L L L
Proof sketch. It suffices to prove the claim for L = 1 L = 1 L = 1 1 1 1 L L L L ≥ 1 L \ge1 L ≥ 1
Consider a one-dimensional predictor class F = Θ = [ 0 , 1 ] \mathcal{F} = \Theta= [0,1] F = Θ = [ 0 , 1 ] X = { x 0 } \mathcal{X} = \{x_0\} X = { x 0 } Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } ℓ ( θ , y ) = ( θ − y ) 2 \ell(\theta,y) = (\theta-y)^2 ℓ ( θ , y ) = ( θ − y ) 2 1 1 1
D + ( θ ) : Y ∼ Bern ( min ( θ + ϵ , 1 − ϵ ) ) , D_+(\theta):\quad Y \sim\operatorname{Bern}\left(\min(\theta+\epsilon,1-\epsilon)\right), D + ( θ ) : Y ∼ Bern ( min ( θ + ϵ , 1 − ϵ ) ) , D − ( θ ) : Y ∼ Bern ( max ( θ − ϵ , ϵ ) ) . D_-(\theta):\quad Y \sim\operatorname{Bern}\left(\max(\theta-\epsilon,\epsilon)\right). D − ( θ ) : Y ∼ Bern ( max ( θ − ϵ , ϵ ) ) . These maps admit performatively stable predictors, namely θ + ⋆ = 1 − ϵ \theta_+^\star= 1-\epsilon θ + ⋆ = 1 − ϵ θ − ⋆ = ϵ \theta_-^\star= \epsilon θ − ⋆ = ϵ Bern ( 1 − ϵ ) \operatorname{Bern}(1-\epsilon) Bern ( 1 − ϵ ) Bern ( ϵ ) \operatorname{Bern}(\epsilon) Bern ( ϵ )
At any deployment θ \theta θ D + ( θ ) D_+(\theta) D + ( θ ) D − ( θ ) D_-(\theta) D − ( θ ) 2 ϵ 2\epsilon 2 ϵ [ ϵ , 1 − ϵ ] [\epsilon,1-\epsilon] [ ϵ , 1 − ϵ ] O ( ϵ ) O(\epsilon) O ( ϵ ) θ \theta θ ϵ = c / n \epsilon= c/n ϵ = c / n n n n
However, because X \mathcal{X} X Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } { 0 } \{0\} { 0 } { 1 } \{1\} { 1 } ϵ < min ( α , 1 − α ) \epsilon< \min(\alpha,1-\alpha) ϵ < min ( α , 1 − α ) D + ( θ + ⋆ ) = Bern ( 1 − ϵ ) D_+(\theta_+^\star) = \operatorname{Bern}(1-\epsilon) D + ( θ + ⋆ ) = Bern ( 1 − ϵ ) 1 − α 1-\alpha 1 − α { 1 } \{1\} { 1 } D − ( θ − ⋆ ) = Bern ( ϵ ) D_-(\theta_-^\star) = \operatorname{Bern}(\epsilon) D − ( θ − ⋆ ) = Bern ( ϵ ) 1 − α 1-\alpha 1 − α { 0 } \{0\} { 0 } [16 ] , the bounded KL divergence implies that no algorithm can distinguish D + D_{+} D + D − D_{-} D −
The full proof, including the extension to general spaces, is in Appendix A. That extension shows that this binary construction can be embedded into an arbitrary feature and label space.
The implication is direct. When L ≥ 1 L \ge1 L ≥ 1 L L L
Minimax Rate When L < 1 L < 1 L < 1
When L < 1 L < 1 L < 1
Theorem 3.2 (Minimax Lower Bound for L < 1 L < 1 L < 1 D ( ⋅ ) D(\cdot) D ( ⋅ ) L L L L < 1 L < 1 L < 1 τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] n n n τ \tau τ
M τ ( n , L , F ) ≥ Ω ~ ( 1 ( 1 − L ) n ) . \mathcal{M}_{\tau}(n,L,\mathcal{F}) \ge\widetilde{\Omega}\left(\frac{1}{(1-L)\sqrt{n}}\right). M τ ( n , L , F ) ≥ Ω ( ( 1 − L ) n 1 ) . Equivalently, for every algorithm in A τ \mathcal{A}_{\tau} A τ L L L
ExMisc ( C f ^ , D ( f ⋆ ) ) ≥ Ω ~ ( 1 ( 1 − L ) n ) . \operatorname{ExMisc}(C_{\hat{f}},D(f^{\star})) \ge\widetilde{\Omega}\left(\frac{1}{(1-L)\sqrt{n}}\right). ExMisc ( C f ^ , D ( f ⋆ )) ≥ Ω ( ( 1 − L ) n 1 ) . The restriction to A τ \mathcal{A}_{\tau} A τ τ \tau τ τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ]
Matching upper bounds appear in § 4 . We sketch the lower bound here; the full proof is in Appendix B.
Lower bound construction. We use Le Cam’s two-point method. Consider two L L L X = { x 0 } \mathcal{X} = \{x_{0}\} X = { x 0 } Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 }
D i ( θ ) : Y ∼ Bern ( a + i δ + L θ ) , i ∈ { 0 , 1 } , D_{i}(\theta):\quad Y \sim\operatorname{Bern}(a+i\delta+L\theta),\qquad i \in\{0,1\}, D i ( θ ) : Y ∼ Bern ( a + i δ + L θ ) , i ∈ { 0 , 1 } , where a a a
θ i ⋆ = a + i δ 1 − L . \theta_{i}^{\star} = \frac{a+i\delta}{1-L}. θ i ⋆ = 1 − L a + i δ . Thus the two environments differ by only δ \delta δ θ \theta θ
∣ θ 1 ⋆ − θ 0 ⋆ ∣ = δ 1 − L . \left|\theta_{1}^{\star}-\theta_{0}^{\star}\right| = \frac{\delta}{1-L}. ∣ θ 1 ⋆ − θ 0 ⋆ ∣ = 1 − L δ . This is the key amplification effect: a local perturbation of size δ \delta δ 1 / ( 1 − L ) 1/(1-L) 1/ ( 1 − L )
At the same time, the two environments are statistically hard to distinguish:
p 1 ( θ ) − p 0 ( θ ) = δ for every θ , p_1(\theta)-p_0(\theta)=\delta\quad\text{for every } \theta, p 1 ( θ ) − p 0 ( θ ) = δ for every θ , so the per-sample KL divergence is O ( δ 2 ) O(\delta^2) O ( δ 2 ) O ( δ 2 ) O(\delta^2) O ( δ 2 ) n n n O ( n δ 2 ) O(n\delta^2) O ( n δ 2 )
Choosing δ = c / n \delta=c/\sqrt{n} δ = c / n
Ω ( δ 1 − L ) = Ω ( 1 ( 1 − L ) n ) . \Omega\left(\frac{\delta}{1-L}\right)=\Omega\left(\frac{1}{(1-L)\sqrt{n}}\right). Ω ( 1 − L δ ) = Ω ( ( 1 − L ) n 1 ) . The full proof is given in Appendix B.
The Price of Performativity
Theorems 3.1 and 3.2 together give a complete picture as a function of L L L
Table 2.
The factor 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 price of performativity : how the sample size must grow to maintain a fixed accuracy under endogenous distribution shift. If excess miscoverage scales as O ~ ( 1 / ( ( 1 − L ) n ) ) \widetilde{O}(1/((1-L)\sqrt{n})) O ( 1/ (( 1 − L ) n )) ϵ \epsilon ϵ
O ~ ( 1 ( 1 − L ) n ) ≤ ϵ ⟹ n ≥ Ω ~ ( 1 ( 1 − L ) 2 ϵ 2 ) . \widetilde{O}\left(\frac{1}{(1-L)\sqrt{n}}\right)\leq\epsilon
\quad\Longrightarrow\quad
n\geq\widetilde{\Omega}\left(\frac{1}{(1-L)^2\epsilon^2}\right). O ( ( 1 − L ) n 1 ) ≤ ϵ ⟹ n ≥ Ω ( ( 1 − L ) 2 ϵ 2 1 ) . Thus the cost is constant at L = 0 L=0 L = 0 L → 1 L\to1 L → 1 L = 0.5 L=0.5 L = 0.5 4 × 4\times 4 × L = 0.9 L=0.9 L = 0.9 100 × 100\times 100 × L = 1 L=1 L = 1
The intuition is that performative feedback magnifies statistical error. A local estimation error of size ϵ \epsilon ϵ ϵ \epsilon ϵ 1 / ( 1 − L ) 1/(1-L) 1/ ( 1 − L ) Δ \Delta Δ Δ ( 1 − L ) \Delta(1-L) Δ ( 1 − L ) ϵ \epsilon ϵ 1 / ϵ 2 1/\epsilon^2 1/ ϵ 2 1 / ( Δ 2 ( 1 − L ) 2 ) 1/(\Delta^2(1-L)^2) 1/ ( Δ 2 ( 1 − L ) 2 ) ( 1 − L ) − 2 (1-L)^{-2} ( 1 − L ) − 2
Algorithms
Section 2.3 reduces equilibrium-valid coverage to a constructive problem: produce a predictor close to performative equilibrium, then transfer that predictor error into a coverage guarantee. This section gives two retraining-based algorithms that follow this template. The model-free method gives general achievability under minimal assumptions, while the parametric method sharpens the rate under stronger regularity.
Model-Free Algorithm
We begin with a finite-class model-free setting, meaning that we do not assume a parametric or differentiable form for the performative map. The main structural assumption is L < 1 L < 1 L < 1
Algorithm 1 Model-Free Performative Conformal Prediction (MF-PCP)
Require: Finite predictor class F \mathcal{F} F ∣ F ∣ = N |\mathcal{F}| = N ∣ F ∣ = N s s s ℓ \ell ℓ n n n T T T α \alpha α f 0 ∈ F f_0 \in\mathcal{F} f 0 ∈ F
Set m = ⌊ n / ( T + 1 ) ⌋ m = \left\lfloor n/(T+1) \right\rfloor m = ⌊ n / ( T + 1 ) ⌋
for t = 1 , … , T t = 1,\ldots,T t = 1 , … , T do
Deploy f t − 1 f_{t-1} f t − 1 m m m S t S_t S t D ( f t − 1 ) D(f_{t-1}) D ( f t − 1 )
f t ← arg min f ∈ F R ^ ( f ; S t ) f_t \leftarrow\mathop{\arg\min}_{f\in\mathcal{F}} \widehat{R}(f;S_t) f t ← arg min f ∈ F R ( f ; S t ) F \mathcal{F} F ℓ \ell ℓ
end for
Deploy f T f_T f T m m m S T + 1 S_{T+1} S T + 1 D ( f T ) D(f_T) D ( f T )
q ^ ← ⌈ ( 1 − α ) ( ∣ S T + 1 ∣ + 1 ) ⌉ \widehat{q} \leftarrow\left\lceil(1-\alpha)(|S_{T+1}|+1)\right\rceil q ← ⌈ ( 1 − α ) ( ∣ S T + 1 ∣ + 1 ) ⌉ S T + 1 S_{T+1} S T + 1 s ( x , y ; f T ) s(x,y;f_T) s ( x , y ; f T )
return f T f_T f T C f T ( x ) = { y : s ( x , y ; f T ) ≤ q ^ } C_{f_T}(x)=\{y:s(x,y;f_T)\le\widehat{q}\} C f T ( x ) = { y : s ( x , y ; f T ) ≤ q }
For a finite class with bounded loss, empirical risk minimization (ERM) based on m m m O ( log N / m ) O(\sqrt{\log N/m}) O ( log N / m ) [32 ] ). Applied at round t t t f t f_t f t D ( f t − 1 ) D(f_{t-1}) D ( f t − 1 ) μ > 0 \mu> 0 μ > 0
d F ( f , f t − 1 † ) ≤ 1 μ ( R ( f ; D ( f t − 1 ) ) − R ( f t − 1 † ; D ( f t − 1 ) ) ) , d_{\mathcal{F}}(f,f^\dagger_{t-1}) \leq\frac{1}{\mu}\left(R(f;D(f_{t-1}))-R(f^\dagger_{t-1};D(f_{t-1}))\right), d F ( f , f t − 1 † ) ≤ μ 1 ( R ( f ; D ( f t − 1 )) − R ( f t − 1 † ; D ( f t − 1 )) ) , where f t − 1 † f_{t-1}^{\dagger} f t − 1 † D ( f t − 1 ) D(f_{t-1}) D ( f t − 1 )
d F ( f t , f t − 1 † ) = O ( 1 μ log N m ) d_{\mathcal{F}}(f_t,f_{t-1}^{\dagger})=O\left(\frac{1}{\mu}\sqrt{\frac{\log N}{m}}\right) d F ( f t , f t − 1 † ) = O ( μ 1 m log N ) which can then be combined with the L L L d F ( f t , f ⋆ ) d_{\mathcal{F}}(f_t,f^\star) d F ( f t , f ⋆ )
Theorem 4.1 (Model-Free Upper Bound). Under L L L L < 1 L<1 L < 1 ℓ ∈ [ 0 , 1 ] \ell\in[0,1] ℓ ∈ [ 0 , 1 ] ∣ F ∣ = N |\mathcal{F}|=N ∣ F ∣ = N μ > 0 \mu>0 μ > 0 0 < L < 1 0<L<1 0 < L < 1
T = ⌈ log n log ( 1 / L ) ⌉ T=\left\lceil\frac{\log n}{\log(1/L)}\right\rceil T = ⌈ log ( 1/ L ) log n ⌉ then
ExMisc ‾ ( C f T , S , D ( f ⋆ ) ) ≤ O ~ ( 1 ( 1 − L ) 3 / 2 n ) . \overline{\operatorname{ExMisc}}(\mathcal{C}_{f_T,S},D(f^\star))\leq\widetilde{O}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right). ExMisc ( C f T , S , D ( f ⋆ )) ≤ O ( ( 1 − L ) 3/2 n 1 ) . For L = 0 L=0 L = 0 T = 1 T=1 T = 1
Proof sketch. Let m = ⌊ n / ( T + 1 ) ⌋ m=\lfloor n/(T+1)\rfloor m = ⌊ n / ( T + 1 )⌋
O ~ N , μ ( 1 m ) \widetilde{O}_{N,\mu}\left(\frac{1}{\sqrt{m}}\right) O N , μ ( m 1 ) in d F d_{\mathcal{F}} d F
d F ( f T , f ⋆ ) ≤ L T d F ( f 0 , f ⋆ ) + ∑ k = 0 T − 1 L k O ~ N , μ ( 1 m ) ≤ L T d F ( f 0 , f ⋆ ) + 1 1 − L O ~ N , μ ( 1 m ) . \begin{aligned}
d_{\mathcal{F}}(f_T,f^\star)\leq L^T d_{\mathcal{F}}(f_0,f^\star)+\sum_{k=0}^{T-1}L^k\widetilde{O}_{N,\mu}\left(\frac{1}{\sqrt{m}}\right) \\
&\leq L^T d_{\mathcal{F}}(f_0,f^\star)+\frac{1}{1-L}\widetilde{O}_{N,\mu}\left(\frac{1}{\sqrt{m}}\right).
\end{aligned} d F ( f T , f ⋆ ) ≤ L T d F ( f 0 , f ⋆ ) + k = 0 ∑ T − 1 L k O N , μ ( m 1 ) ≤ L T d F ( f 0 , f ⋆ ) + 1 − L 1 O N , μ ( m 1 ) . The first term is the transient error from the initialization, while the second is the accumulated statistical error across rounds. With
T = ⌈ log n log ( 1 / L ) ⌉ , T=\left\lceil\frac{\log n}{\log(1/L)}\right\rceil, T = ⌈ log ( 1/ L ) log n ⌉ , we have L T ≤ 1 / n L^T\leq1/n L T ≤ 1/ n log ( 1 / L ) ≥ 1 − L \log(1/L)\geq1-L log ( 1/ L ) ≥ 1 − L 0 < L < 1 0<L<1 0 < L < 1
T = O ( log n 1 − L ) , T=O\left(\frac{\log n}{1-L}\right), T = O ( 1 − L log n ) , and hence
m = Ω ( n ( 1 − L ) log n ) . m=\Omega\left(\frac{n(1-L)}{\log n}\right). m = Ω ( log n n ( 1 − L ) ) . Substituting this into the accumulated error term yields
1 1 − L O ~ N , μ ( 1 m ) = O ~ N , μ ( 1 ( 1 − L ) 3 / 2 n ) . \frac{1}{1-L}\widetilde{O}_{N,\mu}\left(\frac{1}{\sqrt{m}}\right)=\widetilde{O}_{N,\mu}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right). 1 − L 1 O N , μ ( m 1 ) = O N , μ ( ( 1 − L ) 3/2 n 1 ) . Thus,
d F ( f T , f ⋆ ) = O ~ N , μ ( 1 ( 1 − L ) 3 / 2 n ) . d_F(f_T,f^\star)=\widetilde{O}_{N,\mu}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right). d F ( f T , f ⋆ ) = O N , μ ( ( 1 − L ) 3/2 n 1 ) . The retraining phase bounds the distance between f T f_T f T f ⋆ f^\star f ⋆ D ( f T ) D(f_T) D ( f T ) Theorem 2.8 translates this distance bound into the stated excess-miscoverage guarantee under D ( f ⋆ ) D(f^\star) D ( f ⋆ )
Remark 4.2. The model-free rate has an extra ( 1 − L ) − 1 / 2 (1-L)^{-1/2} ( 1 − L ) − 1/2 O ( log n / ( 1 − L ) ) O(\log n/(1-L)) O ( log n / ( 1 − L )) Theorem 4.4 ) by exploiting the AR(1) autocorrelation structure of the iterates. Whether the information-theoretic rate is achievable over finite classes without smoothness assumptions is an open question.
Remark 4.3 (Beyond Finite Classes). Although Theorem 4.1 is stated for a finite class F \mathcal{F} F F \mathcal{F} F
Parametric Algorithm
We now turn to continuous parametric classes, where predictors are parameterized by vectors in a convex subset of R d \mathbb{R}^d R d
Under these assumptions, the population retraining map is contractive, so repeated retraining drives the predictor toward equilibrium. Finite samples introduce noise at each round. Averaging later iterates reduces this noise, but averaging too early retains too much dependence on the initial predictor. We therefore use a short stabilization period and average only the later iterates, in the spirit of Polyak–Ruppert averaging ([30 , 29 ] ).
Theorem 4.4 (Parametric Upper Bound). Assume F ⊆ R d \mathcal{F} \subseteq\mathbb{R}^d F ⊆ R d d F ( ⋅ , ⋅ ) = ∥ ⋅ − ⋅ ∥ 2 d_F(\cdot,\cdot)=\|\cdot-\cdot\|_2 d F ( ⋅ , ⋅ ) = ∥ ⋅ − ⋅ ∥ 2 D ( ⋅ ) D(\cdot) D ( ⋅ ) L L L D D D R D R_D R D β \beta β γ \gamma γ F \mathcal{F} F
ρ : = L β γ , ρ < 1. \rho:= \frac{L\beta}{\gamma}, \qquad\rho< 1. ρ := γ L β , ρ < 1. Run Algorithm 2 with stabilization length and averaging window satisfying
B = O ( log n 1 − ρ ) , K = O ( log n 1 − ρ ) . B=O\left(\frac{\log n}{1-\rho}\right), \qquad K=O\left(\frac{\log n}{1-\rho}\right). B = O ( 1 − ρ log n ) , K = O ( 1 − ρ log n ) . Algorithm 2 Parametric Performative Conformal Prediction (P-PCP)
Require: Initial predictor f 0 f_0 f 0 n n n B B B K K K α \alpha α
Set m = ⌊ n / ( B + K + 1 ) ⌋ m = \lfloor n/(B + K + 1) \rfloor m = ⌊ n / ( B + K + 1 )⌋
for t = 1 , … , B + K t = 1, \ldots, B + K t = 1 , … , B + K do
Deploy f t − 1 f_{t-1} f t − 1 m m m S t ∼ D ( f t − 1 ) S_t \sim D(f_{t-1}) S t ∼ D ( f t − 1 )
Retrain by ERM:
f t ← arg min f ∈ F R ^ ( f ; S t ) f_t \leftarrow\underset{f \in\mathcal{F}}{\arg\min}\ \widehat{R}(f; S_t) f t ← f ∈ F arg min R ( f ; S t ) end for
Form the tail-averaged predictor
f ‾ B , K ← 1 K ∑ t = B + 1 B + K f t \overline{f}_{B,K} \leftarrow\frac{1}{K}\sum_{t=B+1}^{B+K} f_t f B , K ← K 1 t = B + 1 ∑ B + K f t Deploy f ‾ B , K \overline{f}_{B,K} f B , K m m m S B + K + 1 ∼ D ( f ‾ B , K ) S_{B+K+1} \sim D(\overline{f}_{B,K}) S B + K + 1 ∼ D ( f B , K )
Let q ^ \widehat{q} q ⌈ ( 1 − α ) ( m + 1 ) ⌉ \lceil(1-\alpha)(m+1)\rceil ⌈( 1 − α ) ( m + 1 )⌉ { s ( x , y ; f ‾ B , K ) : ( x , y ) ∈ S B + K + 1 } \{s(x,y;\overline{f}_{B,K}) : (x,y) \in S_{B+K+1}\} { s ( x , y ; f B , K ) : ( x , y ) ∈ S B + K + 1 }
return f ‾ B , K \overline{f}_{B,K} f B , K
C f ‾ B , K ( x ) = { y : s ( x , y ; f ‾ B , K ) ≤ q ^ } C_{\overline{f}_{B,K}}(x) = \{y : s(x,y;\overline{f}_{B,K}) \le\widehat{q}\} C f B , K ( x ) = { y : s ( x , y ; f B , K ) ≤ q } Then
ExMisc ‾ ( C f ‾ B , K , D ( f ⋆ ) ) ≤ O ~ ( 1 ( 1 − ρ ) n ) . \overline{\operatorname{ExMisc}}(C_{\overline{f}_{B,K}}, D(f^\star)) \le\widetilde{O}\left(\frac{1}{(1-\rho)\sqrt{n}}\right). ExMisc ( C f B , K , D ( f ⋆ )) ≤ O ( ( 1 − ρ ) n 1 ) . When ρ ≍ L \rho\asymp L ρ ≍ L β / γ ≈ 1 \beta/\gamma\approx1 β / γ ≈ 1 n n n L L L Theorem 3.2 ) up to logarithmic factors under the stated regularity conditions.
Proof sketch. Under smoothness and strong convexity, the population minimizer varies Lipschitzly with the underlying distribution; combined with L L L ρ = L β / γ \rho= L\beta/\gamma ρ = L β / γ
Thus repeated retraining moves the predictor toward equilibrium, and the effect of the initial predictor shrinks by a factor ρ \rho ρ B B B K K K
d F ( f ‾ B , K , f ⋆ ) = O ~ ( 1 ( 1 − ρ ) n ) . d_{\mathcal{F}}(\overline{f}_{B,K}, f^\star) = \widetilde{O}\left(\frac{1}{(1-\rho)\sqrt{n}}\right). d F ( f B , K , f ⋆ ) = O ( ( 1 − ρ ) n 1 ) . The transfer theorem (Theorem 2.8 ) then converts this predictor error into the stated excess miscoverage bound. Full details are given in Appendix C.
that are themselves τ \tau τ q ^ \hat{q} q ^ ⌈ ( 1 − α ) ( m + 1 ) ⌉ \lceil(1-\alpha)(m+1)\rceil ⌈( 1 − α ) ( m + 1 )⌉ ( 1 − α ) (1-\alpha) ( 1 − α ) q ^ \hat{q} q ^ sup s \sup s sup s Inf ( C f ^ , D ( f ∗ ) ) ≥ τ \operatorname{Inf}(C_{\hat{f}},D(f^*)) \ge\tau Inf ( C f ^ , D ( f ∗ )) ≥ τ τ > 0 \tau> 0 τ > 0 A τ A_\tau A τ
Comparing the Two Algorithms
Table 1 summarizes the tradeoffs between the two approaches. The model-free method requires only bounded loss but incurs an additional ( 1 − L ) − 1 / 2 (1-L)^{-1/2} ( 1 − L ) − 1/2 ( 1 − L ) − 1 / 2 (1-L)^{-1/2} ( 1 − L ) − 1/2 β / γ ≈ 1 \beta/\gamma\approx1 β / γ ≈ 1
Table 1. Comparison of the two algorithms
This comparison also clarifies the mechanics of the transfer theorem. The minimax lower bound depends exclusively on the performative sensitivity L L L Theorem 3.2 ), capturing the statistical difficulty induced by feedback. By contrast, the parametric upper bound depends on ρ = L β / γ \rho= L\beta/\gamma ρ = L β / γ L L L β \beta β γ \gamma γ
Experiments
This section serves two purposes. We first show practical relevance in a semi-synthetic credit-scoring task, where performative feedback causes a standard conformal baseline to fail and where equilibrium-aware retraining restores coverage. We then turn to controlled synthetic models that isolate the dependence predicted by the theory on L L L n n n
Semi-Synthetic Case Study: Strategic Regression in Credit Scoring
We begin with a semi-synthetic strategic regression task based on the Kaggle “Give Me Some Credit” dataset [15 ] . The goal is to test the method under realistic covariates and model misspecification, rather than only in stylized synthetic settings.
Results. Figure 3 presents the results of the semi-synthetic experiment. As the manipulation strength ϵ \epsilon ϵ ϵ \epsilon ϵ
(a) Equilibrium coverage versus ϵ \epsilon ϵ
(b) Prediction interval width versus ϵ \epsilon ϵ
Figure 3. Semi-synthetic strategic regression experiment. (a) Equilibrium coverage versus manipulation strength ϵ \epsilon ϵ ϵ \epsilon ϵ
Figure 3b shows the corresponding interval widths. In this run, the naive baseline stays nearly flat as ϵ \epsilon ϵ
Synthetic Illustrations of the Theory
We now turn to controlled synthetic models. Their role is different: they isolate the dependence on L L L n n n Y ∼ N ( a + L θ , 1 ) Y \sim\mathcal{N}(a + L\theta,1) Y ∼ N ( a + L θ , 1 ) a = 0.3 a = 0.3 a = 0.3 s ( y ; θ ) = ∣ y − θ ∣ s(y;\theta) = |y-\theta| s ( y ; θ ) = ∣ y − θ ∣ α = 0.1 \alpha= 0.1 α = 0.1 D ( f ⋆ ) D(f^\star) D ( f ⋆ )
Rate and price of performativity (Simulation 1; Theorem 3.2). We use Algorithm 2 as a testbed to examine the scaling predicted by Theorem 3.2 . For each fixed L L L Θ ~ ( 1 / ( ( 1 − L ) n ) ) \widetilde{\Theta}(1/((1-L)\sqrt{n})) Θ ( 1/ (( 1 − L ) n )) n − 1 / 2 n^{-1/2} n − 1/2 ( 1 − L ) − 1 (1-L)^{-1} ( 1 − L ) − 1 L ∈ { 0 , 0.1 , … , 0.7 } L \in\{0,0.1,\ldots,0.7\} L ∈ { 0 , 0.1 , … , 0.7 } n ∈ { 50 , … , 100,000 } n \in\{50,\ldots,100{,}000\} n ∈ { 50 , … , 100 , 000 } Figure 1 a plots excess miscoverage against n n n n − 1 / 2 n^{-1/2} n − 1/2 L L L L L L
Figure 1. Synthetic validation of the theory. (a) Excess miscoverage versus sample size n n n L ∈ { 0 , … , 0.7 } L \in\{0,\ldots,0.7\} L ∈ { 0 , … , 0.7 } n − 1 / 2 n^{-1/2} n − 1/2 n ⋆ ( L ) n^\star(L) n ⋆ ( L ) n n n 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 L ε L\varepsilon L ε L L L 1 − α − L ε 1-\alpha-L\varepsilon 1 − α − L ε
Figure 1 b shows the same relationship in sample-complexity form. Since Theorem 3.2 predicts excess miscoverage of order Θ ~ ( 1 / ( ( 1 − L ) n ) ) \widetilde{\Theta}(1/((1-L)\sqrt{n})) Θ ( 1/ (( 1 − L ) n )) Θ ~ ( 1 / ( 1 − L ) 2 ) \widetilde{\Theta}(1/(1-L)^2) Θ ( 1/ ( 1 − L ) 2 ) n ⋆ ( L ) n^\star(L) n ⋆ ( L ) 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 n ⋆ ( L ) n^\star(L) n ⋆ ( L ) n ⋆ ≈ 107 / ( 1 − L ) 2 + 97 n^\star\approx107/(1-L)^2 + 97 n ⋆ ≈ 107/ ( 1 − L ) 2 + 97 R 2 = 0.948 R^2 = 0.948 R 2 = 0.948 Θ ~ ( 1 / ( 1 − L ) 2 ) \widetilde{\Theta}(1/(1-L)^2) Θ ( 1/ ( 1 − L ) 2 )
Transfer theorem (Simulation 2; Theorem 2.8). We next test the main prediction of the transfer theorem. For a deployed predictor at distance
ϵ = ∣ θ d e p l o y e d − θ ⋆ ∣ \epsilon= |\theta_{\mathrm{deployed}}-\theta^\star| ϵ = ∣ θ deployed − θ ⋆ ∣ from equilibrium, the theorem implies that the leading-order coverage loss should depend on the single quantity L ε L\varepsilon L ε m = 2000 m = 2000 m = 2000 ε \varepsilon ε L L L
Figure 1 c plots coverage against L ε L\varepsilon L ε L ε ≤ 0.3 L\varepsilon\le0.3 L ε ≤ 0.3 1 − α − L ε 1-\alpha-L\varepsilon 1 − α − L ε L ε L\varepsilon L ε L L L ε \varepsilon ε
Phase transition at L = 1 L = 1 L = 1 We next illustrate the feasibility boundary predicted by Theorem 3.1 using bounded Bernoulli maps whose equilibria remain explicit on both sides of the threshold. Figure 2 reports the results.
Figure 2. Phase transition at L = 1 L = 1 L = 1 g L , ± ( θ ) = clip ( c + L ( θ − c ) ± ϵ , [ ϵ , 1 − ϵ ] ) g_{L,\pm}(\theta) = \operatorname{clip}(c + L(\theta-c)\pm\epsilon, [\epsilon, 1-\epsilon]) g L , ± ( θ ) = clip ( c + L ( θ − c ) ± ϵ , [ ϵ , 1 − ϵ ]) c = 0.05 c = 0.05 c = 0.05 ϵ = 0.01 \epsilon= 0.01 ϵ = 0.01 + + + − - − L L L L = 1 L = 1 L = 1
Figure 2 sweeps L ∈ { 0.7 , 0.8 , 0.9 , 0.95 , 0.98 , 0.99 , 1.0 , 1.01 , 1.02 , 1.05 , 1.1 , 1.2 } L \in\{0.7, 0.8, 0.9, 0.95, 0.98, 0.99, 1.0, 1.01, 1.02, 1.05, 1.1, 1.2\} L ∈ { 0.7 , 0.8 , 0.9 , 0.95 , 0.98 , 0.99 , 1.0 , 1.01 , 1.02 , 1.05 , 1.1 , 1.2 }
g L , ± ( θ ) = clip ( c + L ( θ − c ) ± ε , [ ε , 1 − ε ] ) , c = 0.05 , ε = 0.01 , g_{L,\pm}(\theta) = \operatorname{clip}(c + L(\theta-c) \pm\varepsilon, [\varepsilon, 1-\varepsilon]), \qquad c = 0.05, \quad\varepsilon= 0.01, g L , ± ( θ ) = clip ( c + L ( θ − c ) ± ε , [ ε , 1 − ε ]) , c = 0.05 , ε = 0.01 , and reports conservative equilibrium coverage (the minimum over the two branches) together with the unrestricted full-set rate (the maximum over the two branches). As L L L L L L L ≥ 1 L \ge1 L ≥ 1
Related Work
Performative prediction. The performative prediction framework of Perdomo et al. [27 ] shows that when L < 1 L < 1 L < 1 L → 1 L \to1 L → 1 [22 ] , regret under performativity [14 ] , state-dependent feedback [4 ] , and performative power [11 ] . This entire line of work asks how quickly a system reaches equilibrium and how to minimize performative risk. We ask a different question: once the system has stabilized, how reliably can we quantify prediction uncertainty? The connection is that the same parameter L L L
Conformal prediction under distribution shift. Several papers extend conformal prediction to settings where the test distribution differs from the calibration distribution. Tibshirani et al. [33 ] handle covariate shift via importance-weighted scores. Barber et al. [2 ] derive coverage bounds for general non-exchangeable data. Gibbs and Candès [8 , 9 ] give procedures that maintain coverage under arbitrary temporal drift. Oliveira et al. [26 ] study split conformal guarantees when data is not exchangeable. None of
these papers model the performative case, where deployment itself alters the future data-generating process.
The closest papers on the conformal side are Fannjiang et al. [7 ] and Binny and Dixit [3 ] . Fannjiang et al. study a biomolecular design setting in which deploying a model changes which candidate molecules are proposed in the next round. However, their analysis handles only covariate shift: the marginal distribution over inputs changes, but the conditional distribution of outcomes given inputs does not. In a performative system, predictions affect behavior, which changes outcomes, so the full joint distribution shifts. Moreover, their analysis does not address the equilibrium that emerges after repeated retraining. Binny and Dixit apply a similar iterative conformal idea to multi-agent motion planning, where deploying an uncertainty-aware controller changes how surrounding agents behave. Their focus is on safe trajectory prediction rather than performative equilibrium in the statistical learning sense, and they do not analyze sample complexity. Our work is the first to study conformal validity at the equilibrium distribution D ( f ⋆ ) D(f^{\star}) D ( f ⋆ )
Uncertainty quantification under performativity. Three recent papers study uncertainty quantification in performative settings, and we differ from each in a distinct way.
Li et al. [21 ] introduce Performative Risk Control (PRC), which calibrates a scalar threshold so that a chosen risk measure stays controlled throughout the retraining process. Their guarantee is that E [ ℓ ( z ; λ ) ] ≤ α \mathbb{E}[\ell(z; \lambda)] \leq\alpha E [ ℓ ( z ; λ )] ≤ α 1 − α 1-\alpha 1 − α
Csillag et al. [5 ] construct prediction sets that are valid against the worst-case strategic response of the population. Because they do not assume anything about which equilibrium will emerge, their sets must be wide enough to cover all possible outcomes under any plausible response, and may be unnecessarily wide when the actual equilibrium is less extreme than the worst case. We instead target the specific equilibrium D ( f ⋆ ) D(f^{\star}) D ( f ⋆ ) L < 1 L < 1 L < 1 Theorem 3.1 delineates where each applies: when L < 1 L < 1 L < 1 Θ ~ ( 1 / ( 1 − L ) 2 ) \widetilde{\Theta}(1/(1-L)^2) Θ ( 1/ ( 1 − L ) 2 ) L ≥ 1 L \geq1 L ≥ 1
Perdomo [28 ] shows that performative multicalibration — simultaneously matching predicted probabilities to observed outcome frequencies across a large collection of subgroups — is always achievable under performative feedback, without any Lipschitz condition on D ( ⋅ ) D(\cdot) D ( ⋅ ) L ≥ 1 L \ge1 L ≥ 1 C ( x ) C(x) C ( x ) 1 − α 1-\alpha 1 − α L ≥ 1 L \ge1 L ≥ 1
No prior work establishes the feasibility threshold for equilibrium-valid coverage, derives the minimax sample complexity below that threshold, proves a transfer theorem that converts proximity to equilibrium directly into a coverage guarantee, or provides algorithms that match the optimal rate. These are the four contributions of the present paper.
Discussion and Conclusion
Our results establish a sharp phase transition at L = 1 L = 1 L = 1 L ≥ 1 L \ge1 L ≥ 1 Θ ( 1 / ( 1 − L ) 2 ) \Theta(1/(1-L)^2) Θ ( 1/ ( 1 − L ) 2 ) L < 1 L < 1 L < 1
Practical implications. Our results suggest a workflow for uncertainty quantification under performativity. Before deployment in an environment where predictions affect outcomes, estimate the sensitivity L L L L ≥ 1 L \ge1 L ≥ 1 L L L L < 1 L < 1 L < 1 1 / ( 1 − L ) 2 1/(1-L)^2 1/ ( 1 − L ) 2 1 / ( 1 − L ) 3 1/(1-L)^3 1/ ( 1 − L ) 3
Limitations. Our analysis has several limitations. First, the coverage guarantees hold on average at equilibrium across the whole population, rather than separately for each feature value or subgroup. Second, the sharp parametric upper bound requires smoothness and strong convexity, while the more general model-free result pays an additional ( 1 − L ) − 1 / 2 (1-L)^{-1/2} ( 1 − L ) − 1/2 L L L
Extensions. Our minimax characterization also points to natural next directions. The model-free algorithm (Theorem 4.1 ) shows that L < 1 L < 1 L < 1 ρ = L β / γ < 1 \rho= L\beta/\gamma< 1 ρ = L β / γ < 1 L < 1 L < 1 L < 1 Theorem 2.8 ) is useful precisely because it decouples this optimization question from calibration: any future method with a convergence guarantee to equilibrium immediately inherits a coverage guarantee through the theorem.
Reproducibility. The synthetic and semi-synthetic experiments rely only on the models and parameter grids described in § 5 and Appendix S2. The semi-synthetic study uses the publicly available “Give Me Some Credit” dataset [15 ] . Code and simulation scripts to reproduce all figures will be made publicly available upon acceptance.
Proof of Theorem 3.1
It suffices to prove the theorem for L = 1 L = 1 L = 1
TV ( D ( f ) , D ( g ) ) ≤ d F ( f , g ) for all f , g ∈ F , \operatorname{TV}(D(f), D(g)) \le d_{\mathcal{F}}(f,g) \quad\text{for all } f,g \in\mathcal{F}, TV ( D ( f ) , D ( g )) ≤ d F ( f , g ) for all f , g ∈ F , then automatically
TV ( D ( f ) , D ( g ) ) ≤ L d F ( f , g ) for all f , g ∈ F \operatorname{TV}(D(f), D(g)) \le Ld_{\mathcal{F}}(f,g) \quad\text{for all } f,g \in\mathcal{F} TV ( D ( f ) , D ( g )) ≤ L d F ( f , g ) for all f , g ∈ F for every L ≥ 1 L \ge1 L ≥ 1 L ≥ 1 L \ge1 L ≥ 1
A Binary Hard Instance for Theorem 3.1
Proof. Take X = { x 0 } \mathcal{X} = \{x_0\} X = { x 0 } Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } Θ = [ 0 , 1 ] \Theta= [0,1] Θ = [ 0 , 1 ] ℓ ( θ , y ) = ( θ − y ) 2 \ell(\theta,y) = (\theta-y)^2 ℓ ( θ , y ) = ( θ − y ) 2 ϵ > 0 \epsilon> 0 ϵ > 0 n n n
D + ( θ ) : Y ∼ Bern ( g + ( θ ) ) , g + ( θ ) = min ( θ + ϵ , 1 − ϵ ) , D_+(\theta): Y \sim\operatorname{Bern}(g_+(\theta)), \qquad g_+(\theta) = \min(\theta+\epsilon,1-\epsilon), D + ( θ ) : Y ∼ Bern ( g + ( θ )) , g + ( θ ) = min ( θ + ϵ , 1 − ϵ ) , D − ( θ ) : Y ∼ Bern ( g − ( θ ) ) , g − ( θ ) = max ( θ − ϵ , ϵ ) . D_-(\theta): Y \sim\operatorname{Bern}(g_-(\theta)), \qquad g_-(\theta) = \max(\theta-\epsilon,\epsilon). D − ( θ ) : Y ∼ Bern ( g − ( θ )) , g − ( θ ) = max ( θ − ϵ , ϵ ) . Step 1: Both maps are 1-sensitive. We first show that g + g_+ g + g − g_- g −
g + ( θ ) = c ( θ + ϵ ) , c ( u ) = min ( u , 1 − ϵ ) . g_+(\theta) = c(\theta+\epsilon), \qquad c(u) = \min(u,1-\epsilon). g + ( θ ) = c ( θ + ϵ ) , c ( u ) = min ( u , 1 − ϵ ) . The map θ ↦ θ + ϵ \theta\mapsto\theta+\epsilon θ ↦ θ + ϵ
∣ ( θ + ϵ ) − ( θ ′ + ϵ ) ∣ = ∣ θ − θ ′ ∣ . \lvert(\theta+\epsilon)-(\theta'+\epsilon)\rvert= \lvert\theta-\theta'\rvert. ∣( θ + ϵ ) − ( θ ′ + ϵ )∣ = ∣ θ − θ ′ ∣ . The clipping map c c c
∣ c ( u ) − c ( v ) ∣ ≤ ∣ u − v ∣ for all u , v ∈ R . \lvert c(u)-c(v)\rvert\le\lvert u-v\rvert\quad\text{for all } u,v \in\mathbb{R}. ∣ c ( u ) − c ( v )∣ ≤ ∣ u − v ∣ for all u , v ∈ R . Hence g + g_+ g +
g − ( θ ) = max ( θ − ϵ , ϵ ) , g_-(\theta) = \max(\theta-\epsilon,\epsilon), g − ( θ ) = max ( θ − ϵ , ϵ ) , so g − g_- g −
For Bernoulli distributions, total variation distance is the absolute difference of the success probabilities. Therefore
TV ( D ± ( θ ) , D ± ( θ ′ ) ) = ∣ g ± ( θ ) − g ± ( θ ′ ) ∣ ≤ ∣ θ − θ ′ ∣ . \operatorname{TV}(D_{\pm}(\theta),D_{\pm}(\theta')) = \lvert g_{\pm}(\theta)-g_{\pm}(\theta')\rvert\le\lvert\theta-\theta'\rvert. TV ( D ± ( θ ) , D ± ( θ ′ )) = ∣ g ± ( θ ) − g ± ( θ ′ )∣ ≤ ∣ θ − θ ′ ∣ . Hence both distribution maps are 1-sensitive.
The clipping ensures that the Bernoulli parameter remains in [ ϵ , 1 − ϵ ] [\epsilon,1-\epsilon] [ ϵ , 1 − ϵ ] [ 0 , 1 ] [0,1] [ 0 , 1 ]
Step 2: Both maps admit performatively stable predictors. Under squared loss, the risk minimizer under a Bernoulli distribution with mean p p p θ = p \theta= p θ = p
θ ⋆ = E [ Y ∣ Y ∼ D ( θ ⋆ ) ] = g ( θ ⋆ ) . \theta^\star= \mathbb{E}[Y \mid Y \sim D(\theta^\star)] = g(\theta^\star). θ ⋆ = E [ Y ∣ Y ∼ D ( θ ⋆ )] = g ( θ ⋆ ) . For D + D_{+} D +
θ = min ( θ + ϵ , 1 − ϵ ) . \theta= \min(\theta+ \epsilon, 1 - \epsilon). θ = min ( θ + ϵ , 1 − ϵ ) . Because ϵ > 0 \epsilon> 0 ϵ > 0 θ = θ + ϵ \theta= \theta+ \epsilon θ = θ + ϵ
θ + ⋆ = 1 − ϵ . \theta_{+}^{\star} = 1 - \epsilon. θ + ⋆ = 1 − ϵ . At θ = 1 − ϵ \theta= 1 - \epsilon θ = 1 − ϵ
g + ( 1 − ϵ ) = min ( 1 , 1 − ϵ ) = 1 − ϵ , g_{+}(1 - \epsilon) = \min(1, 1 - \epsilon) = 1 - \epsilon, g + ( 1 − ϵ ) = min ( 1 , 1 − ϵ ) = 1 − ϵ , so 1 − ϵ 1 - \epsilon 1 − ϵ
For D − D_{-} D −
θ = max ( θ − ϵ , ϵ ) , \theta= \max(\theta- \epsilon, \epsilon), θ = max ( θ − ϵ , ϵ ) , and similarly the only solution is
θ − ⋆ = ϵ , \theta_{-}^{\star} = \epsilon, θ − ⋆ = ϵ , since
g − ( ϵ ) = max ( 0 , ϵ ) = ϵ . g_{-}(\epsilon) = \max(0, \epsilon) = \epsilon. g − ( ϵ ) = max ( 0 , ϵ ) = ϵ . Thus the equilibrium distributions are
D + ( θ + ⋆ ) = Bern ( 1 − ϵ ) , D − ( θ − ⋆ ) = Bern ( ϵ ) . D_{+}(\theta_{+}^{\star}) = \operatorname{Bern}(1 - \epsilon), \qquad D_{-}(\theta_{-}^{\star}) = \operatorname{Bern}(\epsilon). D + ( θ + ⋆ ) = Bern ( 1 − ϵ ) , D − ( θ − ⋆ ) = Bern ( ϵ ) . Step 3: The two environments are hard to distinguish. For every deployment θ ∈ [ 0 , 1 ] \theta\in[0,1] θ ∈ [ 0 , 1 ] 2 ϵ 2\epsilon 2 ϵ [ 2 ϵ , 1 − 2 ϵ ] [2\epsilon, 1 - 2\epsilon] [ 2 ϵ , 1 − 2 ϵ ]
g + ( θ ) = θ + ϵ , g − ( θ ) = θ − ϵ , g_{+}(\theta) = \theta+ \epsilon, \qquad g_{-}(\theta) = \theta- \epsilon, g + ( θ ) = θ + ϵ , g − ( θ ) = θ − ϵ , and therefore
∣ g + ( θ ) − g − ( θ ) ∣ = 2 ϵ . \lvert g_{+}(\theta) - g_{-}(\theta) \rvert= 2\epsilon. ∣ g + ( θ ) − g − ( θ )∣ = 2 ϵ . If θ ∉ [ 2 ϵ , 1 − 2 ϵ ] \theta\notin[2\epsilon, 1 - 2\epsilon] θ ∈ / [ 2 ϵ , 1 − 2 ϵ ] θ − ϵ < ϵ \theta- \epsilon< \epsilon θ − ϵ < ϵ θ + ϵ > 1 − ϵ \theta+ \epsilon> 1 - \epsilon θ + ϵ > 1 − ϵ θ ∈ [ 0 , 1 ] \theta\in[0,1] θ ∈ [ 0 , 1 ]
∣ g + ( θ ) − g − ( θ ) ∣ ≤ 2 ϵ . \lvert g_{+}(\theta) - g_{-}(\theta) \rvert\leq2\epsilon. ∣ g + ( θ ) − g − ( θ )∣ ≤ 2 ϵ . Moreover, both parameters lie in [ ϵ , 1 − ϵ ] [\epsilon, 1 - \epsilon] [ ϵ , 1 − ϵ ]
KL ( D + ( θ ) ∥ D − ( θ ) ) ≤ ( g + ( θ ) − g − ( θ ) ) 2 g − ( θ ) ( 1 − g − ( θ ) ) ≤ ( 2 ϵ ) 2 ϵ ( 1 − ϵ ) = 4 ϵ 1 − ϵ . \operatorname{KL}(D_{+}(\theta) \mathbin{\|} D_{-}(\theta)) \leq\frac{(g_{+}(\theta) - g_{-}(\theta))^{2}}{g_{-}(\theta)(1 - g_{-}(\theta))} \leq\frac{(2\epsilon)^{2}}{\epsilon(1 - \epsilon)} = \frac{4\epsilon}{1 - \epsilon}. KL ( D + ( θ ) ∥ D − ( θ )) ≤ g − ( θ ) ( 1 − g − ( θ )) ( g + ( θ ) − g − ( θ ) ) 2 ≤ ϵ ( 1 − ϵ ) ( 2 ϵ ) 2 = 1 − ϵ 4 ϵ . Now consider any adaptive algorithm that deploys predictors θ 1 , … , θ T \theta_{1}, \ldots, \theta_{T} θ 1 , … , θ T n t n_{t} n t t t t ∑ t = 1 T n t = n \sum_{t=1}^{T} n_{t} = n ∑ t = 1 T n t = n
KL ( P + ( n ) ∥ P − ( n ) ) = ∑ t = 1 T n t E + [ KL ( D + ( θ t ) ∥ D − ( θ t ) ) ] ≤ 4 n ϵ 1 − ϵ . \operatorname{KL}(\mathbb{P}_{+}^{(n)} \mathbin{\|} \mathbb{P}_{-}^{(n)}) = \sum_{t=1}^{T} n_{t} \mathbb{E}_{+}\left[\operatorname{KL}(D_{+}(\theta_{t}) \mathbin{\|} D_{-}(\theta_{t}))\right] \leq\frac{4n\epsilon}{1 - \epsilon}. KL ( P + ( n ) ∥ P − ( n ) ) = t = 1 ∑ T n t E + [ KL ( D + ( θ t ) ∥ D − ( θ t )) ] ≤ 1 − ϵ 4 n ϵ . Choosing
ϵ = c 0 n (2) \epsilon= \frac{c_{0}}{n} \tag*{(2)} ϵ = n c 0 (2) for some constant c 0 > 0 c_0 > 0 c 0 > 0 D + D_+ D + D − D_- D −
Step 4: The nontrivial valid sets are incompatible. Because X \mathcal{X} X Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 }
∅ , { 0 } , { 1 } , Y . \varnothing,\quad\{0\},\quad\{1\},\quad\mathcal{Y}. ∅ , { 0 } , { 1 } , Y . The empty set is never valid, and Y \mathcal{Y} Y { 0 } \{0\} { 0 } { 1 } \{1\} { 1 }
Their equilibrium coverages are:
Table 3.
If
ϵ < min ( α , 1 − α ) , \epsilon< \min(\alpha, 1-\alpha), ϵ < min ( α , 1 − α ) , then under D + D_+ D + 1 − α 1-\alpha 1 − α { 1 } \{1\} { 1 } D − D_- D − 1 − α 1-\alpha 1 − α { 0 } \{0\} { 0 }
Therefore any algorithm that uniformly guaranteed both equilibrium-valid coverage and nontriviality would, from its output, implicitly identify which environment is active: output { 1 } \{1\} { 1 } D + D_+ D + { 0 } \{0\} { 0 } D − D_- D −
Hence, for L = 1 L = 1 L = 1
Every 1-sensitive map is also L L L L ≥ 1 L \ge1 L ≥ 1 L ≥ 1 L \ge1 L ≥ 1
Extension to general spaces
Lemma A.1 (Reduction to the binary instance). Assume X ≠ ∅ \mathcal{X} \ne\varnothing X = ∅ ∣ Y ∣ ≥ 2 |\mathcal{Y}| \ge2 ∣ Y ∣ ≥ 2 Pick any x 0 ∈ X x_0 \in\mathcal{X} x 0 ∈ X y 0 , y 1 ∈ Y y_0, y_1 \in\mathcal{Y} y 0 , y 1 ∈ Y Consider the binary hard instance from the proof above, and view it as a distribution on ( X , Y ) (\mathcal{X}, \mathcal{Y}) ( X , Y ) x 0 x_0 x 0 { y 0 , y 1 } \{y_0,y_1\} { y 0 , y 1 } 0 0 0 y 0 y_0 y 0 1 1 1 y 1 y_1 y 1
Proof. The larger spaces X \mathcal{X} X Y \mathcal{Y} Y x 0 x_0 x 0 y 0 , y 1 y_0, y_1 y 0 , y 1
Therefore the embedded instance is the same as the binary one, just with relabeled outcomes. The total variation distances are the same, the fixed-point equations are the same, and the coverage of any prediction set depends only on whether it contains y 0 y_0 y 0 y 1 y_1 y 1 x 0 x_0 x 0
Full Lower Bound Proof (Theorem 3.2, Lower Bound)
We prove the lower bound by constructing two performative environments that are statistically hard to distinguish but for which a single informative prediction set is valid at one equilibrium and strictly invalid at the other.
Construction
Take X = { x 0 } \mathcal{X} = \{x_0\} X = { x 0 } Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } θ ∈ [ 0 , 1 ] \theta\in[0,1] θ ∈ [ 0 , 1 ] ℓ ( θ , y ) = ( θ − y ) 2 \ell(\theta,y) = (\theta-y)^2 ℓ ( θ , y ) = ( θ − y ) 2 L < 1 L < 1 L < 1 L L L
D 0 ( θ ) : Y ∼ Bern ( a + L θ ) , D_0(\theta): \quad Y \sim\operatorname{Bern}(a + L\theta), D 0 ( θ ) : Y ∼ Bern ( a + L θ ) , D 1 ( θ ) : Y ∼ Bern ( a + δ + L θ ) . D_1(\theta): \quad Y \sim\operatorname{Bern}(a + \delta+ L\theta). D 1 ( θ ) : Y ∼ Bern ( a + δ + L θ ) . where a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) δ > 0 \delta> 0 δ > 0 a + δ + L < 1 a + \delta+ L < 1 a + δ + L < 1 ( 0 , 1 ) (0,1) ( 0 , 1 )
This construction changes the performative map only by a constant shift δ \delta δ L L L
For Bernoulli outcomes under squared loss, the population risk minimizer is the Bernoulli mean. Therefore the equilibrium points satisfy
θ 0 ⋆ = a + L θ 0 ⋆ , θ 1 ⋆ = a + δ + L θ 1 ⋆ . \theta_0^\star= a + L\theta_0^\star, \qquad\theta_1^\star= a + \delta+ L\theta_1^\star. θ 0 ⋆ = a + L θ 0 ⋆ , θ 1 ⋆ = a + δ + L θ 1 ⋆ . hence
θ 0 ⋆ = a 1 − L , θ 1 ⋆ = a + δ 1 − L . \theta_0^\star= \frac{a}{1-L}, \qquad\theta_1^\star= \frac{a+\delta}{1-L}. θ 0 ⋆ = 1 − L a , θ 1 ⋆ = 1 − L a + δ . Since under squared loss the population minimizer equals the Bernoulli mean, the equilibrium Bernoulli parameters are
p 0 ⋆ = a 1 − L , p 1 ⋆ = a + δ 1 − L . p_0^\star= \frac{a}{1-L}, \qquad p_1^\star= \frac{a+\delta}{1-L}. p 0 ⋆ = 1 − L a , p 1 ⋆ = 1 − L a + δ . so the equilibrium gap is
∣ p 1 ⋆ − p 0 ⋆ ∣ = δ 1 − L . \lvert p_1^\star- p_0^\star\rvert= \frac{\delta}{1-L}. ∣ p 1 ⋆ − p 0 ⋆ ∣ = 1 − L δ . This is the amplification effect used in the lower bound: a local perturbation of size δ \delta δ 1 / ( 1 − L ) 1/(1-L) 1/ ( 1 − L )
Sequential KL divergence
An algorithm may deploy predictors adaptively. At round t t t θ t \theta_t θ t n t n_t n t D 0 ( θ t ) D_0(\theta_t) D 0 ( θ t ) D 1 ( θ t ) D_1(\theta_t) D 1 ( θ t ) ∑ t n t = n \sum_t n_t = n ∑ t n t = n
For every deployment θ \theta θ
p 1 ( θ ) − p 0 ( θ ) = δ , p_1(\theta) - p_0(\theta) = \delta, p 1 ( θ ) − p 0 ( θ ) = δ , since p 1 ( θ ) = a + δ + L θ p_1(\theta) = a+\delta+L\theta p 1 ( θ ) = a + δ + L θ p 0 ( θ ) = a + L θ p_0(\theta) = a+L\theta p 0 ( θ ) = a + L θ a a a a + δ + L < 1 a+\delta+L<1 a + δ + L < 1 p 0 ( θ ) p_0(\theta) p 0 ( θ ) p 1 ( θ ) p_1(\theta) p 1 ( θ ) [ η , 1 − η ] ⊂ ( 0 , 1 ) [\eta,1-\eta]\subset(0,1) [ η , 1 − η ] ⊂ ( 0 , 1 ) θ \theta θ
For Bernoulli distributions,
KL ( Bern ( p ) ∥ Bern ( q ) ) ≤ ( p − q ) 2 q ( 1 − q ) . \operatorname{KL}(\operatorname{Bern}(p)\mathbin\Vert\operatorname{Bern}(q))\le\frac{(p-q)^2}{q(1-q)}. KL ( Bern ( p ) ∥ Bern ( q )) ≤ q ( 1 − q ) ( p − q ) 2 . Since p 0 ( θ ) , p 1 ( θ ) ∈ [ η , 1 − η ] p_0(\theta),p_1(\theta)\in[\eta,1-\eta] p 0 ( θ ) , p 1 ( θ ) ∈ [ η , 1 − η ] θ \theta θ
KL ( Bern ( p 0 ( θ ) ) ∥ Bern ( p 1 ( θ ) ) ) ≤ δ 2 η ( 1 − η ) = : C a δ 2 . \operatorname{KL}(\operatorname{Bern}(p_0(\theta))\mathbin\Vert\operatorname{Bern}(p_1(\theta)))\le\frac{\delta^2}{\eta(1-\eta)}=:C_a\delta^2. KL ( Bern ( p 0 ( θ )) ∥ Bern ( p 1 ( θ ))) ≤ η ( 1 − η ) δ 2 =: C a δ 2 . Now condition on the history up to round t − 1 t-1 t − 1 θ t \theta_t θ t n t n_t n t t t t Bern ( p 0 ( θ t ) ) \operatorname{Bern}(p_0(\theta_t)) Bern ( p 0 ( θ t )) Bern ( p 1 ( θ t ) ) \operatorname{Bern}(p_1(\theta_t)) Bern ( p 1 ( θ t )) t t t
n t KL ( Bern ( p 0 ( θ t ) ) ∥ Bern ( p 1 ( θ t ) ) ) . n_t\operatorname{KL}(\operatorname{Bern}(p_0(\theta_t))\mathbin\Vert\operatorname{Bern}(p_1(\theta_t))). n t KL ( Bern ( p 0 ( θ t )) ∥ Bern ( p 1 ( θ t ))) . Applying the chain rule for KL divergence and then taking expectation over the history gives
KL ( P 0 ( n ) ∥ P 1 ( n ) ) = ∑ t = 1 T n t E 0 [ KL ( Bern ( p 0 ( θ t ) ) ∥ Bern ( p 1 ( θ t ) ) ) ] ≤ C a ∑ t = 1 T n t δ 2 = C a n δ 2 . \operatorname{KL}(\mathbb{P}_0^{(n)}\mathbin\Vert\mathbb{P}_1^{(n)})=\sum_{t=1}^{T}n_t\mathbb{E}_0\left[\operatorname{KL}(\operatorname{Bern}(p_0(\theta_t))\mathbin\Vert\operatorname{Bern}(p_1(\theta_t)))\right]\le C_a\sum_{t=1}^{T}n_t\delta^2=C_an\delta^2. KL ( P 0 ( n ) ∥ P 1 ( n ) ) = t = 1 ∑ T n t E 0 [ KL ( Bern ( p 0 ( θ t )) ∥ Bern ( p 1 ( θ t ))) ] ≤ C a t = 1 ∑ T n t δ 2 = C a n δ 2 . Therefore adaptivity does not help: no matter how the algorithm chooses its deployments, the total information available for distinguishing the two environments is at most of order n δ 2 n\delta^2 n δ 2
From equilibrium separation to excess miscoverage
We now explain why this equilibrium gap forces a lower bound on excess miscoverage.
Because X \mathcal{X} X Y = { 0 , 1 } \mathcal{Y}=\{0,1\} Y = { 0 , 1 }
∅ , { 0 } , { 1 } , { 0 , 1 } . \varnothing,\qquad\{0\},\qquad\{1\},\qquad\{0,1\}. ∅ , { 0 } , { 1 } , { 0 , 1 } . The empty set is always invalid and { 0 , 1 } \{0,1\} { 0 , 1 } { 0 } \{0\} { 0 } { 1 } \{1\} { 1 } X \mathcal{X} X Inf ∈ { 0 , 1 } \operatorname{Inf}\in\{0,1\} Inf ∈ { 0 , 1 } A τ A_\tau A τ τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] { 0 , 1 } \{0,1\} { 0 , 1 } { 0 } \{0\} { 0 } { 1 } \{1\} { 1 }
Under environment i ∈ { 0 , 1 } i\in\{0,1\} i ∈ { 0 , 1 } Bern ( p i ⋆ ) \operatorname{Bern}(p_i^\star) Bern ( p i ⋆ )
P i ( Y ∉ { 1 } ) = 1 − p i ⋆ , P i ( Y ∉ { 0 } ) = p i ⋆ . \mathbb{P}_i(Y\notin\{1\})=1-p_i^\star,\qquad\mathbb{P}_i(Y\notin\{0\})=p_i^\star. P i ( Y ∈ / { 1 }) = 1 − p i ⋆ , P i ( Y ∈ / { 0 }) = p i ⋆ . So the excess miscoverage of the two nontrivial sets is determined directly by the equilibrium Bernoulli parameter p i ⋆ p_i^\star p i ⋆
To make the informative set { 1 } \{1\} { 1 } α \alpha α a a a 1 − α 1-\alpha 1 − α
p 0 ⋆ = 1 − α − Δ 2 , p 1 ⋆ = 1 − α + Δ 2 . p_0^\star=1-\alpha-\frac{\Delta}{2},\qquad p_1^\star=1-\alpha+\frac{\Delta}{2}. p 0 ⋆ = 1 − α − 2 Δ , p 1 ⋆ = 1 − α + 2 Δ . where
Δ = δ 1 − L . \Delta= \frac{\delta}{1-L}. Δ = 1 − L δ . This can be achieved by choosing
a = ( 1 − L ) ( 1 − α − Δ 2 ) . a=(1-L)\left(1-\alpha-\frac{\Delta}{2}\right). a = ( 1 − L ) ( 1 − α − 2 Δ ) . Under D 0 D_0 D 0 { 1 } \{1\} { 1 }
1 − p 0 ∗ = α + Δ 2 , 1-p_0^*=\alpha+\frac{\Delta}{2}, 1 − p 0 ∗ = α + 2 Δ , so its excess miscoverage is Δ / 2 \Delta/2 Δ/2 D 1 D_1 D 1 { 1 } \{1\} { 1 }
1 − p 1 ∗ = α − Δ 2 , 1-p_1^*=\alpha-\frac{\Delta}{2}, 1 − p 1 ∗ = α − 2 Δ , so its excess miscoverage is 0. Because the two equilibrium means p 0 ∗ , p 1 ∗ p_0^*,p_1^* p 0 ∗ , p 1 ∗ 1 − α 1-\alpha 1 − α { 1 } \{1\} { 1 } valid under D 1 D_1 D 1 strictly invalid under D 0 D_0 D 0 Δ / 2 \Delta/2 Δ/2 { 0 } \{0\} { 0 } p i ∗ p_i^* p i ∗ 1 − α ∓ Δ / 2 1-\alpha\mp\Delta/2 1 − α ∓ Δ/2 1 − 2 α 1-2\alpha 1 − 2 α D 0 D_0 D 0 { 1 } \{1\} { 1 } Δ / 2 \Delta/2 Δ/2
Therefore the same informative set { 1 } \{1\} { 1 } τ \tau τ { 1 } \{1\} { 1 } Δ \Delta Δ D 0 D_0 D 0 A τ \mathcal{A}_{\tau} A τ
Completing the lower bound
The two equilibria straddle the validity boundary of the informative set { 1 } \{1\} { 1 } D 0 D_0 D 0 Δ / 2 \Delta/2 Δ/2 { 1 } \{1\} { 1 } D 1 D_1 D 1 { 1 } \{1\} { 1 } τ \tau τ Δ / 2 \Delta/2 Δ/2
Le Cam’s two-point lemma now applies. Since the KL divergence between the two induced data-generating processes is at most C a n δ 2 C_a n\delta^2 C a n δ 2
inf ϕ ( P 0 ( ϕ = 1 ) + P 1 ( ϕ = 0 ) ) ≥ 1 − 1 2 C a n δ 2 . \inf_{\phi}\left(\mathbb{P}_0(\phi=1)+\mathbb{P}_1(\phi=0)\right)\ge1-\sqrt{\frac{1}{2}C_a n\delta^2}. ϕ inf ( P 0 ( ϕ = 1 ) + P 1 ( ϕ = 0 ) ) ≥ 1 − 2 1 C a n δ 2 . Hence, at least one of the two testing errors is at least
1 2 ( 1 − 1 2 C a n δ 2 ) . \frac{1}{2}\left(1-\sqrt{\frac{1}{2}C_a n\delta^2}\right). 2 1 ( 1 − 2 1 C a n δ 2 ) . Combining this with the loss separation Δ / 2 \Delta/2 Δ/2
max i ∈ { 0 , 1 } ExMisc ( C f ^ , D i ( f ∗ ) ) ≥ Δ 4 ( 1 − 1 2 C a n δ 2 ) . \max_{i\in\{0,1\}}\operatorname{ExMisc}(\mathcal{C}_{\hat f},D_i(f^*))\ge\frac{\Delta}{4}\left(1-\sqrt{\frac{1}{2}C_a n\delta^2}\right). i ∈ { 0 , 1 } max ExMisc ( C f ^ , D i ( f ∗ )) ≥ 4 Δ ( 1 − 2 1 C a n δ 2 ) . Set
δ = c ′ n \delta= \frac{c'}{\sqrt{n}} δ = n c ′ with c ′ > 0 c' > 0 c ′ > 0
Δ = δ 1 − L = c ′ ( 1 − L ) n , \Delta= \frac{\delta}{1-L} = \frac{c'}{(1-L)\sqrt{n}}, Δ = 1 − L δ = ( 1 − L ) n c ′ , and therefore
max i ∈ { 0 , 1 } ExMisc ( C f ^ , D i ( f ⋆ ) ) ≥ Ω ( 1 ( 1 − L ) n ) . \max_{i\in\{0,1\}} \operatorname{ExMisc}(C_{\hat f},D_i(f^\star)) \ge\Omega\left(\frac{1}{(1-L)\sqrt{n}}\right). i ∈ { 0 , 1 } max ExMisc ( C f ^ , D i ( f ⋆ )) ≥ Ω ( ( 1 − L ) n 1 ) . This proves the lower bound in Theorem 3.2 .
Full Upper Bound Proof
Proof of Coverage Decomposition (Lemma 2.7)
Proof. Define score CDFs:
F h ( q ) = P ( X , Y ) ∼ D ( h ) ( s ( X , Y ; h ) ≤ q ) , F_h(q) = \mathbb{P}_{(X,Y)\sim D(h)}(s(X,Y;h) \le q), F h ( q ) = P ( X , Y ) ∼ D ( h ) ( s ( X , Y ; h ) ≤ q ) , G g ( q ) = P ( X , Y ) ∼ D ( g ) ( s ( X , Y ; h ) ≤ q ) . G_g(q) = \mathbb{P}_{(X,Y)\sim D(g)}(s(X,Y;h) \le q). G g ( q ) = P ( X , Y ) ∼ D ( g ) ( s ( X , Y ; h ) ≤ q ) . Step 1: Conformal guarantee under the calibration distribution. Conditional on h h h s 1 , … , s m s_1,\ldots,s_m s 1 , … , s m G g G_g G g s m + 1 s_{m+1} s m + 1 s 1 , … , s m s_1,\ldots,s_m s 1 , … , s m s m + 1 s_{m+1} s m + 1 s 1 , … , s m + 1 s_1,\ldots,s_{m+1} s 1 , … , s m + 1 { 1 , … , m + 1 } \{1,\ldots,m+1\} { 1 , … , m + 1 } 1 / ( m + 1 ) 1/(m+1) 1/ ( m + 1 )
P ( s m + 1 ≤ q ^ ) ≥ ⌈ ( 1 − α ) ( m + 1 ) ⌉ m + 1 ≥ 1 − α . \mathbb{P}(s_{m+1} \le\hat q) \ge\frac{\lceil(1-\alpha)(m+1)\rceil}{m+1} \ge1-\alpha. P ( s m + 1 ≤ q ^ ) ≥ m + 1 ⌈( 1 − α ) ( m + 1 )⌉ ≥ 1 − α . So E S [ G g ( q ^ ) ] ≥ 1 − α \mathbb{E}_S[G_g(\hat q)] \ge1-\alpha E S [ G g ( q ^ )] ≥ 1 − α
Step 2 (Transfer to the target distribution). For any measurable event A A A ∣ P ( A ) − Q ( A ) ∣ ≤ TV ( P , Q ) |P(A)-Q(A)| \le\operatorname{TV}(P,Q) ∣ P ( A ) − Q ( A ) ∣ ≤ TV ( P , Q ) A = { ( x , y ) : s ( x , y ; h ) ≤ q } A = \{(x,y):s(x,y;h) \le q\} A = {( x , y ) : s ( x , y ; h ) ≤ q }
∣ F h ( q ) − G g ( q ) ∣ ≤ TV ( D ( h ) , D ( g ) ) ∀ q . |F_h(q)-G_g(q)| \le\operatorname{TV}(D(h),D(g)) \quad\forall q. ∣ F h ( q ) − G g ( q ) ∣ ≤ TV ( D ( h ) , D ( g )) ∀ q . This holds for the random threshold q ^ \hat q q ^ F h ( q ^ ) ≥ G g ( q ^ ) − TV ( D ( h ) , D ( g ) ) F_h(\hat q) \ge G_g(\hat q)-\operatorname{TV}(D(h),D(g)) F h ( q ^ ) ≥ G g ( q ^ ) − TV ( D ( h ) , D ( g ))
Step 3 (Combine).
E S [ F h ( q ^ ) ] ≥ E S [ G g ( q ^ ) ] − TV ( D ( h ) , D ( g ) ) ≥ ( 1 − α ) − TV ( D ( h ) , D ( g ) ) . \begin{aligned}
\mathbb{E}_S[F_h(\hat q)] \ge\mathbb{E}_S[G_g(\hat q)]-\operatorname{TV}(D(h),D(g)) \\
&\ge(1-\alpha)-\operatorname{TV}(D(h),D(g)).
\end{aligned} E S [ F h ( q ^ )] ≥ E S [ G g ( q ^ )] − TV ( D ( h ) , D ( g )) ≥ ( 1 − α ) − TV ( D ( h ) , D ( g )) . □
Proof of the Coverage Transfer Theorem (Theorem 2.8)
Proof. Apply Lemma 2.7 with h = g = f ^ h=g=\hat{f} h = g = f ^ m m m D ( f ^ ) D(\hat{f}) D ( f ^ ) ≥ 1 − α \ge1-\alpha ≥ 1 − α D ( f ^ ) D(\hat{f}) D ( f ^ )
Transfer to D ( f ⋆ ) D(f^\star) D ( f ⋆ ) A A A
∣ P D ( f ^ ) ( A ) − P D ( f ⋆ ) ( A ) ∣ ≤ TV ( D ( f ^ ) , D ( f ⋆ ) ) ≤ L ⋅ d F ( f ^ , f ⋆ ) = L ϵ . \left|\mathbb{P}_{D(\hat{f})}(A)-\mathbb{P}_{D(f^\star)}(A)\right| \le\operatorname{TV}(D(\hat{f}),D(f^\star)) \le L\cdot d_F(\hat{f},f^\star)=L\epsilon. P D ( f ^ ) ( A ) − P D ( f ⋆ ) ( A ) ≤ TV ( D ( f ^ ) , D ( f ⋆ )) ≤ L ⋅ d F ( f ^ , f ⋆ ) = L ϵ . Combining:
P D ( f ⋆ ) ( Y ∈ C f ^ ( X ) ) ≥ 1 − α − L ϵ . \mathbb{P}_{D(f^\star)}(Y\in C_{\hat{f}}(X)) \ge1-\alpha-L\epsilon. P D ( f ⋆ ) ( Y ∈ C f ^ ( X )) ≥ 1 − α − L ϵ . Equivalently,
ExMisc ‾ ( C f ^ , D ( f ⋆ ) ) ≤ L ϵ . \overline{\operatorname{ExMisc}}(C_{\hat{f}},D(f^\star))\le L\epsilon. ExMisc ( C f ^ , D ( f ⋆ )) ≤ L ϵ . Proof of Parametric Upper Bound (Theorem 4.4)
The argument rests on the following predictor-error bound for the tail-averaged iterate; its proof, a tail-averaging analysis of the retraining recursion, is given in the supplementary material (Appendix § 12 ).
Lemma C.1 (Predictor-error bound for P-PCP). Under the assumptions of Theorem 4.4, the tail-averaged predictor returned by Algorithm 2 satisfies
E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ~ ( 1 ( 1 − ρ ) 2 n ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)^2\right]\le\widetilde{O}\left(\frac{1}{(1-\rho)^2 n}\right). E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ( ( 1 − ρ ) 2 n 1 ) . Proof. The proof has two steps.
Step 1: Predictor error after stabilization and averaging. By Lemma C.1 , Algorithm 2 returns a predictor f ˉ B , K \bar{f}_{B,K} f ˉ B , K
E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ~ ( 1 ( 1 − ρ ) 2 n ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)^2\right]\le\widetilde{O}\left(\frac{1}{(1-\rho)^2 n}\right). E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ( ( 1 − ρ ) 2 n 1 ) . By Jensen’s inequality (since x ↦ x x\mapsto\sqrt{x} x ↦ x
E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ O ~ ( 1 ( 1 − ρ ) n ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)\right]\le\widetilde{O}\left(\frac{1}{(1-\rho)\sqrt{n}}\right). E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ O ( ( 1 − ρ ) n 1 ) . Step 2: Transfer to coverage. Apply Theorem 2.8 with ϵ = d F ( f ˉ B , K , f ⋆ ) \epsilon=d_F(\bar{f}_{B,K},f^\star) ϵ = d F ( f ˉ B , K , f ⋆ )
ExMisc ‾ ( C f ˉ B , K , D ( f ⋆ ) ) ≤ L ⋅ E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ O ~ ( L ( 1 − ρ ) n ) . \overline{\operatorname{ExMisc}}(C_{\bar{f}_{B,K}},D(f^\star))\le L\cdot\mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)\right]\le\widetilde{O}\left(\frac{L}{(1-\rho)\sqrt{n}}\right). ExMisc ( C f ˉ B , K , D ( f ⋆ )) ≤ L ⋅ E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ O ( ( 1 − ρ ) n L ) . Since L ≤ 1 L\le1 L ≤ 1
ExMisc ‾ ( C f ˉ B , K , D ( f ⋆ ) ) ≤ O ~ ( 1 ( 1 − ρ ) n ) . \overline{\operatorname{ExMisc}}(C_{\bar{f}_{B,K}},D(f^\star))\le\widetilde{O}\left(\frac{1}{(1-\rho)\sqrt{n}}\right). ExMisc ( C f ˉ B , K , D ( f ⋆ )) ≤ O ( ( 1 − ρ ) n 1 ) . When ρ ≲ L \rho\lesssim L ρ ≲ L β / γ ≈ 1 \beta/\gamma\approx1 β / γ ≈ 1
1 1 − ρ = Θ ( 1 1 − L ) , \frac{1}{1-\rho} = \Theta\left(\frac{1}{1-L}\right), 1 − ρ 1 = Θ ( 1 − L 1 ) , so the upper bound matches the n n n L L L
Proof of Model-Free Upper Bound (Theorem 4.1)
We prove the three components: the finite-class contraction argument, the iterated convergence, and the final coverage guarantee.
Finite-Class Contraction Argument
Proof. Let BR ( P ) = arg min f ∈ F E P [ ℓ ( f ( X ) , Y ) ] \operatorname{BR}(P) = \arg\min_{f \in\mathcal{F}} \mathbb{E}_{P}[\ell(f(X),Y)] BR ( P ) = arg min f ∈ F E P [ ℓ ( f ( X ) , Y )] P P P f ⋆ f^\star f ⋆ f ⋆ = BR ( D ( f ⋆ ) ) f^\star= \operatorname{BR}(D(f^\star)) f ⋆ = BR ( D ( f ⋆ ))
Step 1: ERM approximation. With m m m D ( f t ) D(f_t) D ( f t ) ℓ ∈ [ 0 , 1 ] \ell\in[0,1] ℓ ∈ [ 0 , 1 ] ∣ F ∣ = N |\mathcal{F}| = N ∣ F ∣ = N
sup f ∈ F ∣ R ^ ( f ; S t ) − R D ( f t ) ( f ) ∣ ≤ c 0 log N m . \sup_{f \in\mathcal{F}} \left|\widehat{R}(f;S_t)-R_{D(f_t)}(f)\right| \le c_0\sqrt{\frac{\log N}{m}}. f ∈ F sup R ( f ; S t ) − R D ( f t ) ( f ) ≤ c 0 m log N . with probability ≥ 1 − 1 / n 2 \ge1-1/n^2 ≥ 1 − 1/ n 2
R D ( f t ) ( f t + 1 ) ≤ R D ( f t ) ( BR ( D ( f t ) ) ) + 2 c 0 log N m . R_{D(f_t)}(f_{t+1}) \le R_{D(f_t)}(\operatorname{BR}(D(f_t))) + 2c_0\sqrt{\frac{\log N}{m}}. R D ( f t ) ( f t + 1 ) ≤ R D ( f t ) ( BR ( D ( f t ))) + 2 c 0 m log N . Step 2: Best-response stability. Define the sub-optimality gap
μ = min f ∈ F , f ≠ f ⋆ [ R D ( f ⋆ ) ( f ) − R D ( f ⋆ ) ( f ⋆ ) ] > 0 , \mu= \min_{f \in\mathcal{F},\,f\ne f^\star}\left[R_{D(f^\star)}(f)-R_{D(f^\star)}(f^\star)\right] > 0, μ = f ∈ F , f = f ⋆ min [ R D ( f ⋆ ) ( f ) − R D ( f ⋆ ) ( f ⋆ ) ] > 0 , which is strictly positive because F \mathcal{F} F f ⋆ f^\star f ⋆ D ( f ⋆ ) D(f^\star) D ( f ⋆ )
Claim: If TV ( D ( f t ) , D ( f ⋆ ) ) < μ / 2 \operatorname{TV}(D(f_t),D(f^\star)) < \mu/2 TV ( D ( f t ) , D ( f ⋆ )) < μ /2 BR ( D ( f t ) ) = f ⋆ \operatorname{BR}(D(f_t))=f^\star BR ( D ( f t )) = f ⋆
Proof of claim. For any f ≠ f ⋆ f\ne f^\star f = f ⋆
R D ( f t ) ( f ) − R D ( f t ) ( f ⋆ ) = [ R D ( f ⋆ ) ( f ) − R D ( f ⋆ ) ( f ⋆ ) ] + [ R D ( f t ) ( f ) − R D ( f ⋆ ) ( f ) ] − [ R D ( f t ) ( f ⋆ ) − R D ( f ⋆ ) ( f ⋆ ) ] . \begin{aligned}
R_{D(f_t)}(f)-R_{D(f_t)}(f^\star)
={}&\left[R_{D(f^\star)}(f)-R_{D(f^\star)}(f^\star)\right] \\
&+\left[R_{D(f_t)}(f)-R_{D(f^\star)}(f)\right]
-\left[R_{D(f_t)}(f^\star)-R_{D(f^\star)}(f^\star)\right].
\end{aligned} R D ( f t ) ( f ) − R D ( f t ) ( f ⋆ ) = [ R D ( f ⋆ ) ( f ) − R D ( f ⋆ ) ( f ⋆ ) ] + [ R D ( f t ) ( f ) − R D ( f ⋆ ) ( f ) ] − [ R D ( f t ) ( f ⋆ ) − R D ( f ⋆ ) ( f ⋆ ) ] . Since ℓ ∈ [ 0 , 1 ] \ell\in[0,1] ℓ ∈ [ 0 , 1 ] TV ( D ( f t ) , D ( f ⋆ ) ) \operatorname{TV}(D(f_t),D(f^\star)) TV ( D ( f t ) , D ( f ⋆ ))
R D ( f t ) ( f ) − R D ( f t ) ( f ⋆ ) ≥ μ − 2 TV ( D ( f t ) , D ( f ⋆ ) ) > 0 , R_{D(f_t)}(f)-R_{D(f_t)}(f^\star)\ge\mu-2\operatorname{TV}(D(f_t),D(f^\star))>0, R D ( f t ) ( f ) − R D ( f t ) ( f ⋆ ) ≥ μ − 2 TV ( D ( f t ) , D ( f ⋆ )) > 0 , so f ⋆ f^\star f ⋆ R D ( f t ) R_{D(f_t)} R D ( f t ) F \mathcal{F} F
By L L L TV ( D ( f t ) , D ( f ⋆ ) ) ≤ L ⋅ d F ( f t , f ⋆ ) \operatorname{TV}(D(f_t),D(f^\star))\le L\cdot d_{\mathcal{F}}(f_t,f^\star) TV ( D ( f t ) , D ( f ⋆ )) ≤ L ⋅ d F ( f t , f ⋆ ) d F ( f t , f ⋆ ) < μ / ( 2 L ) d_{\mathcal{F}}(f_t,f^\star)<\mu/(2L) d F ( f t , f ⋆ ) < μ / ( 2 L ) Step 3: Contraction in the near regime. When d F ( f t , f ⋆ ) < μ / ( 2 L ) d_{\mathcal{F}}(f_t, f^\star) < \mu/(2L) d F ( f t , f ⋆ ) < μ / ( 2 L ) f ⋆ f^\star f ⋆ d F ( BR ( D ( f t ) ) , f ⋆ ) = 0 d_{\mathcal{F}}(\operatorname{BR}(D(f_t)), f^\star) = 0 d F ( BR ( D ( f t )) , f ⋆ ) = 0
d F ( f t + 1 , f ⋆ ) ≤ d F ( f t + 1 , BR ( D ( f t ) ) ) + d F ( BR ( D ( f t ) ) , f ⋆ ) ≤ O ( log N m ) + 0. d_{\mathcal{F}}(f_{t+1}, f^\star) \le d_{\mathcal{F}}(f_{t+1}, \operatorname{BR}(D(f_t))) + d_{\mathcal{F}}(\operatorname{BR}(D(f_t)), f^\star) \le O\left(\sqrt{\frac{\log N}{m}}\right) + 0. d F ( f t + 1 , f ⋆ ) ≤ d F ( f t + 1 , BR ( D ( f t ))) + d F ( BR ( D ( f t )) , f ⋆ ) ≤ O ( m log N ) + 0. Since 0 ≤ L ⋅ d F ( f t , f ⋆ ) 0 \le L \cdot d_{\mathcal{F}}(f_t, f^\star) 0 ≤ L ⋅ d F ( f t , f ⋆ )
d F ( f t + 1 , f ⋆ ) ≤ L ⋅ d F ( f t , f ⋆ ) + O ( log N m ) . d_{\mathcal{F}}(f_{t+1}, f^\star) \le L \cdot d_{\mathcal{F}}(f_t, f^\star) + O\left(\sqrt{\frac{\log N}{m}}\right). d F ( f t + 1 , f ⋆ ) ≤ L ⋅ d F ( f t , f ⋆ ) + O ( m log N ) . Transient. The far regime, where d F ( f t , f ⋆ ) ≥ μ / ( 2 L ) d_{\mathcal{F}}(f_t, f^\star) \ge\mu/(2L) d F ( f t , f ⋆ ) ≥ μ / ( 2 L )
T 0 = O ( log ( diam ( F ) / μ ) 1 − L ) T_0 = O\left(\frac{\log(\operatorname{diam}(\mathcal{F})/\mu)}{1-L}\right) T 0 = O ( 1 − L log ( diam ( F ) / μ ) ) rounds. This is because the excess risk decreases by at least a constant per round in that regime.
Iterated Convergence and Coverage
Proof of Theorem 4.1. From the one-step recursion,
d F ( f t + 1 , f ⋆ ) ≤ L d F ( f t , f ⋆ ) + c 1 log N m , d_{\mathcal{F}}(f_{t+1}, f^\star) \le L d_{\mathcal{F}}(f_t, f^\star) + c_1\sqrt{\frac{\log N}{m}}, d F ( f t + 1 , f ⋆ ) ≤ L d F ( f t , f ⋆ ) + c 1 m log N , iterating over T T T
d F ( f T , f ⋆ ) ≤ L T d F ( f 0 , f ⋆ ) + ∑ k = 0 T − 1 L k c 1 log N m . d_{\mathcal{F}}(f_T, f^\star) \le L^T d_{\mathcal{F}}(f_0, f^\star) + \sum_{k=0}^{T-1} L^k c_1\sqrt{\frac{\log N}{m}}. d F ( f T , f ⋆ ) ≤ L T d F ( f 0 , f ⋆ ) + k = 0 ∑ T − 1 L k c 1 m log N . Since d F ( f 0 , f ⋆ ) ≤ diam ( F ) d_{\mathcal{F}}(f_0, f^\star) \le\operatorname{diam}(\mathcal{F}) d F ( f 0 , f ⋆ ) ≤ diam ( F ) ∑ k = 0 T − 1 L k ≤ 1 / ( 1 − L ) \sum_{k=0}^{T-1} L^k \le1/(1-L) ∑ k = 0 T − 1 L k ≤ 1/ ( 1 − L )
d F ( f T , f ⋆ ) ≤ L T diam ( F ) + c 1 1 − L log N m . d_{\mathcal{F}}(f_T, f^\star) \le L^T \operatorname{diam}(\mathcal{F}) + \frac{c_1}{1-L}\sqrt{\frac{\log N}{m}}. d F ( f T , f ⋆ ) ≤ L T diam ( F ) + 1 − L c 1 m log N . Choosing T T T Set
T = ⌈ log ( n diam ( F ) ) log ( 1 / L ) ⌉ T = \left\lceil\frac{\log(n\operatorname{diam}(\mathcal{F}))}{\log(1/L)}\right\rceil T = ⌈ log ( 1/ L ) log ( n diam ( F )) ⌉ so that
L T diam ( F ) ≤ 1 n . L^T \operatorname{diam}(\mathcal{F}) \le\frac{1}{n}. L T diam ( F ) ≤ n 1 . Since log ( 1 / L ) ≥ 1 − L \log(1/L) \ge1-L log ( 1/ L ) ≥ 1 − L L ∈ ( 0 , 1 ) L \in(0,1) L ∈ ( 0 , 1 )
T = O ( log n 1 − L ) . T = O\left(\frac{\log n}{1-L}\right). T = O ( 1 − L log n ) . Per-round budget. Therefore
m = ⌊ n T + 1 ⌋ = Θ ( n ( 1 − L ) log n ) m=\left\lfloor\frac{n}{T+1}\right\rfloor=\Theta\left(\frac{n(1-L)}{\log n}\right) m = ⌊ T + 1 n ⌋ = Θ ( log n n ( 1 − L ) ) Equilibrium error. Substituting this into the previous bound yields
1 1 − L log N m = O ~ ( 1 ( 1 − L ) 3 / 2 n ) \frac{1}{1-L}\sqrt{\frac{\log N}{m}}=\widetilde{O}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right) 1 − L 1 m log N = O ( ( 1 − L ) 3/2 n 1 ) Hence
d F ( f T , f ⋆ ) ≤ 1 n + O ~ ( 1 ( 1 − L ) 3 / 2 n ) = O ~ ( 1 ( 1 − L ) 3 / 2 n ) d_F(f_T,f^\star)\leq\frac{1}{n}+\widetilde{O}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right)=\widetilde{O}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right) d F ( f T , f ⋆ ) ≤ n 1 + O ( ( 1 − L ) 3/2 n 1 ) = O ( ( 1 − L ) 3/2 n 1 ) Coverage. Applying Theorem 2.8 and using the bound above, we conclude
ExMisc ‾ ( C f T , S , D ( f ⋆ ) ) ≤ O ~ ( 1 ( 1 − L ) 3 / 2 n ) \overline{\operatorname{ExMisc}}(C_{f_T,S},D(f^\star))\leq\widetilde{O}\left(\frac{1}{(1-L)^{3/2}\sqrt{n}}\right) ExMisc ( C f T , S , D ( f ⋆ )) ≤ O ( ( 1 − L ) 3/2 n 1 ) The extra ( 1 − L ) − 1 / 2 (1-L)^{-1/2} ( 1 − L ) − 1/2 § 4.1 .
Tail-Averaging Analysis for the Parametric Algorithm
This appendix proves Lemma C.1, the predictor-error bound used in the proof of Theorem 4.4.
The main idea is the following. Repeated retraining moves the predictor toward equilibrium because the population retraining map is contractive. However, each empirical retraining step is noisy because it uses only finitely many samples. To combine these two facts, we split the procedure into two phases:
a short stabilization period , whose only role is to reduce the effect of the initial predictor, and
an averaging period , where we average later iterates that are already close to equilibrium in order to reduce sampling noise.
The appendix below makes this idea precise.
Parameter notation and one-step decomposition
For the parametric analysis, write the predictor as f θ f_\theta f θ θ ∈ Θ ⊆ R d \theta\in\Theta\subseteq\mathbb{R}^d θ ∈ Θ ⊆ R d
d F ( f θ , f θ ′ ) = ∥ θ − θ ′ ∥ 2 . d_F(f_\theta, f_{\theta'}) = \lVert\theta- \theta' \rVert_2. d F ( f θ , f θ ′ ) = ∥ θ − θ ′ ∥ 2 . Write θ t \theta_t θ t f t f_t f t θ ⋆ \theta^\star θ ⋆ f ⋆ f^\star f ⋆
e t : = θ t − θ ⋆ . e_t := \theta_t - \theta^\star. e t := θ t − θ ⋆ . Let
BR ( D ( θ ) ) : = arg min ϑ ∈ Θ R D ( θ ) ( ϑ ) \operatorname{BR}(D(\theta)) := \arg\min_{\vartheta\in\Theta} R_{D(\theta)}(\vartheta) BR ( D ( θ )) := arg ϑ ∈ Θ min R D ( θ ) ( ϑ ) be the population best response to deployment θ \theta θ β \beta β γ \gamma γ L L L
∥ BR ( D ( θ ) ) − θ ⋆ ∥ ≤ ρ ∥ θ − θ ⋆ ∥ , ρ = L β γ < 1 , (3) \lVert\operatorname{BR}(D(\theta)) - \theta^\star\rVert\le\rho\lVert\theta- \theta^\star\rVert, \qquad\rho= \frac{L\beta}{\gamma} < 1, \tag*{(3)} ∥ BR ( D ( θ )) − θ ⋆ ∥ ≤ ρ ∥ θ − θ ⋆ ∥ , ρ = γ L β < 1 , (3) by Perdomo et al. [27 ] .
At round t t t m m m D ( θ t ) D(\theta_t) D ( θ t )
θ t + 1 = BR ( D ( θ t ) ) + ξ t , (4) \theta_{t+1} = \operatorname{BR}(D(\theta_t)) + \xi_t, \tag*{(4)} θ t + 1 = BR ( D ( θ t )) + ξ t , (4) where the estimation error ξ t \xi_t ξ t
E [ ξ t ∣ θ t ] = 0 , E [ ∥ ξ t ∥ 2 ∣ θ t ] ≤ σ 2 m (5) \mathbb{E}[\xi_t \mid\theta_t] = 0, \qquad\mathbb{E}[\lVert\xi_t \rVert^2 \mid\theta_t] \le\frac{\sigma^2}{m} \tag*{(5)} E [ ξ t ∣ θ t ] = 0 , E [∥ ξ t ∥ 2 ∣ θ t ] ≤ m σ 2 (5) for a constant σ 2 \sigma^2 σ 2 t t t m m m n n n
(4) says that each empirical retraining step equals the population retraining step plus a finite-sample error.
Lemma S1.1 (Contractive Error Recursion). Under (S1)–(S3), the errors satisfy
e t + 1 = A t e t + ξ t , e_{t+1}=A_t e_t+\xi_t, e t + 1 = A t e t + ξ t , where ∥ A t ∥ ≤ ρ \lVert A_t\rVert\le\rho ∥ A t ∥ ≤ ρ for all t t t Consequently, for every t > s t>s t > s there are matrices Φ t , s \Phi_{t,s} Φ t , s with
∥ Φ t , s ∥ ≤ ρ t − s \lVert\Phi_{t,s}\rVert\le\rho^{t-s} ∥ Φ t , s ∥ ≤ ρ t − s such that
e t = Φ t , 0 e 0 + ∑ s = 0 t − 1 Φ t , s + 1 ξ s . e_t=\Phi_{t,0}e_0+\sum_{s=0}^{t-1}\Phi_{t,s+1}\xi_s. e t = Φ t , 0 e 0 + s = 0 ∑ t − 1 Φ t , s + 1 ξ s . Proof. From (S2),
e t + 1 = θ t + 1 − θ ⋆ = ( B R ( D ( θ t ) ) − θ ⋆ ) + ξ t . e_{t+1}=\theta_{t+1}-\theta^\star=(\mathrm{BR}(D(\theta_t))-\theta^\star)+\xi_t. e t + 1 = θ t + 1 − θ ⋆ = ( BR ( D ( θ t )) − θ ⋆ ) + ξ t . Let
u t : = B R ( D ( θ t ) ) − θ ⋆ . u_t:=\mathrm{BR}(D(\theta_t))-\theta^\star. u t := BR ( D ( θ t )) − θ ⋆ . By (S1),
∥ u t ∥ ≤ ρ ∥ e t ∥ . \lVert u_t\rVert\le\rho\lVert e_t\rVert. ∥ u t ∥ ≤ ρ ∥ e t ∥ . If e t ≠ 0 e_t\ne0 e t = 0
A t : = u t e t T ∥ e t ∥ 2 . A_t:=\frac{u_t e_t^{\mathsf T}}{\lVert e_t\rVert^2}. A t := ∥ e t ∥ 2 u t e t T . Then
A t e t = u t , ∥ A t ∥ = ∥ u t ∥ ∥ e t ∥ ≤ ρ . A_t e_t=u_t,\qquad\lVert A_t\rVert=\frac{\lVert u_t\rVert}{\lVert e_t\rVert}\le\rho. A t e t = u t , ∥ A t ∥ = ∥ e t ∥ ∥ u t ∥ ≤ ρ . If e t = 0 e_t=0 e t = 0 u t = 0 u_t=0 u t = 0 A t = 0 A_t=0 A t = 0
u t = A t e t with ∥ A t ∥ ≤ ρ . u_t=A_t e_t\qquad\text{with}\qquad\lVert A_t\rVert\le\rho. u t = A t e t with ∥ A t ∥ ≤ ρ . Therefore
e t + 1 = A t e t + ξ t , e_{t+1}=A_t e_t+\xi_t, e t + 1 = A t e t + ξ t , which proves the first claim.
Iterating the recursion yields
e t = Φ t , 0 e 0 + ∑ s = 0 t − 1 Φ t , s + 1 ξ s , e_t=\Phi_{t,0}e_0+\sum_{s=0}^{t-1}\Phi_{t,s+1}\xi_s, e t = Φ t , 0 e 0 + s = 0 ∑ t − 1 Φ t , s + 1 ξ s , where
Φ t , s = A t − 1 A t − 2 ⋯ A s ( t > s ) , \Phi_{t,s}=A_{t-1}A_{t-2}\cdots A_s\qquad(t>s), Φ t , s = A t − 1 A t − 2 ⋯ A s ( t > s ) , and Φ t , t = I \Phi_{t,t}=I Φ t , t = I ∥ A j ∥ ≤ ρ \lVert A_j\rVert\le\rho ∥ A j ∥ ≤ ρ
∥ Φ t , s ∥ ≤ ∏ j = s t − 1 ∥ A j ∥ ≤ ρ t − s . \lVert\Phi_{t,s}\rVert\le\prod_{j=s}^{t-1}\lVert A_j\rVert\le\rho^{t-s}. ∥ Φ t , s ∥ ≤ j = s ∏ t − 1 ∥ A j ∥ ≤ ρ t − s . Error of the averaged post-stabilization iterates
Algorithm 2 uses two phases:
Define the averaged parameter error over the second phase by
e ˉ B , K : = 1 K ∑ t = B + 1 B + K e t . \bar{e}_{B,K} := \frac{1}{K}\sum_{t=B+1}^{B+K} e_t. e ˉ B , K := K 1 t = B + 1 ∑ B + K e t . The next lemma separates the two sources of error:
an initialization term , which becomes small after the stabilization period, and
a sampling-noise term , which becomes small after averaging.
Lemma S1.2 (Bias-Variance Bound for the Post-Stabilization Average). Under the conditions of Lemma S1.1,
E [ ∥ e ˉ B , K ∥ 2 ] ≤ 2 ρ 2 B ∥ e 0 ∥ 2 + 2 σ 2 ( B + K ) m K 2 ( 1 − ρ ) 2 . \mathbb{E}\left[\left\|\bar{e}_{B,K}\right\|^2\right] \le2\rho^{2B}\left\|e_0\right\|^2 + \frac{2\sigma^2(B+K)}{mK^2(1-\rho)^2}. E [ ∥ e ˉ B , K ∥ 2 ] ≤ 2 ρ 2 B ∥ e 0 ∥ 2 + m K 2 ( 1 − ρ ) 2 2 σ 2 ( B + K ) . Proof. Using Lemma S1.1,
e ˉ B , K = 1 K ∑ t = B + 1 B + K Φ t , 0 e 0 + 1 K ∑ t = B + 1 B + K ∑ s = 0 t − 1 Φ t , s + 1 ξ s . \bar{e}_{B,K} = \frac{1}{K}\sum_{t=B+1}^{B+K}\Phi_{t,0}e_0 + \frac{1}{K}\sum_{t=B+1}^{B+K}\sum_{s=0}^{t-1}\Phi_{t,s+1}\xi_s. e ˉ B , K = K 1 t = B + 1 ∑ B + K Φ t , 0 e 0 + K 1 t = B + 1 ∑ B + K s = 0 ∑ t − 1 Φ t , s + 1 ξ s . Call these two terms b ˉ B , K \bar{b}_{B,K} b ˉ B , K v ˉ B , K \bar{v}_{B,K} v ˉ B , K
e ˉ B , K = b ˉ B , K + v ˉ B , K . \bar{e}_{B,K} = \bar{b}_{B,K} + \bar{v}_{B,K}. e ˉ B , K = b ˉ B , K + v ˉ B , K . Initialization term. For every t ≥ B + 1 t \ge B+1 t ≥ B + 1
∥ Φ t , 0 e 0 ∥ ≤ ρ t ∥ e 0 ∥ ≤ ρ B ∥ e 0 ∥ . \left\|\Phi_{t,0}e_0\right\| \le\rho^t\left\|e_0\right\| \le\rho^B\left\|e_0\right\|. ∥ Φ t , 0 e 0 ∥ ≤ ρ t ∥ e 0 ∥ ≤ ρ B ∥ e 0 ∥ . Therefore
∥ b ˉ B , K ∥ = ∥ 1 K ∑ t = B + 1 B + K Φ t , 0 e 0 ∥ ≤ 1 K ∑ t = B + 1 B + K ρ B ∥ e 0 ∥ = ρ B ∥ e 0 ∥ . \left\|\bar{b}_{B,K}\right\| = \left\|\frac{1}{K}\sum_{t=B+1}^{B+K}\Phi_{t,0}e_0\right\| \le\frac{1}{K}\sum_{t=B+1}^{B+K}\rho^B\left\|e_0\right\| = \rho^B\left\|e_0\right\|. b ˉ B , K = K 1 t = B + 1 ∑ B + K Φ t , 0 e 0 ≤ K 1 t = B + 1 ∑ B + K ρ B ∥ e 0 ∥ = ρ B ∥ e 0 ∥ . Hence
∥ b ˉ B , K ∥ 2 ≤ ρ 2 B ∥ e 0 ∥ 2 . \left\|\bar{b}_{B,K}\right\|^2 \le\rho^{2B}\left\|e_0\right\|^2. b ˉ B , K 2 ≤ ρ 2 B ∥ e 0 ∥ 2 . Sampling-noise term. Rearrange the second term by grouping together the contributions of each noise variable ξ s \xi_s ξ s
v ˉ B , K = ∑ s = 0 B + K − 1 W s ξ s , \bar{v}_{B,K} = \sum_{s=0}^{B+K-1} W_s \xi_s, v ˉ B , K = s = 0 ∑ B + K − 1 W s ξ s , where
W s ≔ 1 K ∑ t = max ( B + 1 , s + 1 ) B + K Φ t , s + 1 . W_s \coloneqq\frac{1}{K}\sum_{t=\max(B+1,s+1)}^{B+K}\Phi_{t,s+1}. W s : = K 1 t = m a x ( B + 1 , s + 1 ) ∑ B + K Φ t , s + 1 . Using ∥ Φ t , s + 1 ∥ ≤ ρ t − s − 1 \lVert\Phi_{t,s+1}\rVert\le\rho^{t-s-1} ∥ Φ t , s + 1 ∥ ≤ ρ t − s − 1
∥ W s ∥ ≤ 1 K ∑ j = 0 ∞ ρ j = 1 K ( 1 − ρ ) . \lVert W_s\rVert\le\frac{1}{K}\sum_{j=0}^{\infty}\rho^j = \frac{1}{K(1-\rho)}. ∥ W s ∥ ≤ K 1 j = 0 ∑ ∞ ρ j = K ( 1 − ρ ) 1 . Condition on the full trajectory A = { A 0 , … , A B + K − 1 } \mathcal{A}=\{A_0,\ldots,A_{B+K-1}\} A = { A 0 , … , A B + K − 1 } A \mathcal{A} A W s W_s W s E [ ξ s ∣ A ] = 0 \mathbb{E}[\xi_s\mid\mathcal{A}]=0 E [ ξ s ∣ A ] = 0 ξ s \xi_s ξ s A \mathcal{A} A
E [ ∥ v ˉ B , K ∥ 2 ∣ A ] = ∑ s = 0 B + K − 1 ∥ W s ∥ 2 E [ ∥ ξ s ∥ 2 ∣ A ] ≤ σ 2 m ∑ s = 0 B + K − 1 ∥ W s ∥ 2 . \mathbb{E}\left[\lVert\bar{v}_{B,K}\rVert^2\mid\mathcal{A}\right]
=
\sum_{s=0}^{B+K-1}\lVert W_s\rVert^2\mathbb{E}\left[\lVert\xi_s\rVert^2\mid\mathcal{A}\right]
\le
\frac{\sigma^2}{m}\sum_{s=0}^{B+K-1}\lVert W_s\rVert^2. E [ ∥ v ˉ B , K ∥ 2 ∣ A ] = s = 0 ∑ B + K − 1 ∥ W s ∥ 2 E [ ∥ ξ s ∥ 2 ∣ A ] ≤ m σ 2 s = 0 ∑ B + K − 1 ∥ W s ∥ 2 . Taking expectation over A \mathcal{A} A ∥ W s ∥ ≤ 1 K ( 1 − ρ ) \lVert W_s\rVert\le\frac{1}{K(1-\rho)} ∥ W s ∥ ≤ K ( 1 − ρ ) 1
E [ ∥ v ˉ B , K ∥ 2 ] ≤ ( B + K ) ⋅ 1 K 2 ( 1 − ρ ) 2 ⋅ σ 2 m . \mathbb{E}\left[\lVert\bar{v}_{B,K}\rVert^2\right]
\le
(B+K)\cdot\frac{1}{K^2(1-\rho)^2}\cdot\frac{\sigma^2}{m}. E [ ∥ v ˉ B , K ∥ 2 ] ≤ ( B + K ) ⋅ K 2 ( 1 − ρ ) 2 1 ⋅ m σ 2 . Combine the two terms. Using ∥ a + b ∥ 2 ≤ 2 ∥ a ∥ 2 + 2 ∥ b ∥ 2 \lVert a+b\rVert^2\le2\lVert a\rVert^2+2\lVert b\rVert^2 ∥ a + b ∥ 2 ≤ 2 ∥ a ∥ 2 + 2 ∥ b ∥ 2
E [ ∥ e ˉ B , K ∥ 2 ] ≤ 2 ∥ b ˉ B , K ∥ 2 + 2 E [ ∥ v ˉ B , K ∥ 2 ] , \mathbb{E}\left[\lVert\bar{e}_{B,K}\rVert^2\right]
\le
2\lVert\bar{b}_{B,K}\rVert^2+2\mathbb{E}\left[\lVert\bar{v}_{B,K}\rVert^2\right], E [ ∥ e ˉ B , K ∥ 2 ] ≤ 2 ∥ b ˉ B , K ∥ 2 + 2 E [ ∥ v ˉ B , K ∥ 2 ] , which gives
E [ ∥ e ˉ B , K ∥ 2 ] ≤ 2 ρ 2 B ∥ e 0 ∥ 2 + 2 σ 2 ( B + K ) m K 2 ( 1 − ρ ) 2 . \mathbb{E}\left[\lVert\bar{e}_{B,K}\rVert^2\right]
\le
2\rho^{2B}\lVert e_0\rVert^2+
\frac{2\sigma^2(B+K)}{mK^2(1-\rho)^2}. E [ ∥ e ˉ B , K ∥ 2 ] ≤ 2 ρ 2 B ∥ e 0 ∥ 2 + m K 2 ( 1 − ρ ) 2 2 σ 2 ( B + K ) . Rate for Algorithm 2
The last step is to choose B B B K K K
the initialization term is negligible, and
the averaging term uses essentially the full sample budget.
Lemma S1.4 (Tail-Average Rate for Performative Retraining). Under the conditions of Theorem 4.4, suppose the ERM errors satisfy (S3). Set
B = K = ⌊ log n log ( 1 / ρ ) ⌋ , m = ⌊ n B + K + 1 ⌋ . B=K=\left\lfloor\frac{\log n}{\log(1/\rho)}\right\rfloor,\qquad m=\left\lfloor\frac{n}{B+K+1}\right\rfloor. B = K = ⌊ log ( 1/ ρ ) log n ⌋ , m = ⌊ B + K + 1 n ⌋ . Then the predictor returned by Algorithm 2 satisfies
E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ~ ( 1 ( 1 − ρ ) 2 n ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)^2\right]\leq\widetilde{O}\left(\frac{1}{(1-\rho)^2n}\right). E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ( ( 1 − ρ ) 2 n 1 ) . Consequently,
E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ O ~ ( 1 ( 1 − ρ ) n ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)\right]\leq\widetilde{O}\left(\frac{1}{(1-\rho)\sqrt{n}}\right). E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ O ( ( 1 − ρ ) n 1 ) . Proof. Apply Lemma S1.2.
Initialization term. With
B = ⌊ log n log ( 1 / ρ ) ⌋ , B=\left\lfloor\frac{\log n}{\log(1/\rho)}\right\rfloor, B = ⌊ log ( 1/ ρ ) log n ⌋ , we have
ρ B ≤ 1 n , hence ρ 2 B ∥ e 0 ∥ 2 ≤ ∥ e 0 ∥ 2 n 2 . \rho^B\leq\frac{1}{n},\qquad\text{hence}\qquad\rho^{2B}\lVert e_0\rVert^2\leq\frac{\lVert e_0\rVert^2}{n^2}. ρ B ≤ n 1 , hence ρ 2 B ∥ e 0 ∥ 2 ≤ n 2 ∥ e 0 ∥ 2 . So the initialization term is of order 1 / n 2 1/n^2 1/ n 2 1 / n 1/n 1/ n
Averaging term. Since B = K B=K B = K ( B + K ) / K 2 (B+K)/K^2 ( B + K ) / K 2 1 / K 1/K 1/ K
m = ⌊ n B + K + 1 ⌋ , m=\left\lfloor\frac{n}{B+K+1}\right\rfloor, m = ⌊ B + K + 1 n ⌋ , we have m ≍ n / ( B + K ) m\asymp n/(B+K) m ≍ n / ( B + K )
B + K m K 2 = O ( 1 n ) . \frac{B+K}{mK^2}=O\left(\frac{1}{n}\right). m K 2 B + K = O ( n 1 ) . Therefore
2 σ 2 ( B + K ) m K 2 ( 1 − ρ ) 2 = O ( 1 n ( 1 − ρ ) 2 ) . \frac{2\sigma^2(B+K)}{mK^2(1-\rho)^2}=O\left(\frac{1}{n(1-\rho)^2}\right). m K 2 ( 1 − ρ ) 2 2 σ 2 ( B + K ) = O ( n ( 1 − ρ ) 2 1 ) . Combine. Lemma S1.2 now gives
E [ ∥ e ˉ B , K ∥ 2 ] ≤ O ( 1 n 2 ) + O ( 1 n ( 1 − ρ ) 2 ) = O ~ ( 1 n ( 1 − ρ ) 2 ) . \mathbb{E}\left[\lVert\bar{e}_{B,K}\rVert^2\right]\leq O\left(\frac{1}{n^2}\right)+O\left(\frac{1}{n(1-\rho)^2}\right)=\widetilde{O}\left(\frac{1}{n(1-\rho)^2}\right). E [ ∥ e ˉ B , K ∥ 2 ] ≤ O ( n 2 1 ) + O ( n ( 1 − ρ ) 2 1 ) = O ( n ( 1 − ρ ) 2 1 ) . Since d F d_F d F
E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ~ ( 1 n ( 1 − ρ ) 2 ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)^2\right]\leq\widetilde{O}\left(\frac{1}{n(1-\rho)^2}\right). E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ( n ( 1 − ρ ) 2 1 ) . The bound on the first moment follows from Jensen’s inequality:
E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ~ ( 1 ( 1 − ρ ) n ) . \mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)\right]\leq\sqrt{\mathbb{E}\left[d_F(\bar{f}_{B,K},f^\star)^2\right]}\leq\widetilde{O}\left(\frac{1}{(1-\rho)\sqrt{n}}\right). E [ d F ( f ˉ B , K , f ⋆ ) ] ≤ E [ d F ( f ˉ B , K , f ⋆ ) 2 ] ≤ O ( ( 1 − ρ ) n 1 ) . Experimental Details
This appendix collects the full settings for the simulations reported in § 5 . Unless stated otherwise, all simulations use α = 0.1 \alpha= 0.1 α = 0.1 D ( f ⋆ ) D(f^{\star}) D ( f ⋆ )
For the semi-synthetic strategic-regression setup, we also align with the broader strategic-classification and recourse literature on behavioral response and practical deployment constraints [12 , 17 , 34 ] .
Parameter Specifications
Table S1 summarizes the parameter grids for the six simulation setups reported in the main text and appendix. All use a constant covariate, X = { x 0 } \mathcal{X} = \{x_0\} X = { x 0 }
Distribution map. Simulations 1, 2, 4, and 5 use the Gaussian location model
Y ∼ N ( a + L θ , 1 ) , Y \sim\mathcal{N}(a+L\theta,1), Y ∼ N ( a + L θ , 1 ) , with equilibrium
θ ⋆ = a 1 − L , \theta^{\star} = \frac{a}{1-L}, θ ⋆ = 1 − L a , and score
s ( y ; θ ) = ∣ y − θ ∣ . s(y;\theta) = \lvert y-\theta\rvert. s ( y ; θ ) = ∣ y − θ ∣ . Simulation 1 varies L L L n n n O ~ ( 1 / ( ( 1 − L ) n ) ) \widetilde{O}(1/((1-L)\sqrt{n})) O ( 1/ (( 1 − L ) n )) Θ ~ ( 1 / ( 1 − L ) 2 ) \widetilde{\Theta}(1/(1-L)^2) Θ ( 1/ ( 1 − L ) 2 )
Simulation 2 fixes the calibration size m = 2000 m = 2000 m = 2000
ε = ∣ θ d e p l o y e d − θ ⋆ ∣ \varepsilon= \lvert\theta_{\mathrm{deployed}}-\theta^{\star}\rvert ε = ∣ θ deployed − θ ⋆ ∣ across several values of L L L L ε L\varepsilon L ε
Table S1. Synthetic experiments reported in the paper and appendix.
Auxiliary Experiments
Simulation 4: Le Cam Lower-Bound
This simulation validates the minimax lower bound of Theorem 3.2 by instantiating the Le Cam two-hypothesis construction. For each ( L , n ) (L, n) ( L , n ) D 0 D_{0} D 0 D 1 D_{1} D 1 δ = 0.5 / n \delta= 0.5/\sqrt{n} δ = 0.5/ n
Figure S1 shows the worst-case excess miscoverage on a log-log scale. All curves decrease with n n n L L L L = 0.9 L = 0.9 L = 0.9 = α = \alpha = α n ≤ 1000 n \le1000 n ≤ 1000 n ≥ 5000 n \ge5000 n ≥ 5000
Figure S1. (a) Worst-case excess miscoverage versus n n n
Figure S1: Simulation 4: Le Cam lower bound validation. (a) Worst-case excess miscoverage (maximum over D 0 D_0 D 0 D 1 D_1 D 1 n n n L = 0.9 L = 0.9 L = 0.9 n ≤ 1000 n \le1000 n ≤ 1000 × ( 1 − L ) × n \times(1-L) \times\sqrt{n} × ( 1 − L ) × n [ 0.13 , 0.35 ] [0.13, 0.35] [ 0.13 , 0.35 ] Ω ( 1 / ( ( 1 − L ) n ) ) \Omega(1/((1-L)\sqrt{n})) Ω ( 1/ (( 1 − L ) n ))
Figure S1 plots the scaled quantity excess × ( 1 − L ) × n \times(1-L) \times\sqrt{n} × ( 1 − L ) × n Ω ( 1 / ( ( 1 − L ) n ) ) \Omega(1/((1-L)\sqrt{n})) Ω ( 1/ (( 1 − L ) n )) [ 0.13 , 0.35 ] [0.13, 0.35] [ 0.13 , 0.35 ] n n n L > 0 L > 0 L > 0 L L L ≈ 0.27 \approx0.27 ≈ 0.27 L = 0.3 L = 0.3 L = 0.3 ≈ 0.14 \approx0.14 ≈ 0.14 L = 0.9 L = 0.9 L = 0.9 n n n ( 1 − L ) (1-L) ( 1 − L )
Simulation 5: Model-Free Algorithm
This simulation validates Algorithm 1 (MF-PCP) and Theorem 4.1 using the Gaussian location model with a finite predictor class of size N N N
Figure S2 shows excess miscoverage vs. n n n N = 50 N = 50 N = 50 L L L n − 1 / 2 n^{-1/2} n − 1/2 [ − 0.54 , − 0.44 ] [-0.54, -0.44] [ − 0.54 , − 0.44 ] L L L
(a) Excess miscoverage versus n n n N = 50 N = 50 N = 50
(b) Effect of class size N N N L = 0.5 L = 0.5 L = 0.5
Figure S2. Simulation 5: Model-free algorithm validation. (a) Excess miscoverage vs. n n n N = 50 N = 50 N = 50 n − 1 / 2 n^{-1/2} n − 1/2 L L L N N N L = 0.5 L = 0.5 L = 0.5 log N \log N log N
Figure S2 shows the effect of the class size N N N L = 0.5 L = 0.5 L = 0.5 N = 10 , 50 , 200 N = 10, 50, 200 N = 10 , 50 , 200 log N \log N log N n − 1 / 2 n^{-1/2} n − 1/2
Convergence to equilibrium. The convergence check (fraction of replications where θ f i n a l \theta_{\mathrm{final}} θ final θ g r i d \theta_{\mathrm{grid}} θ grid L = 0 L = 0 L = 0 N = 10 N = 10 N = 10 n = 50,000 n = 50{,}000 n = 50 , 000 L = 0.5 L = 0.5 L = 0.5 N = 200 N = 200 N = 200 n = 200 n = 200 n = 200 not indicate a problem: with a discrete grid of N N N θ g r i d \theta_{\mathrm{grid}} θ grid
Simulation 6: Impossibility at L = 1 L = 1 L = 1
This simulation validates Theorem 3.1 (Case 2) using the construction from the proof. Two 1-sensitive maps D + D_{+} D + D − D_{-} D − θ + ⋆ = 1 − ε \theta_{+}^{\star} = 1 - \varepsilon θ + ⋆ = 1 − ε θ − ⋆ = ε \theta_{-}^{\star} = \varepsilon θ − ⋆ = ε ε = 0.5 / n \varepsilon= 0.5/n ε = 0.5/ n n n n ε → 0 \varepsilon\to0 ε → 0 θ + ⋆ → 1 \theta_{+}^{\star} \to1 θ + ⋆ → 1 θ − ⋆ → 0 \theta_{-}^{\star} \to0 θ − ⋆ → 0
Figure S3 plots the failure rate (fraction of replications producing either a trivial set { 0 , 1 } \{0, 1\} { 0 , 1 } 1 − α 1-\alpha 1 − α n n n n = 100 n = 100 n = 100 n ≥ 5,000 n \ge5{,}000 n ≥ 5 , 000 n = 500 , 1000 n = 500, 1000 n = 500 , 1000 ≈ 74 % \approx74\% ≈ 74% ≈ 89 % \approx89\% ≈ 89% ε \varepsilon ε n n n ε → 0 \varepsilon\to0 ε → 0
Figure S3. Simulation 6: Impossibility at L = 1 L = 1 L = 1 n n n D + D_{+} D + D − D_{-} D − Theorem 3.1 . Dashed line: Le Cam floor at 0.5.
This non-monotone pattern is predicted by the construction: at small n n n ε = 0.5 / n \varepsilon= 0.5/n ε = 0.5/ n TV ( D + ( θ ) , D − ( θ ) ) ≤ 2 ε \operatorname{TV}(D_{+}(\theta), D_{-}(\theta)) \le2\varepsilon TV ( D + ( θ ) , D − ( θ )) ≤ 2 ε n n n ε → 0 \varepsilon\to0 ε → 0 KL \operatorname{KL} KL
The dominant failure mode is trivial prediction sets: at n ≥ 5,000 n \ge5{,}000 n ≥ 5 , 000 C = { 0 , 1 } C = \{0, 1\} C = { 0 , 1 }
