# Conformal Prediction Regions for Time Series using Linear Complementarity Programming

arXiv: https://arxiv.org/abs/2304.01075 · HTML: https://mlsanity.com/paper/2304.01075/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 3 Apr 2023.

## Builds on (most cited first, 23 of 23)

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Human Trajectory Forecasting in Crowds: A Deep Learning Perspective](https://mlsanity.com/paper/2007.03639/) (2020)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Safe Planning in Dynamic Environments using Conformal Prediction](https://mlsanity.com/paper/2210.10254/) (2022)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Conformal Prediction Under Feedback Covariate Shift for Biomolecular Design](https://mlsanity.com/paper/2202.03613/) (2022)
- [Adaptive Conformal Prediction for Motion Planning among Dynamic Agents](https://mlsanity.com/paper/2212.00278/) (2022)
- [Sample-Efficient Safety Assurances using Conformal Prediction](https://mlsanity.com/paper/2109.14082/) (2021)
- [Conformal Prediction for STL Runtime Verification](https://mlsanity.com/paper/2211.01539/) (2022)
- [Copula Conformal Prediction for Multi-step Time Series Forecasting](https://mlsanity.com/paper/2212.03281/) (2022)
- [iDECODe: In-distribution Equivariance for Conformal Out-of-distribution Detection](https://mlsanity.com/paper/2201.02331/) (2022)
- [Physics Constrained Motion Prediction with Uncertainty Quantification](https://mlsanity.com/paper/2302.01060/) (2023)
- [Guaranteed Dynamic Scheduling of Ultra-Reliable Low-Latency Traffic via Conformal Prediction](https://mlsanity.com/paper/2302.07675/) (2023)
- [Moving Obstacle Avoidance: a Data-Driven Risk-Aware Approach](https://mlsanity.com/paper/2203.14913/) (2022)
- [Reliable Prediction Intervals with Directly Optimized Inductive Conformal Regression for Deep Learning](https://mlsanity.com/paper/2302.00872/) (2023)
- [Solving Linear Programs with Complementarity Constraints using Branch-and-Cut](https://mlsanity.com/paper/1802.02941/) (2018)

## Built on by (most cited first, 30 of 33)

- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Conformal Temporal Logic Planning using Large Language Models](https://mlsanity.com/paper/2309.10092/) (2023)
- [Forking Uncertainties: Reliable Prediction and Model Predictive Control with Sequence Models via Conformal Risk Control](https://mlsanity.com/paper/2310.10299/) (2023)
- [Probabilistically Correct Language-based Multi-Robot Planning using Conformal Prediction](https://mlsanity.com/paper/2402.15368/) (2024)
- [Data-Driven Reachability Analysis of Stochastic Dynamical Systems with Conformal Inference](https://mlsanity.com/paper/2309.09187/) (2023)
- [Conformalized Interval Arithmetic with Symmetric Calibration](https://mlsanity.com/paper/2408.10939/) (2024)
- [Learnable Conformal Prediction with Context-Aware Nonconformity Functions for Robotic Planning and Perception](https://mlsanity.com/paper/2509.21955/) (2025)
- [PAC-Bayes Generalization Certificates for Learned Inductive Conformal Prediction](https://mlsanity.com/paper/2312.04658/) (2023)
- [Conformal Predictive Programming for Chance Constrained Optimization](https://mlsanity.com/paper/2402.07407/) (2024)
- [Bridging Dimensions: Confident Reachability for High-Dimensional Controllers](https://mlsanity.com/paper/2311.04843/) (2023)
- [Multi-Modal Conformal Prediction Regions with Simple Structures by Optimizing Convex Shape Templates](https://mlsanity.com/paper/2312.07434/) (2023)
- [Statistical Reachability Analysis of Stochastic Cyber-Physical Systems under Distribution Shift](https://mlsanity.com/paper/2407.11609/) (2024)
- [Adaptive Conformal Inference by Particle Filtering under Hidden Markov Models](https://mlsanity.com/paper/2411.01558/) (2024)
- [JAPAN: Joint Adaptive Prediction Areas with Normalising-Flows](https://mlsanity.com/paper/2505.23196/) (2025)
- [Split Conformal Prediction in the Function Space with Neural Operators](https://mlsanity.com/paper/2509.04623/) (2025)
- [Conformal Off-Policy Prediction for Multi-Agent Systems](https://mlsanity.com/paper/2403.16871/) (2024)
- [JANET: Joint Adaptive predictioN-region Estimation for Time-series](https://mlsanity.com/paper/2407.06390/) (2024)
- [Reliable uncertainty quantification for 2D/3D anatomical landmark localization using multi-output conformal prediction](https://mlsanity.com/paper/2503.14106/) (2025)
- [Probabilistic Robustness Analysis in High Dimensional Space: Application to Semantic Segmentation Network](https://mlsanity.com/paper/2509.11838/) (2025)
- [Conformal Prediction for Signal Temporal Logic Inference](https://mlsanity.com/paper/2509.25473/) (2025)
- [Conformal Prediction in The Loop: A Feedback-Based Uncertainty Model for Trajectory Optimization](https://mlsanity.com/paper/2510.16376/) (2025)
- [Deterministic World Models for Closed-loop Reachability Analysis of End-to-End Vision-based Control](https://mlsanity.com/paper/2512.08991/) (2025)
- [When Environments Shift: Safe Planning with Generative Priors and Robust Conformal Prediction](https://mlsanity.com/paper/2602.12616/) (2026)
- [Single Trajectory Conformal Prediction](https://mlsanity.com/paper/2406.01570/) (2024)
- [Conformalised Conditional Normalising Flows for Joint Prediction Regions in time series](https://mlsanity.com/paper/2411.17042/) (2024)
- [Uncertainty-Calibrated Prediction of Randomly-Timed Biomarker Trajectories with Conformal Bands](https://mlsanity.com/paper/2511.13911/) (2025)
- [Conformal Safety Monitoring for Flight Testing: A Case Study in Data-Driven Safety Learning](https://mlsanity.com/paper/2511.20811/) (2025)
- [Feature Fitted Online Conformal Prediction for Deep Time Series Forecasting Model](https://mlsanity.com/paper/2505.08158/) (2025)
- [AdaptNC: Adaptive Nonconformity Scores for Conformal Prediction under Distribution Shift](https://mlsanity.com/paper/2602.01629/) (2026)

## Abstract (arXiv)

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.