PaperlayerView exact revision on arXiv

Source-linked AI summary

Conformal Prediction Regions for Continuous-Time Trajectories under Random Sampling

Joaquin Alvarez, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

arXiv:2608.29559v1eess.SY

TL;DR

Discrete, sparse, and random trajectory sampling leaves standard conformal prediction without guarantees between observations, despite the importance of continuous-time safety. The paper uses trajectory regularity, high-frequency calibration, and random-time procedures to construct continuous-time conformal regions, with experiments validating coverage across the trajectory.

  • Problem

    Standard conformal prediction typically provides guarantees only at discrete sampling times, leaving continuous-time trajectory coverage unresolved under sparse or random observations.

  • Method

    The paper propagates discrete-time conformal regions using trajectory regularity, estimates regularity from an additional high-frequency calibration dataset, and introduces methods for random sampling times.

  • Results

    The experiments validate that the proposed methods achieve valid coverage across the entire continuous trajectory.

  • Takeaways & Limitations

    The framework provides fully data-driven continuous-time prediction regions without making model assumptions, while supporting discrete and possibly random sampling.

  • Takeaways & Limitations

    The approach relies on a Lipschitz regularity condition and excludes some standard continuous-time processes, such as Brownian motion.

Abstract

from arXiv · show

Uncertainty quantification for continuous-time trajectories is a prerequisite in many safety-critical engineering domains. However, a major challenge in data-driven uncertainty quantification is that calibration trajectories are sampled only at discrete, often sparse, and random intervals. Standard conformal prediction methods typically fail to provide guarantees in between sampling times. In this work, we introduce a new technique to obtain valid conformal prediction regions for continuous-time trajectories that are sampled at discrete and possibly random times. To accomplish this goal, we make three contributions: (1) we provide an algorithm that leverages regularity properties of the underlying trajectories to obtain valid prediction regions in between samples, (2) we provide methods that estimate valid bounds on the aforementioned regularity properties from an additional high-frequency calibration dataset, and (3) we introduce and compare several algorithms to deal with random sampling times. Finally, we present experiments where we validate that our methods achieve valid coverage across the entire continuous trajectory.

1 Introduction

The paper addresses the challenge of constructing valid continuous-time prediction regions when trajectories are observed only at discrete, sparse, and possibly random intervals. It extends conformal prediction with trajectory regularity estimation and methods for random sampling.

  • Discrete observations can leave safety violations undetected between consecutive sampling times.The paper motivates this issue with examples including networked control, aviation, medical decision support, and adaptive ODE solvers.
  • Prior conformal prediction methods provide discrete-time trajectory regions but are generally limited to discrete domains.These methods address temporal dependence that violates exchangeability assumptions typically needed for conformal prediction.
  • The proposed technique constructs continuous-time prediction regions under discrete and possibly random sampling without model assumptions.It uses trajectory regularity properties to extend guarantees between observed samples.
  • The method estimates trajectory regularity from finite samples by downsampling high-frequency trajectories and using a stochastic dominance assumption.This additional calibration procedure is intended to keep the approach fully data-driven.
  • The paper introduces multiple approaches for obtaining valid prediction regions when sampling times are random.

2 Related Work

Related work includes discrete- and online-time conformal prediction, safety-critical control, reachability, Gaussian processes, and functional data analysis. These approaches differ in their time-domain coverage, data requirements, computational costs, and structural assumptions.

  • Adaptive conformal inference handles exchangeability violations from trajectory data using past observation windows, but guarantees asymptotic rather than simultaneous coverage.It has also not been studied for continuous-time trajectories.
  • Existing conformal methods for safety-critical continuous-time control commonly assume access to continuous-time calibration trajectories.The paper positions its approach as complementary because it does not make that assumption.
  • Dynamic programming methods for stochastic reachability can be exact but are typically computationally expensive and require knowledge of the system’s underlying randomness.
  • Gaussian-process and functional-data approaches model or smooth inter-sample behavior but impose structural assumptions, distributional priors, or model parameters.

3 Problem Formulation

The problem is to construct prediction regions for continuous-time test trajectories from calibration data observed at discrete sampling times that may themselves be random. The target region must cover the trajectory across the full domain [0, T*].

  • The framework models a continuous-time trajectory X on [0, T*] together with a discrete sampling set T whose size may be random.
  • Observed data consist of sampled trajectory states paired with their sampling times.The observable pair is represented as Z = (X, T), with its distribution induced by the joint trajectory-and-sampling distribution.
  • Calibration data comprise m i.i.d. observable trajectory-and-sampling pairs.
  • The goal is to use the calibration dataset to construct continuous-time prediction regions for a new test trajectory.
  • Unlike prior fixed-time formulations, the objective requires regions over [0, T*] even when test sampling times are random.

4 Prediction Regions under Deterministic Sampling and Known Lipschitz Constant

Under deterministic sampling and a known Lipschitz constant, the paper first builds conformal regions at sampled times and then propagates them between samples. Forward and backward Lipschitz regions are intersected to obtain continuous-time coverage.

  • The method assumes deterministic known sampling times and a known Lipschitz constant L describing trajectory regularity.
  • The regularity condition excludes some continuous-time processes, including Brownian motion, while covering physical systems with bounded velocities and random or neural ODE dynamics.
  • Discrete-time conformal regions are built from normalized nonconformity scores using an empirical quantile.The predictor and normalizing function define the score, and split conformal prediction supplies the quantile-based calibration step.
  • The algorithm propagates sampled-time regions forward and backward using L, then intersects the resulting cones between sampling times.This intersection defines the continuous-time prediction region.
  • The algorithm includes a tightening pass that replaces a later sampled region when the propagated earlier region is tighter.
  • If the discrete-time coverage event and Lipschitz-bound event both hold, their intersection is contained in the continuous-time coverage event.
  • Theorem 1 establishes that the constructed regions satisfy the target continuous-time coverage under the discrete-time guarantee and condition (3) for known L.

5 Prediction Regions with Estimated Trajectory Regularity Properties

The paper estimates trajectory regularity from high-frequency calibration data when the true continuous-time bound is unavailable, then uses that estimate to construct continuous-time prediction regions. It develops gap-based and sum-based estimators under stochastic-dominance assumptions and proves their validity for Algorithm 1.

  • 5.1 Oracle Setting: The oracle approach estimates the maximum time-derivative bound with conformal prediction and uses it in Algorithm 1 to recover analogous guarantees.The estimate ˆLoracle is calibrated from trajectory regularity quantities and can replace the known Lipschitz constant.
  • 5.2 Gap Stochastic Dominance: In practice, high-frequency calibration trajectories bridge the gap between observable sparse-sampling slopes and the unobservable continuous-time maximum derivative.The method uses high-frequency data during calibration; the test trajectory need not be sampled at high frequency.
  • 5.2 Gap Stochastic Dominance: Under Assumption 1, the hidden gap is stochastically dominated by the observed gap, motivating a gap-based estimator of the regularity parameter.Dense sampling is described as capturing maximum slopes more accurately, while sparse sampling can miss sharp variations.
  • 5.2 Gap Stochastic Dominance: The gap-based estimate ˆLgap can be supplied to Algorithm 1 to obtain continuous-time prediction regions with the theorem’s coverage guarantee.The proof combines the regularity event from Lemma 2 with discrete-time conformal coverage and a union bound.
  • 5.3 Sum Stochastic Dominance: An alternative estimator ˆLsum uses stochastic dominance involving the high-frequency maximum slope and sampling gaps, with reliability-efficiency tradeoffs compared against Assumption 1.Lemma 3 establishes validity for ˆLsum, and the paper compares the two assumptions experimentally and in discussion.

6 Prediction Regions under Random Sampling

This section develops four continuous-time prediction-region methods for unknown random sampling times, distinguished by their assumptions about sampling distributions, synthetic times, and trajectory regularity. The methods propagate discrete-time guarantees across the continuous domain and include approaches that avoid knowing the sampling distribution or a Lipschitz constant.

  • Method roadmap: Four methods address unknown test sampling times under different assumptions, with Table 1 comparing Lipschitz-constant reliance, synthetic sampling times, and sampling-distribution requirements.Fig. 3 provides a complementary decision chart for selecting a method based on the sampling regime and available assumptions.
  • Exact Test Sample Imputation: Exact Test Sample Imputation samples synthetic times from P_T and requires independence between trajectories and sampling times.Under these conditions, imputed trajectory-time pairs are i.i.d. with calibration data, enabling split conformal prediction; the method is described as an oracle because its assumptions are strong.
  • Calibrated imputation: Imputed-time prediction regions can be propagated over [0, T*] using a known Lipschitz constant L, while calibrated imputations address mismatch between synthetic and true sampling times.The nonconformity score includes L, so estimating L requires additional care and can be handled jointly as described in Appendix B.
  • Stochastic dominance: When synthetic-time distribution knowledge is available, stochastic-dominance methods use high-frequency trajectories to control unseen continuous-time error through nonconformity-score assumptions.The framework distinguishes hidden high-frequency error from observable lower-frequency error and develops gap- and sum-dominance variants.
  • Stochastic dominance: An oracle stochastic-dominance region uses observable continuous-time nonconformity scores with a split-conformal quantile, while practical variants estimate corresponding dominance-based quantiles.The oracle threshold yields validity by standard split conformal prediction.
  • Distribution-free alternative: A stochastic-dominance method can avoid knowing the sampling-time distribution, accommodate trajectory-dependent sampling, and require no Lipschitz constant.The same approach may also apply to fixed sampling times because it does not inherently require randomness in the sampling schedule.

7 Experiments

Experiments evaluate prediction regions under fixed and random sampling, validate stochastic dominance assumptions, and examine the tradeoff between coverage, robustness, and conservatism. The methods produce tighter regions with denser random sampling and achieve the target coverage in the reported setup.

  • Experimental setup: Euler discretization is used to study prediction regions for a one-dimensional dynamical system under fixed and random sampling.The experiments fit cubic-spline point predictors to 1,000 training trajectories and use clipped velocities with known L = 1/100.
  • Assumption validation: The gap and sum methods are empirically evaluated using continuous-trajectory CDFs and subsampled surrogates across downsampling frequencies.Shaded regions show 2 standard deviations across 10 independent calibration samples with m = 200.
  • Assumption validation: Subsampling faithfully represents oracle gap behavior, while larger h = 0.15 gives tighter Lipschitz estimates but can compromise Assumption 1.High-frequency sampling at h = 0.02 prioritizes robustness of stochastic dominance at the expense of conservative estimation.
  • Lipschitz estimation: The sum-based Lipschitz estimate is typically no larger than the gap-based estimate because splitting α makes the gap method more sensitive to tail behavior.The comparison uses 100 independent predictions based on 200 calibration trajectories per estimate.
  • Coverage: With target coverage 1 −δ = 0.90, the error budget allocates δ/2 = 0.05 to discrete-time intervals and 0.05 to Lipschitz prediction.All methods safely overestimate L = 1/100 in this experiment, so final coverage is attributed to the discrete-time conformal regions.
  • Random sampling times: Prediction regions become tighter as uniform random sampling becomes denser, and this pattern is reflected in coverage evaluations across sparsity levels.Random sampling uses N ∈ {50, 80, 100, 200} uniform samples on [0, 10].

8 Discussion

The discussion identifies a central assumption and a practical tradeoff in the proposed approach. Assumption 1 is supported more often than Assumption 2, but produces more conservative prediction regions.

  • Assumptions: Most methods assume a Lipschitz constant for the test trajectory, and dense trajectories can be downsampled to provide the additional sparse calibration data.The proposed Lipschitz estimation method requires an additional calibration dataset, which may impose no additional cost in moderately dense regimes.
  • Limitations and future work: A remaining challenge is identifying sampling conditions that satisfy either stochastic dominance assumption while avoiding unnecessary conservatism.The hidden gap ∆hidden remains unobservable by construction, motivating future work on principled sampling.

A Results for the Gap Stochastic Dominance Assumption

The analysis establishes when observable gap differences support the gap stochastic dominance assumption. As sampling becomes sufficiently dense, discrete Lipschitz estimates approach the continuous-time constant and observed gaps dominate hidden gaps.

  • For continuously differentiable trajectories, discrete Lipschitz estimates converge to the continuous Lipschitz constant as grid spacing h approaches zero.The result uses dense grids whose mesh is at most h and the maximum derivative magnitude over the continuous domain.
  • The non-degeneracy condition holds whenever the low-frequency grid misses the exact time of maximum derivative magnitude.The authors identify constant-velocity trajectories as an adversarial case, although any sampling frequency still recovers their Lipschitz constant.
  • Almost-sure dominance at high frequencies implies stochastic dominance, providing theoretical support for Assumption 1.The theoretical argument explains why the assumption becomes reasonable under sufficiently fine sampling.
  • High-frequency grids make observed gap differences non-negative almost surely, whereas sparse grids can violate this dominance relationship.In the reported simulations, all observed gap differences were non-negative for h ∈ {0.02, 0.05}.

B Calibrated Envelopes with an Estimated Lipschitz Constant

Estimated Lipschitz constants are incorporated into calibrated envelopes without sacrificing exchangeability. The method splits calibration data so estimation and nonconformity scoring use disjoint subsets, yielding continuous-domain coverage.

  • Reusing calibration data to estimate the Lipschitz constant and compute scores violates exchangeability between calibration and test scores.The test score depends on a threshold estimated only from the calibration dataset.
  • The calibration dataset is partitioned into D_L and D_S, with D_L estimating an upper bound and D_S computing envelope nonconformity scores.The estimated bound is then fixed while the scoring subset is used for conformal calibration.
  • Conditional exchangeability is restored given D_L, so split conformal prediction provides the stated marginal validity guarantee.The argument conditions on the data used to estimate the threshold and then marginalizes over that dataset.
  • The resulting envelope propagates discrete prediction regions across the full interval [0,T*] using the estimated Lipschitz bound.The construction ensures the test trajectory remains inside the envelope throughout the continuous domain when the score and split events hold.

C Empirical Validation of the Stochastic Dominance Assumption

The paper proposes observable surrogate gaps to empirically assess stochastic dominance without continuous ground-truth trajectories. These surrogates generally track oracle behavior, while denser sampling tends to strengthen dominance.

  • The hidden gap is unobservable, motivating two observable sampling regimes for empirical validation of downsampling behavior.The procedure checks whether dominance persists across observable scales rather than directly measuring the continuous-time hidden gap.
  • Consistent dominance across observable scales provides empirical evidence that the selected grid resolution is faithful to the stochastic dominance assumption.The surrogate CDF pipeline is compared with oracle continuous-data CDFs in the experiments.
  • Surrogate hidden gaps compare fine-to-coarse quantities, such as L_full − L_mid, against the observed gap.An analogous construction compares S_full − S_mid when dominance is assessed directly on nonconformity scores.
  • Larger subsampling ratios generally make stochastic dominance hold more strongly, while the surrogate comparisons remain a proxy for oracle behavior.The experiments use trajectories from robotics-inspired DMPs and compare prediction regions across sampling sparsity levels.

D.2 R¨ossler Attractor

The Rössler-attractor experiments examine random adaptive sampling and multiple downsampling regimes. Denser observations produce tighter regions and generally improve dominance validation, while surrogate diagnostics can be optimistic.

  • Random sampling arises because trajectory-specific Rössler parameters alter spike timing, curvature, and stiffness, causing the adaptive solver to choose different step sizes.The trajectories are generated with randomly perturbed system parameters and solved using an adaptive ODE method.
  • Sparse+ retains approximately 6.7% of solver-grid points, while Dense+ retains 25%, creating substantially different observation regimes.The four regimes use downsampling steps k ∈ {15,10,5,4}.
  • Denser downsampling yields tighter prediction regions and higher reflected coverage because observable gaps more closely approximate hidden gaps.The reported comparison identifies Sparse+ as more conservative than Dense+ and links this to retained sampling density.
  • Violating gap dominance does not necessarily eliminate reliable coverage because the gap method is more conservative through a union bound and split error budget.For N = 500, target coverage was still achieved despite Assumption 1 not being satisfied.
  • Surrogate validation tracks oracle dominance behavior but can deviate from oracle CDFs and favor apparent dominance when it is not satisfied.This optimistic bias is reported for the sum-dominance validation, while gap validation remains faithful for detecting violations in Dense+.
Loading 2608.29559v1…