📊 statistics

Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces

This paper proposes a framework for uncertainty quantification in regression models on metric spaces, introducing a conformal algorithm with finite-sample guarantees for homoscedastic settings and a locally adaptive kNN procedure for heteroscedastic cases, both of which are scalable, model-agnostic, and validated through applications in personalized medicine involving complex random objects.

Original authors: Gábor Lugosi, Marcos Matabuena

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gábor Lugosi, Marcos Matabuena

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 weather forecaster. Usually, you just give a single number: "It will be 75°F tomorrow." But that's not very helpful if you're planning a picnic. You also need to know: How sure are you? Is it likely to be between 70°F and 80°F, or could it swing wildly from 50°F to 100°F?

In the world of data science, this "how sure are you?" question is called Uncertainty Quantification. Most current methods are great at giving a single number (the average), but they struggle to draw a reliable "safety zone" around that number, especially when the data is complex or messy.

This paper by Lugosi and Matabuena introduces a new toolkit for drawing those safety zones, specifically for data that doesn't fit neatly into a standard spreadsheet (like shapes, graphs, or probability distributions). They call these complex data points "random objects" living in "metric spaces" (a fancy way of saying "a world where we can measure distance between things, even if they aren't just numbers").

Here is the breakdown of their solution using simple analogies:

1. The Two Types of Weather (Homoscedastic vs. Heteroscedastic)

The authors realize that uncertainty behaves differently depending on the situation. They split the problem into two scenarios:

The "Steady Rain" Scenario (Homoscedastic):
Imagine a day where the rain is consistent. It might be heavy, but the variability (how much it changes from minute to minute) is the same everywhere.
- The Paper's Solution: They use a method called Conformal Prediction. Think of this as taking a bucket of past rain measurements, finding the "typical" amount, and drawing a circle around it that is guaranteed to catch the rain 95% of the time.
- The Benefit: This method is mathematically "bulletproof" for small datasets. It guarantees that your safety zone is correct without needing to make complex assumptions about how the rain behaves. It's fast and reliable.
The "Stormy Day" Scenario (Heteroscedastic):
Now imagine a day where the weather is chaotic. In the morning, it's calm (low uncertainty), but in the afternoon, it's a tornado (high uncertainty). The amount of "wiggle room" you need changes depending on where you are or what time it is.
- The Problem: The "Steady Rain" method fails here because it draws one giant circle for the whole day. It's too big for the calm morning and too small for the stormy afternoon.
- The Paper's Solution: They introduce a k-Nearest Neighbors (kNN) approach. Imagine you are trying to predict the weather for a specific neighborhood. Instead of looking at the whole city's history, you only look at the 5 closest neighborhoods that had similar weather patterns.
- The Magic: This allows the safety zone to shrink when things are calm and expand when things are wild. It adapts locally. While it doesn't have the same "bulletproof" guarantee for tiny datasets as the first method, it is much smarter for complex, changing data.

2. Handling "Weird" Shapes (Metric Spaces)

Most statistics assume data is just a list of numbers (like height and weight). But in modern medicine, data can be weird shapes:

Probability Distributions: Instead of saying "The average glucose level is 100," we might say "Here is the entire curve of how glucose levels fluctuate throughout the day."
Graphs: Instead of a number, the data is a network of connections (like a brain scan or a social network).

The authors' toolkit works in these "weird shape" worlds. They don't force these shapes into a box; they measure the distance between shapes and draw safety zones (balls) around them.

3. Real-World Tests (What the Paper Actually Showed)

The authors didn't just talk theory; they tested their tools on real medical data to prove they work:

Parkinson's Disease Handwriting: They looked at digital drawings of spirals made by people with Parkinson's and healthy people. They used their "Steady Rain" method to draw a "normal" zone based on healthy people. They found that many Parkinson's patients' drawings fell outside this zone, showing the method can spot differences in complex shapes.
Glucose Monitoring: They analyzed continuous glucose data from people without diabetes. Instead of just looking at the average sugar level, they treated the entire daily pattern as a single object. They built a safety zone that changes based on age. They found that as people get older, the "safety zone" for glucose levels gets wider, meaning older adults have more variability in their sugar levels throughout the day.

4. Why This Matters (The Bottom Line)

Speed: Their methods are fast. They can process millions of data points in seconds, whereas older methods for complex shapes take hours.
Flexibility: You can use any prediction model you like (like Random Forests or Neural Networks) and wrap their uncertainty tool around it.
No "Smoothness" Required: Many old methods require the data to be perfectly smooth and predictable. These new methods work even when the data is jagged, discrete, or messy.

In summary: This paper gives scientists a new way to say, "I predict X, and I am 95% sure the real answer is inside this specific shape." It works for simple numbers, but more importantly, it works for complex, real-world objects like medical graphs and time-series distributions, adapting its confidence level to match the chaos of the data.

Technical Summary: Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces

1. Problem Definition and Motivation

The paper addresses the challenge of predictive uncertainty quantification for regression models where the response variable $Y$ resides in a general separable metric space $(\mathcal{Y}, d_1)$ , and the predictor $X$ is in $\mathbb{R}^p$ . The goal is to construct a prediction region $C_\alpha(x) \subset \mathcal{Y}$ such that the true response $Y$ falls within this region with probability at least $1-\alpha$ , given $X=x$ .

The authors identify specific limitations in existing methods, particularly conformal inference:

Conservatism: Standard conformal methods often produce overly conservative intervals, especially in heteroscedastic settings or high-dimensional spaces, leading to a loss of statistical efficiency.
Smoothness Assumptions: Existing metric-space approaches (e.g., Zhou and Müller [2025]) rely on kernel smoothing and differentiability assumptions, which are restrictive for discrete data or complex non-Euclidean structures.
Scalability: Full conformal methods and depth-profile approaches are computationally expensive for large datasets.
Applicability: Many methods are limited to scalar responses or Euclidean predictors, failing to handle "random objects" like probability distributions or graphs common in digital health.

The paper aims to develop a framework that provides finite-sample marginal coverage guarantees (in homoscedastic cases) and locally adaptive prediction radii (in heteroscedastic cases) without imposing strong smoothness assumptions, while remaining computationally scalable.

2. Methodology

The framework defines the regression function $m(x)$ as the conditional Fréchet mean:
$m(x) = \arg\min_{y \in \mathcal{Y}} \mathbb{E}[d_1^2(Y, y) \mid X = x]$
The prediction region is defined as a metric ball $C_\alpha(x) = B(m(x), r(x))$ , where the radius $r(x)$ is determined by the conditional quantile of the distance $d_2(Y, m(x))$ . The authors distinguish between two metrics: $d_1$ (used for loss/regression) and $d_2$ (used for defining the prediction region), allowing for modeling flexibility.

The methodology is divided into three main components:

2.1 Homoscedastic Case: Split Conformal Prediction

The authors introduce a notion of homoscedasticity in metric spaces: the distribution of the distance $d_2(Y, m(x))$ is independent of $x$ .

Algorithm: A split-conformal approach is used. The data is split into a training set ( $D_{train}$ ) to estimate the center $\hat{m}(x)$ and a calibration set ( $D_{test}$ ) to estimate a global radius.
Radius Estimation: The radius is set to the empirical quantile of the calibration scores $\{d_2(Y_i, \hat{m}(X_i))\}_{i \in D_{test}}$ .
Guarantees: This yields a finite-sample marginal coverage guarantee: $P(Y \in \hat{C}_\alpha(X)) \geq 1-\alpha$ .
Convergence: The authors prove consistency and fast convergence rates (driven by the estimation error of the Fréchet mean and the quantile) under mild conditions, specifically requiring only the consistency of the Fréchet mean estimator.

2.2 Heteroscedastic Case: Local kNN Procedure

For settings where the conditional distribution of errors depends on $x$ (heteroscedasticity), a global radius is inefficient.

Algorithm: A k-Nearest Neighbors (kNN) approach is proposed. For a new point $x$ , the prediction radius is estimated using only the calibration points in the $k$ -nearest neighborhood of $x$ .
Data-Driven Selection of $k$ : A novel criterion is introduced to select the neighborhood size $k$ . It balances global empirical coverage (ensuring the overall coverage is close to $1-\alpha$ ) and local empirical coverage (ensuring local deviations are minimized). The algorithm selects the smallest $k$ satisfying these constraints.
Guarantees: While this method does not provide finite-sample conformal guarantees, the authors establish asymptotic consistency and derive finite-sample upper bounds on the expected error. The method avoids smoothing assumptions and adapts to the local geometric structure of the predictor space.

2.3 Sequential Extension for Time Series

The framework is extended to metric-space-valued time series under stationarity and ergodicity assumptions.

Method: A nearest-neighbor expert aggregation method is used. Historical lag blocks are compared to the current state to estimate conditional residual quantiles.
Aggregation: Local quantile experts are combined using exponential weights based on pinball loss to produce a data-adaptive radius.
Guarantees: The method provides an asymptotic time-average calibration guarantee ( $\frac{1}{n}\sum P(Y_{t+1} \in \hat{C}_t) \to 1-\alpha$ ), rather than finite-sample guarantees.

3. Key Contributions

Novel Homoscedasticity Definition: A definition of homoscedasticity tailored to metric spaces, enabling the construction of efficient conformal algorithms with fast convergence rates.
Three Algorithmic Frameworks:
- A split-conformal algorithm for homoscedastic metric spaces with finite-sample marginal guarantees.
- A local kNN algorithm for heteroscedastic settings that achieves good conditional calibration without smoothing assumptions.
- A sequential expert-aggregation method for time series in metric spaces.
Theoretical Consistency: Proofs of consistency for the proposed estimators under minimal conditions (weaker than those required in Euclidean literature).
Computational Efficiency: The proposed methods are computationally scalable, capable of processing millions of observations in seconds, contrasting with depth-profile methods that require hours for smaller datasets.
Flexibility: The framework is compatible with any regression algorithm (e.g., Random Forests, Global Fréchet regression, kNN) and handles non-Euclidean responses (distributions, graphs) and predictors.

4. Results

4.1 Simulation Study

The authors evaluated the framework on scalar-on-scalar regression and metric-space-valued outcomes.

Performance: In heteroscedastic settings (linear and nonlinear), the proposed adaptive kNN method achieved the lowest Integrated Squared Conditional Error (ISCE) and highest Worst-Slice Coverage (WSC) compared to competitors like Conformalized Quantile Regression (CQR) and the depth-profile method of Zhou and Müller [2025].
Homoscedastic Settings: The global conformal method performed competitively with CQR, confirming its efficiency when the homoscedastic assumption holds.
Efficiency: The proposed methods were significantly faster (seconds vs. 50 minutes for $n=3000$ ) than the depth-profile approach.
Robustness: The heteroscedastic method maintained good marginal calibration even when not conformally calibrated, though small-sample stability for worst-slice coverage was noted as a limitation.

4.2 Real-World Applications

The framework was applied to two biomedical datasets:

Shape Analysis (Parkinson's Disease): Handwriting trajectories were treated as random objects. The method constructed Fréchet-centered reference regions for healthy controls. Trajectories from Parkinson's patients frequently fell outside these regions, illustrating the potential for shape-based digital biomarkers.
Distribution-Valued Glucose Monitoring: Continuous Glucose Monitoring (CGM) data were represented as probability distributions in the 2-Wasserstein space. Using Global Fréchet regression and the kNN radius estimator, the authors constructed age-specific prediction regions. Results showed that prediction regions (variability) widen with age, capturing distributional changes not visible in scalar summaries.

5. Significance and Claims

The paper claims to provide a general, flexible, and computationally efficient framework for uncertainty quantification in metric spaces. Its significance lies in:

Bridging the Gap: It extends conformal prediction and local calibration techniques to non-Euclidean settings without relying on the restrictive smoothness assumptions of existing metric-space methods.
Practical Utility: The ability to handle complex random objects (distributions, graphs) with fast computation makes the framework suitable for modern digital health and personalized medicine applications.
Theoretical Rigor: It establishes consistency and convergence rates under minimal assumptions, offering a robust alternative to asymptotic-only methods.
Adaptability: The data-driven selection of neighborhood sizes allows the method to adapt to local heteroscedasticity, improving conditional calibration where global methods fail.

The authors modestly note that while the method provides strong marginal guarantees in homoscedastic cases and good conditional calibration in heteroscedastic cases, the use of metric balls may be conservative for highly non-spherical distributions. Future work is suggested to explore more flexible prediction regions beyond metric balls.