Exact and Approximate Conformal Inference for Multi-Output Regression

Chancellor Johnstone, Eugène NdiayeCOPA 2025 · OpenReview

TL;DR

This paper tackles the challenge of quantifying uncertainty in multi-output regression, a common task in machine learning. The authors introduce novel methods, including exact p-value derivations and efficient approximations like rootCP and unionCP, to generate reliable prediction sets for multiple response variables simultaneously, significantly improving computational efficiency over existing approaches.

What Problem Does This Paper Address?

In machine learning, predicting a response variable ($y$) based on input features ($x$) is a fundamental task. However, standard prediction models often provide point estimates without quantifying the uncertainty associated with these predictions. This is particularly problematic when dealing with multiple response variables (multi-output or multi-task regression), where understanding the joint uncertainty is crucial. Conformal inference offers a principled way to construct prediction sets that guarantee a certain coverage probability, but it can be computationally expensive, especially in high dimensions. This paper aims to bridge this gap by developing efficient exact and approximate conformal inference methods specifically for multi-output regression.

Methods

The paper introduces several key methodological contributions:

  • Exact Conformal Inference for Linear Models: The authors extend the work of Nouretdinov et al. (2001) to derive exact conformal p-values for multi-output regression when the predictive model is a linear function of the response variables. This involves defining "p-value change-point sets" that precisely delineate where rank changes occur in conformity scores.
  • Multivariate Extension of rootCP: They propose a multivariate extension of the rootCP algorithm, originally designed for one-dimensional problems. This method efficiently finds points on the boundary of conformal prediction sets by using directional root-finding, reducing the need for extensive model refitting.
  • unionCP Approximation: A novel approximation method called unionCP is introduced. It leverages the union of individual p-value change-point sets to construct conservative conformal prediction sets, offering a computationally efficient alternative for approximating the true prediction region.
  • Conformity Measures: The paper explores conformity measures based on norms, particularly the $L_2$ norm (Mahalanobis distance) and $L_1$ norm, and shows how these lead to quadratic or piecewise linear conformity scores, respectively, enabling efficient computation.

Datasets

The authors evaluate their methods on three multi-output regression datasets:

  • enb: Features: 8, Responses:
  • Source: Tsanas and Xifara (2012).
  • jura: Features: 13, Responses:
  • Source: Goovaerts (1997).
  • cement: Features: 7, Responses:
  • Source: Yeh (2007).

These datasets are used to compare the empirical coverage and computational efficiency of their proposed methods against existing benchmarks.

Key Insights and Ideas

  • Bridging Exactness and Efficiency: The core insight is that by carefully analyzing the structure of conformity scores (especially for linear models or specific norms), it's possible to derive exact p-values or efficiently approximate prediction set boundaries without the prohibitive cost of full conformal inference.
  • Multivariate rootCP is a Game Changer: Extending rootCP to multiple dimensions is a significant step, as it allows for efficient boundary searching in high-dimensional prediction spaces, a major bottleneck in previous methods.
  • unionCP offers a Practical Approximation: The unionCP method provides a computationally feasible way to obtain conservative prediction sets, which is crucial when exact methods are too slow or complex.
  • Trade-off Management: The work highlights the classic trade-off between prediction set volume (accuracy) and computational cost, showing how their methods can achieve competitive results with significantly reduced computation compared to full conformal prediction.

Key Results

  • Empirical Coverage: The unionCP method, when compared to a randomized selection of p-value change-point sets, demonstrated well-calibrated prediction sets, while the randomized approach tended to overcover.
  • Computational Efficiency: The proposed rootCP and unionCP methods significantly reduce computational requirements compared to full conformal prediction (fullCP). For rootCP, the results show it is competitive with splitCP and often surpasses it in terms of prediction set volume, offering a better trade-off.
  • Model Versatility: The methods were tested with various predictors, including linear regression, Nadaraya-Watson (local constant), and local linear regression, demonstrating their applicability across different model types.

Limitations and Future Work

  • Theoretical Guarantees: The authors acknowledge that further theoretical guarantees are needed, particularly regarding the precise characterization of the number of points required to sample on the conformal set boundary for accurate approximations.
  • High-Dimensional Responses: While the methods extend to multiple dimensions, their performance in extremely high-dimensional response spaces (beyond the tested datasets) might require further investigation.
  • Dependence and Covariate Shift: Future work could explore the performance of these approximations under conditions of dependence between response variables or covariate shift.
  • Other Conformity Measures: The paper focuses on specific conformity measures ($L_1$, $L_2$). Investigating the performance and computational feasibility with other conformity measures could be beneficial.

Summary updated

Abstract

It is common in machine learning to estimate a response $y$ given covariate information $x$. However, these predictions alone do not quantify any uncertainty associated with said predictions. One way to overcome this deficiency is with conformal inference methods, which construct a set containing the unobserved response with a prescribed probability. Unfortunately, even with a one-dimensional response, conformal inference is computationally expensive despite recent encouraging advances. In this paper, we explore multi-output regression, delivering exact derivations of conformal inference p-values when the predictive model can be described as a linear function of $y$. Additionally, we introduce a multivariate extension of rootCP as well unionCP as efficient ways of approximating the conformal prediction region for a wide array of multi-output predictors, both linear and nonlinear, while preserving computational advantages. We also provide both theoretical and empirical evidence of the effectiveness of our methods using both real-world and simulated data.
BibTeX
@inproceedings{johnstone2025exact,
  author = {Chancellor Johnstone and Eugène Ndiaye},
  title = {{Exact and Approximate Conformal Inference for Multi-Output Regression}},
  booktitle = {COPA},
  year = {2025},
  url = {https://openreview.net/forum?id=vY232C4VH4},
}
Figure