Technical Summary: When Does Trimming Help Conformal Prediction?

Problem Statement

Conformal prediction relies on the exchangeability of calibration and test scores to provide finite-sample coverage guarantees. However, this exchangeability fails under calibration contamination, where the calibration sample is drawn from a mixture distribution $P^\star = (1-\epsilon)P + \epsilon Q$ (with $P$ being the clean target law and $Q$ an unknown contaminating law), while the test point remains drawn from $P$.

A common practitioner response is to trim calibration points with high anomaly scores before computing the conformal quantile. While intuitive, the paper argues that this procedure does not simply "purify" the data. Instead, it transforms the calibration law into a retained law $R$. The validity of the resulting prediction set for the clean target $P$ becomes a transfer problem from $R$ back to $P$. The central question is: Under what conditions does trimming actually improve clean-target coverage, and when does it fail or even degrade performance?

Methodology

The Retained-Law Framework

The authors reframe fixed-threshold trimming not as data purification but as conditioning. Given an anomaly score $S$ and a threshold $t^\star$, the calibration points are retained if $S(Z) \le t^\star$. The resulting retained calibration set is i.i.d. from the retained law:
$$R = P^\star(\cdot \mid S \le t^\star)$$
This law is generally neither the original contaminated law $P^\star$ nor the clean law $P$.

Theoretical Diagnostics

The paper derives an exact finite-sample identity for the marginal clean coverage, which depends on the distribution of the retained count and the relationship between the retained law $R$ and the clean law $P$.

To make this tractable, the authors introduce a scalar transfer gap $d_{R \to P, +} = \sup_t (F^A_R(t) - F^A_P(t))_+$, where $F^A$ denotes the cumulative distribution function (CDF) of the nonconformity score $A$. The coverage guarantee is bounded by:
$$\text{Coverage} \ge [1 - \alpha - d_{R \to P, +}]_+$$

Using the mixture decomposition of $R$, the authors derive a componentwise upper bound on this gap:
$$d_{R \to P, +} \le (1 - \tilde{\epsilon}^\star) \Delta^A_{\text{trim}, +} + \tilde{\epsilon}^\star D_{Q, +}$$
where:

1. $\Delta^A_{\text{trim}, +}$ (Clean-side cost): The distortion of the clean nonconformity score distribution caused by conditioning on retention. The paper proves this is exactly a one-sided covariance between the retention indicator and the nonconformity score under the clean law $P$.
2. $\tilde{\epsilon}^\star$ (Retained mixture coefficient): The effective contamination level in the retained set, given by $\tilde{\epsilon}^\star = \frac{\epsilon p_d}{(1-\epsilon)p_c + \epsilon p_d}$, where $p_c$ and $p_d$ are the retention probabilities for clean and dirty points, respectively.
3. $D_{Q, +}$ (Retained dirty discrepancy): The discrepancy between the retained dirty component and the clean target.

Key Theoretical Insights

• Covariance Identity: The cost of trimming clean data is driven by the dependence between the anomaly score $S$ and the nonconformity score $A$ under $P$. If $S$ and $A$ are independent under $P$ (e.g., covariate-only scores in homoscedastic regression), the clean-side cost is zero.
• Coefficient-Level Separation Dichotomy: Trimming reduces contamination only if the anomaly score separates clean and dirty points ($p_d \ll p_c$). If $p_d \approx p_c$, then $\tilde{\epsilon}^\star \approx \epsilon$, and trimming cannot reduce the mixture coefficient. In this "no-separation" regime, trimming may strictly worsen coverage by introducing clean-side distortion without reducing contamination.
• Finite-Sample Sharpness: The scalar lower bound is shown to be minimax optimal within the class of problems defined solely by the scalar discrepancy constraint. No uniform lower bound using only the scalar gap can exceed this value.

Certificate Templates

Since population quantities are unknown in practice, the paper provides certificate templates for numerical guarantees:

1. Componentwise Audit: Bounding the ingredients ($p_c, p_d, \Delta^A_{\text{trim}, +}, D_{Q, +}$) using independent information (e.g., clean audit samples or domain knowledge).
2. Direct Audit: Using an independent clean audit sample to certify the final selected set via exact binomial inversion or Kolmogorov-Smirnov bounds.
3. Same-Sample Selection: A finite-grid empirical-CDF bound is provided for cases where the threshold is selected from the same calibration sample, incurring a $\sqrt{\log K / N}$ penalty.

Experimental Results

The authors evaluate the theory on a heteroscedastic regression task with covariate-geometric contamination.

• Score-Visible Regime: When the anomaly score (Stein score-norm) effectively separates the covariate distributions of clean and dirty data, trimming significantly improves coverage. The improvement is driven by a reduction in the retained mixture coefficient $\tilde{\epsilon}^\star$ (which drops to near zero) and a manageable clean-side cost.
• No-Separation Regime: When clean and dirty points have similar retention probabilities, trimming fails to reduce $\tilde{\epsilon}^\star$. Coverage remains low, confirming that trimming cannot help without separation.
• Label-Only Contamination: When only the response $Y$ is corrupted (and $X$ is clean), covariate-based trimming has no leverage. The method correctly identifies that trimming cannot improve coverage in this setting.
• Large Sample Size: Increasing the calibration size $m$ reduces finite-sample slack but does not eliminate the population-level coverage deficit caused by the retained-law transfer gap. The limiting coverage is governed by the population diagnostics, not sample size.

Significance and Claims

The paper claims to provide a population-level diagnostic that explains when and why trimming helps, moving beyond the heuristic belief that "removing outliers always helps."

1. Reframing Trimming: It establishes that trimming is a transformation of the calibration law, not a restoration of the original law. Validity is exact only for the retained law, requiring a transfer to the clean target.
2. Design Principles: It formalizes that a good anomaly score for trimming must be score-neutral on the clean population (minimizing covariance with the nonconformity score) while being separative between clean and dirty populations.
3. Limitations: It demonstrates that trimming cannot reduce contamination through the mixture coefficient if the score fails to separate retention probabilities. In such cases, trimming may strictly degrade performance.
4. Operational Safety: The paper distinguishes between population diagnostics (mechanistic explanations using known simulation laws) and numerical certificates (guarantees requiring independent audit data), ensuring that practitioners do not mistake theoretical bounds for data-driven certificates without proper auditing.

The work concludes that trimming is not a universal fix for contamination; its efficacy is strictly governed by the interplay between the anomaly score's ability to separate contamination and its neutrality toward the clean target distribution.