Conformal Prediction Regions for Time Series using Linear Complementarity Programming
This addresses the issue of conservative uncertainty quantification for time series data in safety-critical applications like robotics and autonomous systems, representing an incremental improvement over prior methods.
The paper tackles the problem of overly conservative prediction regions in conformal prediction for time series, which hinders long-horizon planning and verification. It proposes an optimization-based method that reduces conservatism by parameterizing prediction errors over multiple time steps, demonstrating efficacy in case studies with pedestrian trajectory and F16 fighter jet predictors.
Conformal prediction is a statistical tool for producing prediction regions of machine learning models that are valid with high probability. However, applying conformal prediction to time series data leads to conservative prediction regions. In fact, to obtain prediction regions over $T$ time steps with confidence $1-δ$, {previous works require that each individual prediction region is valid} with confidence $1-δ/T$. We propose an optimization-based method for reducing this conservatism to enable long horizon planning and verification when using learning-enabled time series predictors. Instead of considering prediction errors individually at each time step, we consider a parameterized prediction error over multiple time steps. By optimizing the parameters over an additional dataset, we find prediction regions that are not conservative. We show that this problem can be cast as a mixed integer linear complementarity program (MILCP), which we then relax into a linear complementarity program (LCP). Additionally, we prove that the relaxed LP has the same optimal cost as the original MILCP. Finally, we demonstrate the efficacy of our method on case studies using pedestrian trajectory predictors and F16 fighter jet altitude predictors.