📊 statistics

Approximate full conformal prediction in an RKHS

This paper proposes a generic, computationally efficient strategy for approximating full conformal prediction regions within a Reproducing Kernel Hilbert Space (RKHS) framework, while providing theoretical guarantees on the approximation's tightness based on the smoothness of loss and score functions.

Original authors: Davidson Lova Razafindrakoto, Alain Celisse, Jérôme Lacaille

Published 2026-07-09

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Davidson Lova Razafindrakoto, Alain Celisse, Jérôme Lacaille

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 detective trying to guess the next number in a secret sequence. You have a crystal ball (your predictor) that gives you a best guess, but you know it's not perfect. To be safe, you don't just give one number; you draw a "confidence net" around your guess. This net is wide enough that, statistically, the real number will fall inside it 90% of the time (or whatever safety level you choose).

This is the world of Conformal Prediction. It's a super reliable way to build these nets without needing to know the exact rules of the universe (distribution-free).

The Impossible Dream: The "Full" Net

The most perfect version of this net is called Full-Conformal Prediction. It's like a detective who, for every single possible number the answer could be, re-runs their entire investigation from scratch to see if that number fits the clues.

Here's the problem: If the answer could be any real number (like 3.14159...), there are infinitely many possibilities. To build the perfect net, you'd have to re-run your investigation an infinite number of times. That's impossible. It's like trying to count every grain of sand on a beach to find the perfect spot to build a sandcastle. You'd never finish.

The Usual Compromise: Cutting the Beach in Half

Because the "Full" method is impossible, most detectives use a shortcut called Split-Conformal. They take their clues, cut the beach in half, use one half to build the sandcastle, and the other half to test the net.

The paper argues that this shortcut has a flaw: You lose information. By throwing away half your clues to test the net, your net becomes wider and fuzzier. It's safe, but it's not very precise. It's like trying to guess the weather using only yesterday's data from one city, ignoring the rest of the world.

The Paper's Big Idea: The "Magic Mirror"

The authors, Davidson Lova Razafindrakoto and colleagues, propose a new strategy. Instead of cutting the beach in half or trying to count infinite grains of sand, they use a Magic Mirror (mathematically known as an RKHS or Reproducing Kernel Hilbert Space).

Think of the predictor as a stretchy, rubbery sheet. When you add a new clue (a new data point), the sheet stretches and changes shape. The "Full" method asks: "If the answer were this specific number, how would the sheet look?"

The paper's breakthrough is realizing that for certain types of smooth, rubbery sheets (specifically those using Kernel Ridge Regression), you don't need to stretch the sheet from scratch for every single number. Instead, you can use a Magic Mirror (called an Influence Function) to predict exactly how the sheet will stretch based on a tiny nudge.

The Three Levels of Magic

The paper tests three different ways to use this mirror, getting better and better:

The Rough Mirror (Uniform Stability): This is the first attempt. It says, "No matter what the number is, the sheet won't stretch too much." It's a safe bet, but it's a bit conservative. It creates a net that is smaller than the "Split" method but still a bit wider than necessary.
The Local Mirror (Local Stability): This mirror is smarter. It says, "If the number is close to what we already know, the sheet won't stretch much. If it's far away, it might stretch more." By looking at the local neighborhood, the net gets tighter and more precise.
The Super Mirror (Influence Functions): This is the star of the show. It uses a high-tech mathematical trick (requiring the rubber sheet to be very smooth and "twice-differentiable") to calculate the stretch with incredible accuracy. It's like having a mirror that doesn't just show you the reflection, but tells you exactly how the light bends.

What They Found (The Results)

The authors didn't just dream this up; they tested it with computer simulations using synthetic data (specifically, the "Friedman1" dataset).

The "Oracle" Test: Since they couldn't build the impossible "Full" net, they built a fake "Oracle" net (a perfect net that knows the answer in advance) to use as a ruler.
The Winner: The Influence Function method (the Super Mirror) created the smallest, tightest nets of all the methods they tested.
The Trade-off: The Super Mirror took a little more time to compute (about 1.41 times longer than the Oracle in their test), but it was worth it. The nets it produced were the most informative (narrowest) while still keeping the safety guarantee (90% coverage).
The "Split" Loser: The traditional "Split" method produced nets that were much wider (less precise) because it threw away half the data.

What They Ruled Out

The paper is very clear about what doesn't work or isn't the focus:

They reject the idea that you must split the data. They show you can get better results by using all the data if you use their approximation tricks.
They reject the idea that you need to re-train infinitely. Their method only requires training the predictor once (or a very small number of times), then using the math mirror to simulate the rest.
They argue against "worst-case" bounds. Previous methods often assumed the worst possible scenario (uniform stability), leading to huge, useless nets. Their new method adapts to the specific situation, making the net tighter.

How Sure Are They?

The authors are very confident in their math. They proved (with rigorous theorems) that their new nets are guaranteed to be safe (they contain the true answer at least 90% of the time). They also proved that their "Super Mirror" nets get tighter and tighter as you add more data, converging faster than the older methods.

In their simulations, the "Super Mirror" nets were consistently the smallest, with the estimated rate of improvement matching their mathematical predictions (a slope of about -1.20 in their graphs, meaning the net shrinks quickly as data grows).

The Bottom Line

If you want to predict the future with a safety net, don't throw away half your clues (Split method), and don't try to count infinite possibilities (Full method). Instead, use a Magic Mirror (Influence Functions) to see how your prediction tool would react to every possible outcome. It's faster than the impossible dream, safer than the shortcuts, and gives you the sharpest, most precise net possible.

Technical Summary: Approximate Full-Conformal Prediction in an RKHS

Problem Statement
Full-conformal prediction is a distribution-free framework that constructs confidence prediction regions with guaranteed coverage for a wide range of estimators. However, its practical application is severely limited by computational intractability. To compute the full-conformal prediction region for a new input $X_{n+1}$ , one must evaluate a non-conformity score for every possible candidate output $y \in \mathcal{Y}$ . Since the underlying predictor $\hat{f}_{D_y}$ must be retrained for each candidate $y$ (where $D_y$ includes the new point $(X_{n+1}, y)$ ), this requires training an infinite number of estimators when $\mathcal{Y} = \mathbb{R}$ .

Existing alternatives, such as split-conformal and cross-conformal prediction, reduce computational costs by training a fixed number of predictors. However, these methods incur a loss of information by discarding data during training or splitting, often resulting in larger, less informative prediction regions. Other approaches relying on closed-form solutions (e.g., for ridge regression) or specific p-value shapes are limited to narrow settings and do not generalize to arbitrary loss functions or Reproducing Kernel Hilbert Spaces (RKHS).

Methodology
The authors propose a generic strategy to approximate the full-conformal prediction region efficiently without splitting the data. The core of the methodology involves:

Approximate Predictors: Instead of retraining the predictor for every candidate $y$ , the method approximates the predictor $\hat{f}_{D_y}$ using a fixed predictor $\hat{f}_{D_z}$ (trained on a fixed point $z$ ) or a first-order correction based on influence functions.
Approximate Non-Conformity Scores: Using the approximate predictor, the authors define approximate non-conformity scores $\tilde{S}_{D_y}$ .
Bounding the Approximation Error: Crucially, the method derives explicit upper bounds ( $\tau$ ) on the discrepancy between the true scores and the approximate scores. These bounds depend on the smoothness of the loss function and the properties of the kernel.
Sandwiching the Region: By incorporating these error bounds into the conformal p-value calculation, the authors construct an "upper" approximate region ( $\hat{C}^{up}$ ) and a "lower" approximate region ( $\hat{C}^{lo}$ ). The true full-conformal region is guaranteed to lie within this sandwich ( $\hat{C}^{lo} \subseteq \hat{C}^{full} \subseteq \hat{C}^{up}$ ).
Thickness Quantification: A new metric called "thickness" is introduced to quantify the volume of the symmetric difference between the approximate and full-conformal regions, providing a measure of the approximation's tightness beyond simple coverage probability.

The paper develops three levels of approximation based on the smoothness assumptions of the loss function:

Level 0 (Uniform Stability): Uses uniform Lipschitz constants for the loss and score functions. This recovers bounds similar to uniform stability approaches but allows for general loss functions in RKHS.
Level 1 (Local Stability): Exploits the differentiability of the loss function to derive local stability bounds that vary with $y$ , tightening the approximation constants.
Level 2 (Influence Functions): Leverages higher-order smoothness (twice and thrice differentiable loss) and influence functions (Bouligand influence function) to create a predictor approximation that depends on $y$ via a first-order Taylor expansion. This yields faster convergence rates for the approximation error.

Key Contributions

Generic Approximation Strategy: The paper provides a distribution-free, generic framework for approximating full-conformal regions in RKHS settings with general (non-quadratic) loss functions, including robust losses like Logcosh, Pseudo-Huber, and smoothed Pinball.
Non-Asymptotic Guarantees: Unlike previous influence-function-based approaches that offer only asymptotic guarantees, this work provides non-asymptotic bounds on the approximation quality and ensures the resulting region is a valid confidence region (coverage $\geq 1-\alpha$ ).
Thickness Metric: The introduction of "thickness" allows for the quantification of the discrepancy between the approximate and full-conformal regions in terms of volume (Lebesgue measure), not just coverage probability.
Improved Convergence Rates: By utilizing influence functions and higher-order smoothness assumptions, the authors demonstrate that the approximation error decays at a faster rate ( $O(n^{-1+r+\min(-1+2r, 0)})$ ) compared to uniform stability bounds ( $O(n^{-1+r})$ ), particularly when the regularization parameter $\lambda$ decays slowly.

Results

Theoretical Bounds: Theoretical analysis shows that the thickness of the approximation is upper-bounded by terms dependent on the kernel properties, the regularization parameter, and the smoothness of the loss. For smooth loss functions, the bounds tighten significantly as sample size $n$ increases.
Empirical Performance: Experiments on synthetic data (Friedman1) compare four strategies: Split-conformal, Uniform Stability (Level 0), Local Stability (Level 1), and Influence Function (Level 2).
- Coverage: All proposed methods achieve empirical coverage close to the target level ( $1-\alpha = 0.9$ ).
- Region Size: The Influence Function-based method produces the narrowest (most informative) prediction regions with low variance, outperforming both split-conformal and stability-based methods.
- Computation: While the Influence Function method requires more computation time (due to Hessian matrix inversion), it remains tractable. The Local Stability method offers a favorable trade-off between precision and computational cost.
Visualization: Log-log plots of the "thickness" gap versus sample size confirm the theoretical convergence rates, showing that the Influence Function approach converges faster than the uniform stability approach.

Significance and Claims
The authors claim that their work bridges the gap between the theoretical optimality of full-conformal prediction and the computational feasibility of split-conformal methods. By avoiding data splitting, the proposed method utilizes the full dataset for training, thereby preserving information and yielding tighter prediction regions. The framework is significant because it extends full-conformal approximation to a broad class of loss functions and RKHS settings, providing rigorous non-asymptotic guarantees on both coverage and the "tightness" (thickness) of the resulting regions. The paper emphasizes that while the approximation is computationally efficient (requiring only one or a few predictor evaluations), it maintains the distribution-free validity of the full-conformal framework.