PaperlayerView exact revision on arXiv

Source-linked AI summary

Rolling Conformal Prediction in Sequential Model Training

Chen Cheng, Ruiting Liang, Rina Foygel Barber

arXiv:2609.26951v1math.STcs.LGstat.MEstat.MLstat.TH

TL;DR

Sequentially updated models pose a challenge for predictive uncertainty quantification because standard conformal methods are not designed for dynamic training. Rolling-CP calibrates incoming observations against the current predictor before using them in future training. It guarantees at least 1−2α coverage for exchangeable streams without stability assumptions, while stability conditions can sharpen coverage toward 1−α.

  • Problem

    Standard conformal procedures are not designed for dynamic training, although modern systems continually update models as data arrive.

    Source: §1 · pp. 1–2

  • Method

    Rolling-CP compares each incoming observation with candidate points using the current score function, then incorporates that observation into future training.

    Source: §1.2 · p. 3

  • Results

    For exchangeable data streams, rolling-CP guarantees at least 1−2α coverage without stability assumptions; under stability conditions, coverage can approach 1−α.

    Source: §2 · p. 6, §3.1 · p. 11

  • Takeaways & Limitations

    Rolling-CP is computationally lean and tuning-free, adapting to evolving models without data splitting or repeated retraining.

    Source: §5 · p. 19

    Robustness and theoretical guarantees for temporally dependent streams remain open questions in this work.

    Source: §5 · p. 19

Abstract

from arXiv · show

We introduce Rolling Conformal Prediction (rolling-CP), a distribution-free predictive inference method for the setting of sequential model training. Specifically, given a data stream $(X_1,Y_1),(X_2,Y_2),\dots$, at each time $n$ the trained model may depend on the observed history $\{(X_i,Y_i)\}_{i<n}$. This setting arises naturally in modern sequential training, including one-pass training over massive datasets and continual fine-tuning or test-time adaptation of language models during deployment. Rolling-CP first calibrates each incoming observation against the current predictor and then rolls it into future training. In this way, we avoid the need for data splitting. Remarkably, although the models at times $n=1,2,\dots$ may have entirely different properties and accuracy levels, for exchangeable data it is nonetheless possible to establish a guarantee of marginal coverage, with a familiar universal factor-two guarantee (a worst case guarantee of $1-2\alpha$ coverage, as compared to the target level $1-\alpha$), without any assumptions of stability or any restrictions on the model training process. For i.i.d. data streams, we further prove high-probability training-conditional validity uniformly over time; under stability conditions, coverage guarantees sharpen towards $1-\alpha$. Numerical experiments on sequential regression, multiclass SGD, and one-pass neural-network training further demonstrate the practical effectiveness of rolling-CP.

1 Introduction

Sequentially updated models complicate uncertainty quantification because standard conformal procedures calibrate a single fitted model. Rolling-CP reuses each observation for calibration before incorporating it into future training, and the introduction situates this approach among sequential-training examples and related conformal methods.

1 Introduction

  • Existing conformal methods are not designed for dynamic training, where models update as new data arrive.Modern systems may train iteratively on massive datasets, including single- or few-pass settings.Source: §1 · pp. 1–2, §1.3 · p. 4

1.1 Setting and background

  • At each time n, the goal is a prediction set for the next response using data observed through n.Split conformal offers marginal coverage under exchangeability but requires splitting training data from calibration data.Source: §1.1 · pp. 2–3

1.2 The rolling conformal prediction method

  • Rolling-CP compares each candidate with every incoming observation using the score function trained before that observation, then uses the observation in future training.Unlike split conformal’s shared trained score function, rolling-CP uses a different score function for each comparison.Source: §1.2 · p. 3

1.3 Examples of sequential training settings

  • Sequential-training examples include SGD for multiclass classification and continually updated language-model pipelines, whose updates may depend on the observed history.The data stream can be exchangeable even when the predictive model evolves with past observations.Source: §1.3 · pp. 4–5

1.4 Related work

  • Related conformal approaches include full conformal, which avoids splitting at greater computational cost, and online conformal methods that target long-run empirical coverage.The paper focuses on per-time guarantees for exchangeable streams and notes that rolling-CP can also be deployed sequentially.Source: §1.4 · pp. 5–6

2 Main results

Rolling-CP’s coverage guarantees address sequentially updated score functions, for which traditional conformal arguments based on a shared trained model do not apply. The results establish marginal coverage under exchangeability, characterize the rolling comparison through convex ordering, and give training-conditional guarantees under i.i.d. data.

2 Main results

  • The usual shared-model exchangeability argument fails for rolling-CP because the score function changes with the observed history and comparisons use scores from different stages.The paper therefore develops a distinct analysis for the sequentially updated construction.Source: §2 · p. 6, §2.2 · p. 8

2.1 Marginal coverage guarantee

  • Rolling-CP guarantees at least 1−2α marginal coverage for exchangeable data, with arbitrary history-dependent score functions and no stability or consistency assumptions.With additional stability assumptions, coverage can be approximately 1−α.Source: §2 · p. 6, §2.1 · pp. 6, 8
  • Even for i.i.d. uniform data, asymptotic coverage can be any value in (1−2α,1], so the factor-two guarantee cannot be improved without further assumptions such as convergence or score stability.The paper states that coverage is expected in practice to be approximately 1−α.Source: §2.1 · p. 8

2.2 Proof of Theorem 1 via convex ordering

  • The rolling comparison satisfies decreasing-convex ordering below a discrete uniform distribution, making it a p*-value and yielding the factor-two coverage guarantee.The bound can be sharpened to 1−(2α−1/(n+1))+, using the discrete-uniform comparison.Source: §2.2 · p. 9

2.3 Conditional and uniform coverage in the i.i.d. case

  • For i.i.d. data, rolling-CP guarantees training-conditional coverage at least 1−2α−O_P(n^−1/2), uniformly over time.The uniform guarantee also implies approximate marginal coverage when test time is chosen adaptively, such as at a suitable stopping time.Source: §2.3 · p. 10

3 Coverage guarantees under stability conditions

Under i.i.d. data, stability assumptions sharpen rolling-CP coverage toward the nominal level. The section formalizes score-comparison stability, derives coverage bounds, and relates this condition to quantitative score stability.

3.2 Comparing to quantitative algorithmic stability conditions

  • Score-comparison stability requires scores to preserve pairwise rankings over time, whereas quantitative Lq stability directly bounds score-value differences.The paper describes this comparison-based condition as often weaker than quantitative stability.Source: §3.1 · p. 11, §3.2 · p. 12

3.1 Results under score comparison stability

  • Under score-comparison stability, marginal coverage is bounded below by 1 − α · (n + 1)/(n − m + 2) − 2√ν.The theorem also gives an analogous upper bound when the limiting score has no ties almost surely.Source: §3.1 · p. 11

3 Coverage guarantees under stability conditions

  • When score functions stabilize after m observations with small ν, rolling-CP coverage is approximately the nominal level 1 − α.The deviation is controlled by an error term measuring score stabilization over time.Source: §3 · pp. 10–11, §3.1 · p. 11

3.1 Results under score comparison stability

  • The training-conditional coverage rate also improves to at least 1 − α − O_P(n^−1/2), compared with 1 − 2α − O_P(n^−1/2).This refinement is stated under score-comparison stability.Source: §3.1 · p. 11

3.2 Comparing to quantitative algorithmic stability conditions

  • With a bounded conditional density for the reference score, Lq score stability implies score-comparison stability; without that density condition, the resulting bound can be vacuous.When the density bound B is arbitrarily large, the induced parameter can equal ν = 1.Source: §3.2 · p. 12

4 Numerical experiments

The experiments evaluate rolling-CP in linear regression, sequential logistic regression, and one-pass neural-network training. Across the reported settings, empirical coverage is near nominal or reasonable along the trajectory, and rolling-CP produces narrower sets than split-CP in the OLS comparison.

4.1 OLS for linear regression

  • OLS rolling-CP coverage is extremely close to nominal across the stream, including as the sample size crosses the interpolation threshold.The experiment uses d = 200, n = 40,000, and M = 100 independent streams.Source: §4.1 · p. 13, Figure 1 · p. 14
  • Rolling-CP sets become substantially narrower than split-CP as n increases, while empirical coverage remains similar across methods.The comparison uses fixed and proportional training cutoffs for minimum-norm OLS.Source: §4.1 · p. 15, Figure 2 · p. 16

4.2 SGD for logistic regression

  • In multi-index logistic regression, rolling-CP achieves approximately nominal empirical coverage despite fluctuations in the SGD-trained classifier.The experiments use both cross-entropy and moving-average logit-margin scores.Source: §4.2 · p. 17, Figure 3 · pp. 17–18

4.3 One-pass training on MNIST

  • The MNIST experiment shows reasonable training-conditional coverage along its realized training trajectory, but does not fully evaluate the marginal guarantees.Only one training stream is used; verifying the marginal guarantees would require repeated independent streams.Source: §4.3 · p. 19

5 Discussion

The discussion presents rolling-CP as a lightweight approach for sequential training and identifies diagnostic uses and open questions about conditional coverage and temporally dependent data.

5 Discussion

  • The method is described as computationally lean and tuning-free, adapting to evolving models without additional data splitting or repeated retraining.The discussion also states that it provides validity under minimal distributional assumptions.Source: §5 · p. 19
  • Rolling-CP records each example’s score before that example updates training, providing an out-of-sample diagnostic within a single run.The authors suggest these diagnostics can guide stopping or continuing and help distinguish overfitting from delayed generalization or other training transitions.Source: §5 · p. 19
  • Extending rolling-CP to test-conditional coverage remains an open direction, with the challenge of handling scores that evolve throughout training.Exact, nontrivial distribution-free test-conditional coverage is generally impossible without additional assumptions [59, 6, 4].Source: §5 · p. 19
  • Rolling-CP’s performance under temporally dependent streams remains an open question because exchangeability no longer holds.The discussion contrasts possible empirical robustness under short-range dependence with potential severe coverage loss requiring modification in related methods.Source: §5 · p. 19

A.1 Proof of Theorem 2

The proof develops a distributional-ordering argument for Theorem 2, using a p*-value bound and an induction based on exchangeability to establish the result.

A.1 Proof of Theorem 2

  • A random variable p with p ⪯dcx Unif(0,1) is called a p*-value and satisfies P(p ≤ α) ≤ 2α for all α ∈ [0,1].The proof invokes this bound as part of its argument.Source: §A.1 · p. 26
  • The proof uses a lemma stating that A + B ⪯dcx X* + Y* when A and B are decreasing-convex dominated by X and Y, respectively, and (X*, Y*) is their comonotone coupling.The section introduces comonotone random variables as variables represented by nondecreasing functions of a shared random variable.Source: §A.1 · p. 26

Proof of Theorem 2.

  • Theorem 2’s proof proceeds by induction on n, conditioning on Z1 and the empirical distribution of the data.It applies the induction hypothesis to the remaining exchangeable observations and their associated scores.Source: Proof of Theorem 2 · p. 27
  • The proof constructs a comonotone coupling of conditional distributions and uses exchangeability to compare the resulting quantities.The argument concludes with a uniformly distributed rank, 1{U > C} + ⌈n ⋅ U⌉, which completes the proof.Source: Proof of Theorem 2 · pp. 27–28

A.2 Alternative proof of Theorem 1

This alternative proof gives a more direct route to Theorem 1 than the distributional-ordering proof, using exchangeability and a simplifying no-ties assumption for intuition.

A.2 Alternative proof of Theorem 1

  • Unlike the earlier proof, this argument proves Theorem 1 without relying on distributional ordering and is closer to the intuitive i.i.d.-case argument.The proof assumes scores have no ties almost surely for this alternative intuitive argument; the earlier proof did not require that assumption.Source: §A.2 · p. 28
  • Under exchangeability, the proof’s p_i values are mutually independent but not identically distributed, with discrete uniform marginals.The marginals are supported on {0, 1/(n−i+1), …, (n−i)/(n−i+1), 1}.Source: §A.2 · pp. 28–29
  • The proof applies a lemma to the filtration generated by past observations to derive the bound needed for the rolling-CP prediction set.The passage states that this bound is sufficient by the definition of the rolling-CP prediction set.Source: §A.2 · p. 29

A.3 Proof of Theorem 3

The proof establishes a uniform-in-time bound by combining independent auxiliary variables with a union bound over time.

A.3 Proof of Theorem 3

  • The proof notes that the p_i values are functions of past observations and therefore independent of the next observation Z_{n+1}.In the no-ties case, these p_i values match those used in the i.i.d.-case marginal-coverage proof.Source: §A.3 · pp. 29–30
  • The proof applies a lemma with W = Z<n+1 to obtain a bound with probability at least 1 − δ.The argument then uses that p_rolling ≥ 1/(n+1) almost surely to establish the desired bound.Source: §A.3 · p. 30
  • The proof allocates δ/(n+1)^2 to each time point and uses a union bound to obtain the desired bound uniformly over n ≥ 0.The series of allocated error probabilities sums to at most δ.Source: §A.3 · p. 30

A.4 Proof of Proposition 1

The proof constructs alternating score functions and analyzes their long-run prediction sets under different target coverage levels. The cases show how these sets can converge to intervals with the stated coverage behavior.

A.4 Proof of Proposition 1

  • The construction alternates between si(z)=z and a score that reflects z across l+r inside [l,r] while leaving values outside unchanged.Source: §A.4 · pp. 30–31
  • For ν∈(0,α), choosing l=1−2α+ν and r=1 yields Cn=[0,l) almost surely for all sufficiently large n.The scores are constructed so si(Zi) is uniform regardless of whether i is odd or even.Source: §A.4 · p. 31
  • For ν∈(α,2α), choosing l=1−2α−ϵ and r=1−2α+ν yields Cn=[0,r] almost surely for all sufficiently large n.Here ϵ∈(0,1−2α).Source: §A.4 · pp. 31–32
  • At ν=2α, constant scores si(z)≡1 give Cn=Z almost surely and coverage 1 for every n.Source: §A.4 · p. 32
  • At ν=α, scores si(z)=z make the prediction sets converge to [0,1−α], with coverage tending to 1−α.Source: §A.4 · p. 32

B Proofs for Section 3

These proofs establish results on stability, distribution drift, and merging conformal procedures. They use conditional score comparisons and clarify how the guarantees relate to their assumptions and weighting schemes.

B.1 Proof of Theorem 4

  • The proof of Theorem 4 conditions on the training history so later scores are exchangeable, then uses a split-conformal p-value argument and chooses γ=√ν for its bounds.Source: §B.1 · pp. 32–33

B.2 Proof of Proposition 2

  • The stability proof compares sequential scores with a reference score, bounding disagreement through score differences and the reference score's bounded density.The proof bounds the probability that the reference scores are within δ by 2δB.Source: §B.2 · pp. 33–34

C.1 Coverage under distribution drift

  • The drift result states that independent observations with distributions Pi close in total variation to the test distribution Pn+1 retain coverage nearly matching the exchangeable or i.i.d. setting.The theorem allows arbitrary sequential score functions; dTV denotes total variation distance.Source: §C.1 · p. 34

C.2 Sequential inference via merging: a comparison

  • Merged split-CP p-values remain valid under exchangeability and yield factor-two validity when averaged, but their unequal weights reduce effective sample size relative to rolling-CP.Source: §C.2 · pp. 35–36

C.3 Training-conditional coverage under stability

Under score-comparison stability, the paper strengthens its training-conditional coverage guarantee. The proof conditions on the training history and uses order statistics of the remaining scores.

C.3 Training-conditional coverage under stability

  • With Assumption 1, training-conditional coverage is approximately 1−α, strengthening the approximately 1−2α guarantee available without stability.The theorem gives a high-probability bound on training-conditional miscoverage for any δ∈(0,1).Source: §C.3 · p. 36
  • Conditional on Z<m, the reference scores from m through n+1 are i.i.d., allowing the proof to express the coverage event through an order statistic.The argument uses the beta distribution of the corresponding uniform order statistic.Source: §C.3 · p. 37

D.1 Proof of Lemma A.2

The appendix proofs adapt a pigeonhole argument to conditional probabilities and use coupling and concentration tools for related lemmas. In the exchangeable setting, observing all conditional probabilities can invalidate the simpler selection argument.

D.1 Proof of Lemma A.2

  • In the exchangeable case, later conditional probabilities are not measurable with respect to the earlier filtration, so selecting the smallest probabilities can invalidate their conditional-probability interpretation.The proof instead selects probabilities using filtration-adapted indicators.Source: §D.1 · p. 38

D.2 Proof of Lemma A.1

  • The proof of Lemma A.1 constructs marginally matching conditional samples, then uses a comonotone coupling to establish the stated convex-order comparison.Source: §D.2 · p. 40

D.3 Proof of Lemma A.3

  • The proof of Lemma A.3 orders the probabilities, applies a pigeonhole argument and Markov's inequality, then invokes McDiarmid's inequality for a high-probability bound.Source: §D.3 · p. 41

D.4 Proof of Lemma C.1

The proof orders the p_i values and tracks events and constants associated with each order statistic. It uses random ranking and a pigeonhole/Markov argument to bound the probability under consideration.

D.4 Proof of Lemma C.1

  • The proof orders p_1,...,p_n and associates each order statistic p_(j) with an event A(j) and constant c(j).The proof distinguishes c(j), the constant associated with p_(j), from an order statistic of the constants.Source: §D.4 · p. 41
  • Because the p_i are continuous, ties occur with probability zero, so each value corresponds uniquely to its position in the ordered list.The proof defines E_i,j to indicate that p_i occupies position j.Source: §D.4 · p. 42
  • Under the stated uniform-rank condition, the proof uses the random ranking of the p_i values to evaluate the events E_i,j and the associated constants.It then applies the pigeonhole principle and Markov’s inequality in deriving the bound.Source: §D.4 · pp. 41–42

Related papers

Loading 2609.26951v1…