Probabilistic Conformal Prediction with Approximate Conditional Validity

This paper proposes a conformal prediction method to enhance conditional coverage while still ensuring a finite-sample marginal coverage guarantee. The authors consider estimating the conditional distribution of $Y|X$ on the training data and use this estimator to define a localization parameter $\tau$ for each calibration and test sample. These parameters are then used to adjust non-conformity score values. The authors prove the marginal validity of their method and give an inflation bound for the conditional coverage. They also prove the asymptotic conditional validity of their proposed interval in the oracle sense. Experimental results show slight superiority of the proposed method compared with other conditional conformal prediction methods.

The paper offers a new score function for constructing conformal prediction sets to improve adaptivity and approximated conditional coverage.

Instead of explicitly relying on a score function, they use a confidence set function---an idea that is known in the literature. The proposed construction of the prediction set suggests scaling the conformal scores \lambda_k by \tau_k, extracting the 1-alpha quantile Q, and then applying the "inverse scaling" of Q by using f_{\tau}.

Since their method requires estimating Y|X which is generally hard---especially when Y is high dim.---they offer an approach to using a sampling generative model for constructing the prediction sets (Algorithm 1); inspired by Wang et al.

The authors provide a marginal guarantee, approximated conditional coverage (depending on the quality of the estimator), and an asymptotic conditional coverage guarantee.

The authors propose a $\text{CP}^2$ framework for conformal prediction that aims to achieve approximately conditional coverage. The key difference from classical split CP is the introduction of a parameter, $\tau$, defined through either the estimation of the conditional distribution $P_{Y|X}$ or the use of a conditional generative model, allowing for adaptive threshold adjustments. Theoretically, they provide a finite-sample marginal coverage guarantee as well as an asymptotic guarantee through a upper bound on conditional coverage. The framework's efficiency is demonstrated through experiments on both synthetic and real-world data.

This paper achieves powerful conditional coverage via a technique that relies on sampling from an empirical estimate of the underlying conditional data distribution. Their method achieves impressive empirical benefits alongside powerful provable guarantees.

Overall this paper has clear contributions and is very sound. I vote to accept this paper.

This paper looks at the central issue of covariate-conditional validity of conformal prediction methods. They propose a systematic and novel procedure of turning a black box estimation of conditional distributions (Y|X) into a valid conformity score which then can be used to construct prediction sets. They carefully design the procedure to make their prediction sets adaptive to the behavior of the conditional distribution. Their method effectively generalizes the previous literature on using conditional distribution estimation by 1) providing algorithmic and theoretical results targeting conditional coverage and 2) going beyond one-dimensional regression setting.

The authors leverage an estimated conditional distribution $P_{Y|X}$ to construct prediction sets that adapt to the local structure of the data, achieving approximate conditional validity. They define confidence sets $R_z(x; t)$, calibrated using a parameter $\tau_{x,z}$ derived from $P_{Y|X}$, and use conformity scores $\lambda_{x,y,z}$ to ensure these sets dynamically adjust to heteroscedasticity and multimodality. For complex distributions, the method supports unions of high-density regions, enabling effective prediction even in multimodal cases. The framework guarantees approximate conditional coverage, with errors bounded by the total variation distance between the true and estimated conditional distributions, making it robust and adaptable to various machine learning tasks.

As a core technical novelty, the conformity score $\lambda_{x,y,z}$ is defined as the minimum "effort" i.e. size $t$ of the confidence set $R_z(x; t)$ needed to include the observed $y$. Intuitively, This score captures the relationship between the observation $y$ and the local structure of $P_{Y|X}$, allowing the prediction sets to adapt not only to the estimated distribution but also to the specific data point being predicted.

The method is innovative but heavily dependent on high-quality conditional distribution estimators. In a strict sense, the proposed method does not provide fundamentally stronger conditional guarantees than existing methods. Asymptotically, conditional coverage has been established in numerous previous conformal prediction paper as well as consistency analysis for estimation of conditional distribution. So it is pretty difficult to grasp what new problem is being solved in this paper and what new it brings to the current literature.

The paper suffers from significant clarity issues, primarily due to its dense and cluttered presentation. It overloads the reader with mathematical rigor, complex notations, and auxiliary variables without first providing an intuitive understanding of the method, making it difficult to grasp the core ideas. And at the end, we can hardly extract a significant novelty. This is really concerning and I encourage the authors to not obfuscate the readers. All the marginal coverage established in this paper hold directly from well known coverage results in conformal prediction but are presented as a "new result".

While I acknowledge that the paper would benefit greatly from simplifying the exposition and presenting the contributions in a more transparent way, the reviewers' post-rebuttal feedback indicates that the contributions are sound and sufficient for acceptance. The program chairs can weigh these merits alongside the remaining concerns to make the final decision.

Accept (Poster)