PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data

Victor Chernozhukov, Kaspar Wuthrich, Yinchu Zhu

arXiv:1802.06300v3stat.MLcs.LG

TL;DR

The paper addresses prediction sets for future responses in time-series settings. It uses block-structured group randomization to account for serial dependence; the method is exactly valid under exchangeability and approximately valid under stated conditions when exchangeability fails.

  • Problem

    The paper considers how to construct prediction sets for future responses from time-series data at a prespecified miscoverage level.

    Source: §1 · p. 1

  • Method

    The method randomizes data using groups of block-structured permutations and constructs conformal prediction sets from conformity scores.

    Source: §2.1 · p. 2, §4 · p. 9

  • Results

    Under exchangeability the method has exact, model-free coverage validity, while under approximate ergodicity and small score error its conformal p-values are approximately uniform.

    Source: §3.1 · p. 6, §3.2 · p. 7, §4 · p. 9

  • Takeaways & Limitations

    The framework provides conformal prediction with theoretical performance guarantees for dependent data, including time-series settings.

    Source: §1 · pp. 1–2, §4 · p. 9

    When exchangeability fails, approximate validity relies on approximate ergodicity and a small conformity-score error condition.

    Source: §3.2 · p. 7

Abstract

from arXiv · show

We extend conformal inference to general settings that allow for time series data. Our proposal is developed as a randomization method and accounts for potential serial dependence by including block structures in the permutation scheme. As a result, the proposed method retains the exact, model-free validity when the data are i.i.d. or more generally exchangeable, similar to usual conformal inference methods. When exchangeability fails, as is the case for common time series data, the proposed approach is approximately valid under weak assumptions on the conformity score.

1 Introduction

The paper seeks prediction sets for future responses with coverage guarantees across settings that include time series. It extends conformal inference through group-based randomization designed to preserve dependence, establishing theoretical guarantees beyond the exchangeable case.

1 Introduction

  • The paper frames its task as predicting future responses from observed time-series data and constructing prediction sets at a prespecified miscoverage level.Its introduction says the paper presents the setup and permutation schemes, develops theoretical properties, and concludes with a simulation experiment in the appendix.Source: §1 · pp. 1–2
  • The framework targets prediction sets with coverage guarantees across a wide range of settings, including time series.It offers one unified method where problem-specific prediction sets might otherwise be designed.Source: §1 · p. 1
  • Group-based randomization permutes blocks to preserve dependence, while transformations approximating a stationary series support bounds when exchangeability fails.Under i.i.d. or more generally exchangeable data, the method has exact, model-free validity.Source: §1 · p. 1
  • The paper establishes theoretical guarantees for randomization inference in non-i.i.d. settings, covering common time-series models including strongly mixing processes.The introduction contrasts these guarantees with earlier blocking procedures for which it says theoretical results were not provided.Source: §1 · p. 2

2 Conformal Inference for Dependent Data

The section builds prediction sets by testing candidate future responses and inverting permutation-based p-values. It adapts the permutation scheme to dependence through blocks, gives regression and autoregressive conformity-score examples, and discusses computational costs and an inductive variant.

2.1 Conformal Inference by Permutations

  • Candidate future responses augment the data; a conformity score maps the augmented data to a real number, and inversion retains candidates whose p-values exceed α.The score can incorporate general machine-learning algorithms, and candidate values are evaluated on a grid.Source: §2.1 · pp. 2–3

2.2 Designing Permutations Π for Dependent Data

  • Block permutations preserve dependence, using either non-overlapping consecutive blocks or overlapping schemes composed with cyclic sliding operations.The non-overlapping permutations form a group containing the identity map.Source: §2.2 · p. 3

2.3.1 Penalized Regression

  • In penalized regression, the conformity score can use the last T1 fitted residuals; if the estimator is permutation-invariant, p-values can be computed by permuting residuals.The paper notes that this invariance can reduce model fitting to once per candidate response.Source: §2.3.1 · p. 4

2.3.2 Autoregressive Models and Neural Networks

  • For linear and nonlinear autoregressive models, the method estimates autoregressive coefficients or functions and uses fitted residuals for a residual-based conformity score.The nonlinear function may be parametric, nonparametric, or semiparametric, including neural-network time-series models.Source: §2.3.2 · pp. 4–5

2.4 Computational Aspects

  • Computing a p-value may require fitting a model for every permutation and each grid candidate, making grid size and forecast dimension computational considerations.When fitting is permutation-invariant, inductive conformal prediction restricts permutations to the calibration set, needs one model fit, and is covered by the framework's theory for dependent data.Source: §2.4 · p. 5

3 Theory: General Results on Exact and Approximate Conformal Inference

The theory gives exact, model-free validity under exchangeability and approximate finite-sample validity when exchangeability fails, under conditions on the conformity score and transformed-data approximation. It also relates approximate validity to oracle-score estimation and establishes approximate ergodicity for strongly mixing time series with blocking permutations.

3.1 Exact Validity

  • Under exchangeability and invariant randomization quantiles, the method has exact model-free validity; i.i.d. data with a permutation group provide a sufficient condition.The resulting conformal set has coverage at least 1 − α, and the randomization p-value is at most α with probability at most α.Source: §3.1 · p. 6

3.3 Approximate Ergodicity for Strongly Mixing Time Series with Blocking Permutations

  • For strongly mixing time series, the paper establishes approximate ergodicity using both non-overlapping and overlapping blocking permutations.The result is framed as a sufficient condition for ergodicity condition (E).Source: §3.2 · p. 7, §3.3 · p. 8

3.2 Approximate Validity

  • Under small score-approximation error and approximate ergodicity, the generalized method achieves approximate validity, with an approximately uniform conformal p-value.Approximate ergodicity requires permuted oracle scores to approximate their unconditional distribution; the paper describes this condition as holding for strongly mixing time series under its blocking permutations.Source: §3.2 · p. 7
  • With stronger estimation-quality conditions and continuity of the oracle-set boundary, the generalized prediction set approaches the oracle set in symmetric-difference volume.The paper also states that consistent approximation of the oracle score yields a valid set approximately equivalent to inference using that score.Source: §3.2 · pp. 6–7

4 Conclusion

The method uses block-structured permutation groups to account for serial dependence. It is exactly model-free valid under exchangeability and retains finite-sample performance bounds beyond exchangeability under weak conditions.

4 Conclusion

  • Block-structured permutation groups account for potential serial dependence in the data.The method is developed within a general randomization-inference framework.Source: §4 · p. 9
  • For i.i.d. or more generally exchangeable data, the method has exact, model-free validity.Source: §4 · p. 9
  • Without exchangeability, finite-sample performance bounds hold under weak conformity-score conditions when data transformations meaningfully approximate a stationary series.Source: §4 · p. 9

A Proof of Theorem 1

The proof follows standard arguments and uses exchangeability to establish equality in law for the relevant indicators under permutations.

A Proof of Theorem 1

B Proof of Theorem 2

The proof first bounds the difference between the estimated and oracle p-values, then derives the desired result. Its argument uses the event where conditions (A) and (E) hold and bounds on the density of the oracle score.

B Proof of Theorem 2

  • The second claim on coverage bounds follows from the first, and the final step bounds the difference between threshold indicators.The threshold-indicator bound uses the uniform distribution of F(S*(Z)) and the bound in (14).Source: B Proof of Theorem 2 · pp. 11–12
  • The proof proceeds in two steps: bound the empirical and oracle distribution-function difference, then derive the desired result.Source: B Proof of Theorem 2 · p. 11
  • Step 1 bounds the difference between the p-value and oracle p-value on the event where conditions (A) and (E) hold.Source: B Proof of Theorem 2 · p. 11

C Proof of Lemma 1

The proof bounds an expected supremum for a fixed permutation and uses that the bound does not depend on the permutation. It invokes a result of Rio (2017) and Markov’s inequality.

C Proof of Lemma 1

  • The proof bounds E sup_x |Gπ(x)| for a fixed permutation in Π_CSO, applying Proposition 7.1 of Rio (2017).Source: C Proof of Lemma 1 · p. 13
  • Because the bound does not depend on π, the proof applies it across the permutation scheme.The passage states that this permutation-independent bound yields the first result.Source: C Proof of Lemma 1 · p. 14
  • The proof obtains the lemma’s second claim by Markov’s inequality.It also notes that f(z) is concave on [1, K − 1] after verifying its second derivative is negative for z ≥ 1.Source: C Proof of Lemma 1 · p. 14

D Empirical Study

The simulations test conformal prediction intervals in a penalized-regression setting with serial dependence induced by AR(1) errors. Coverage is close to nominal across a wide range of dependence values, with some undercoverage at very high dependence.

D Empirical Study

  • The study uses penalized regression with independent Gaussian features and AR(1) errors to induce serial dependence.LASSO estimates the coefficients, and the procedure uses non-overlapping block permutations; 2,000 simulations are run.Source: D Empirical Study · pp. 14–15, Figure 1 · p. 15
  • Across a wide range of ρ, empirical coverage is close to the nominal 0.9, though very high ρ produces some undercoverage.The simulations overall show favorable finite-sample properties under time-series dependence.Source: D Empirical Study · p. 15

Related papers

Loading 1802.06300v3…