📊 statistics

Online Selective Conformal Prediction with Asymmetric Rules: A Permutation Test Approach

This paper proposes PErmutation-based Mondrian Conformal Inference (PEMI), a general framework that achieves exact selection-conditional coverage for online selective conformal prediction by using a permutation-based approach to handle arbitrary asymmetric selection mechanisms.

Original authors: Mingyi Zheng, Ying Jin

Published 2026-02-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mingyi Zheng, Ying Jin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a talent scout for a major music label. You have a massive pile of demo tapes arriving one by one every day. You don't have the time or money to sign everyone, so you only "select" the artists who meet certain criteria—maybe they have a certain energy, or they've already gained some traction on social media.

The problem is this: The very act of being picky changes the math.

If you only sign artists who are already popular, your "average" artist is going to look much better than the general population. If you try to use standard statistics to predict how successful a new artist will be, your predictions will be wildly over-optimistic because you ignored all the "failures" you skipped over.

This paper, "Online Selective Conformal Prediction with Asymmetric Rules," solves this exact problem for data scientists.

The Problem: The "Selection Bias" Trap

In machine learning, we often use "Conformal Prediction" to give not just a single answer (like "this house costs \ $500k"), but a **range of uncertainty** (like "we are 95% sure this house costs between \$ 450k and $550k").

However, in the real world, we often only ask for these ranges when the computer is "interested" in a specific case. For example:

A doctor only asks for a risk assessment if a patient shows specific symptoms.
A scientist only tests a drug if the initial computer model looks promising.

Because the decision to "look" is based on the data itself, the standard rules of probability break. The "uncertainty ranges" become unreliable—they might be too narrow, making you overconfident, or too wide, making them useless.

The Challenge: The "Order Matters" Problem

Previous solutions tried to fix this by "swapping" data points around to see if the selection would still happen. But those methods assumed that the order in which data arrives doesn't matter.

In the real world, order matters immensely. Imagine a stock market algorithm. If a massive crash happens on Monday, the algorithm's decision to trade on Tuesday is completely different than if that crash had happened on Friday. The "history" of what happened before changes the rules of the game. This is what the authors call asymmetry.

The Solution: PEMI (The "Parallel Universe" Approach)

The authors propose a new framework called PEMI (PErmutation-based Mondrian Conformal Inference).

Think of PEMI like a "Multiverse Simulator."

When a new piece of data arrives and the system decides, "Yes! This is interesting, let's make a prediction," PEMI doesn't just look at that one moment. Instead, it runs thousands of "What If" simulations in a digital multiverse.

The Shuffle: It takes all the data it has seen so far and shuffles the order of the days/events in thousands of different ways.
The Filter: It looks through these thousands of parallel universes and asks: "In which of these universes would the selection rule have made the exact same decision we just made?"
The Calibration: It ignores all the universes where the decision would have been different. It only looks at the "Parallel Universes" that match our reality.
The Prediction: It calculates the uncertainty range based only on those matching universes.

By doing this, PEMI "corrects" for the fact that we were picky. It essentially says, "Since we only picked this specific case, we must adjust our expectations to account for the fact that we ignored all the other cases that didn't look like this."

Why does this matter? (The "Drug Discovery" Example)

The authors tested this on a real-world problem: Drug Discovery.

Scientists are constantly testing new chemical compounds to see if they will bind to a disease target. They don't test everything; they only test the "winners" that look promising.

If they used standard math, they would be constantly surprised when a "promising" drug fails in the lab because their uncertainty ranges were too optimistic. Using PEMI, the scientists get a "honest" range of uncertainty. Even when they are being highly selective and picky, the math stays "valid"—meaning the true answer stays within the predicted range exactly as often as promised.

Summary in a Nutshell

The Old Way: "I'll tell you the range of possibilities, assuming I'm looking at a random sample." (But you aren't; you're being picky!)
The PEMI Way: "I'll tell you the range of possibilities, specifically adjusted for the fact that I chose to look at this one because it was special."

Technical Summary: Online Selective Conformal Prediction with Asymmetric Rules

1. Problem Statement

Standard Conformal Prediction (CP) provides valid coverage guarantees for prediction sets under the assumption of exchangeability. However, in many real-world applications, practitioners only issue predictions for a subset of data points based on a data-driven selection mechanism (e.g., a scientist only investigates drug candidates with high predicted activity).

This "selective issuance" breaks the exchangeability between labeled (calibration) and unlabeled (test) data, leading to a coverage gap where the prediction sets fail to cover the true labels for the selected instances.

Existing literature addresses this in two ways:

Offline Setting: Methods like JOMI (Jin and Ren, 2024) work for selection rules that are permutation invariant (symmetric) to the labeled data.
Online Setting: Current online methods are restricted to a narrow class of "decision-driven" rules (where the decision depends only on past decisions and current covariates) and often produce overly conservative or "vacuous" (infinite-length) prediction sets.

The fundamental challenge is that in online settings, selection rules are naturally asymmetric: the specific order of the arriving data affects the selection trajectory, breaking the symmetry required by previous methods.

2. Methodology: PEMI

The authors propose PErmutation-based Mondrian Conformal Inference (PEMI), a general framework designed to achieve Selection-Conditional Coverage (SCC) for arbitrary asymmetric selection rules.

Core Idea: Selective Inference over Permutations
Instead of performing "swapping" on individual data points (which fails when order matters), PEMI performs inference at the level of permutations.

Permutation Reference Set: For a given test point at time $t$ , the method identifies a subset of all possible permutations of the observed data that would result in the exact same selection decision ( $S_t = 1$ ). This subset is called the reference set $\hat{R}_t$ .
Calibration: The prediction set is calibrated by comparing the conformity score of the observed data against the distribution of scores within this selection-preserving reference set.
Monte-Carlo Implementation: Since enumerating all $t!$ permutations is computationally impossible, PEMI uses a Monte-Carlo subset of permutations, which still maintains finite-sample exact coverage guarantees.

Key Extensions:

Offline Data: Can incorporate additional unlabeled data that does not participate in the selection process.
Multiple Test Samples: Generalizes to scenarios where multiple test points are selected simultaneously.
FCR Control: Extends to controlling the False Coverage Rate (FCR) by using a "selection taxonomy" (restricting inference to specific selection trajectories).

3. Key Contributions

Theoretical Generality: Proves that PEMI achieves finite-sample exact SCC for any asymmetric selection mechanism and any prediction model, provided the data is exchangeable.
Computational Efficiency: The authors derive efficient algorithms for three major classes of selection rules:
- Covariate-dependent rules: (e.g., decision-driven, weighted quantiles/averages, or black-box optimization).
- Conformal selection: (e.g., thresholding conformal $p$ -values or $e$ -values).
- Outcome-based selection: (e.g., selecting based on the weighted quantiles of previous realized labels).
Unified Framework: PEMI strictly generalizes previous methods (like JOMI and EXPRESS), reducing to them under specific symmetry conditions.

4. Results and Empirical Validation

The authors validate PEMI using a real-world drug discovery dataset (DTI task) and extensive simulations.

Drug Discovery (Real Data): In tasks like predicting binding affinities, PEMI consistently achieved the target coverage level ( $1-\alpha$ ). In contrast, vanilla CP severely under-covered, and existing online methods (like EXPRESS) were either overly conservative or produced infinite-length prediction sets.
Robustness (Simulations):
- Model Quality: PEMI remained robust even under severe model misspecification and varying noise levels.
- Selection Dynamics: PEMI handled various weight decay rates in selection rules and different types of conformity scores (including CQR) more effectively than standard methods.
Efficiency: PEMI produced non-vacuous (finite-sized) prediction sets even with a relatively small number of labeled samples, whereas previous "swapping" methods often failed to find enough exchangeable points, leading to infinite sets.

5. Significance

This paper provides a much-needed theoretical and practical bridge for selective inference in streaming data. By shifting the unit of inference from data points to permutations, the authors overcome the "asymmetry barrier" that limited previous conformal prediction methods. This makes the framework applicable to a vast array of high-stakes, real-time decision-making processes, such as clinical diagnostics, automated resource allocation, and real-time scientific discovery, where decisions are inherently sequential and data-dependent.