📊 statistics

Robust Predictive Uncertainty and Double Descent in Contaminated Bayesian Random Features

This paper proposes a robust Bayesian framework for random feature regression that utilizes Huber-style contamination sets and pessimistic updating to derive tractable uncertainty bounds, demonstrating that predictive uncertainty remains computationally efficient, preserves double-descent asymptotics, and offers improved worst-case guarantees under prior and likelihood misspecification.

Original authors: Michele Caprio, Katerina Papagiannouli, Siu Lun Chau, Sayan Mukherjee

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michele Caprio, Katerina Papagiannouli, Siu Lun Chau, Sayan Mukherjee

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 trying to predict tomorrow's temperature. You have a sophisticated computer model (the Random Feature Model) that looks at past data to make its guess. Usually, this model is very confident: it gives you a single number (e.g., "70°F") and a tight range of uncertainty (e.g., "between 68°F and 72°F").

However, there's a problem. Your model makes two big assumptions:

The Prior Assumption: It assumes the weather behaves in a very specific, "normal" way based on history.
The Likelihood Assumption: It assumes the data it receives (the temperature readings) are accurate and follow a standard bell curve.

In the real world, these assumptions are often wrong. Maybe the sensors are glitching (bad data), or maybe the climate is shifting in a way the model didn't expect (bad assumptions). If you trust the model blindly, it might give you a very precise but dangerously wrong answer.

This paper proposes a new way to handle this uncertainty, called the Contamination Random Features Model. Here is how it works, using simple analogies:

1. The "Safety Margin" Approach (Contamination Sets)

Instead of trusting a single "best guess" for how the world works, the authors say: "Let's assume our model is mostly right, but maybe a little bit wrong."

They introduce a concept called Contamination. Imagine your weather model is a recipe.

The Baseline: 95% of the recipe is the original, trusted instructions.
The Contamination: The remaining 5% is "wildcard" ingredients. We don't know exactly what they are, but we know they are somewhere in the kitchen.

In the paper, they call these "credal sets." Instead of one single probability distribution, they work with a cloud of possibilities. They ask: "What is the worst-case scenario if that 5% of the recipe is sabotaged?"

2. The "Pessimistic" Forecaster

The authors use a strategy called Pessimistic Generalized Bayesian Updating. Think of this as a very cautious forecaster who always prepares for the worst.

If the data is slightly corrupted (like a sensor glitch), this forecaster doesn't just ignore it. They widen their prediction range to account for the possibility that the data is lying.
They calculate two boundaries: a Lower Bound (the most optimistic the model can be) and an Upper Bound (the most pessimistic).
The Result: Instead of a single tight line, you get a "safety envelope" or a "fuzzy zone" around the prediction. This envelope tells you: "The truth is definitely somewhere in here, even if our assumptions are slightly off."

3. The "Double Descent" Mystery

In modern AI, there is a strange phenomenon called Double Descent.

The Analogy: Imagine you are trying to draw a picture of a cat.
- If you have very few lines (features), the picture is blurry (high error).
- As you add more lines, the picture gets clearer (error goes down).
- But if you add too many lines (overfitting), the picture gets weird and jagged again (error goes up).
- The Twist: If you keep adding even more lines, the picture suddenly becomes smooth and accurate again (error goes down a second time). This "up and down" shape looks like a double valley, hence "Double Descent."

The paper proves something very important: Even when you add "contamination" (bad data or wrong assumptions), this Double Descent shape doesn't disappear.

What changes: The "hills" and "valleys" get taller and wider. The uncertainty envelope expands.
What stays the same: The location of the peak (the point where the model is most confused) stays exactly where it was. The "Double Descent" structure is preserved.

4. The "Imprecise Highest Density Region" (IHDR)

How do you actually use this fuzzy envelope? The authors introduce a tool called the IHDR.

Think of a standard confidence interval as a tight rubber band around the prediction.
The IHDR is a "smart rubber band." It stretches just enough to cover the worst-case scenarios allowed by your contamination settings, but it doesn't stretch unnecessarily.
The paper shows you can calculate this complex "smart band" very easily by just adjusting a standard Gaussian (bell curve) interval. It's like taking a standard map and adding a "buffer zone" around the roads to account for construction.

Summary of the Paper's Claims

Robustness: By admitting that our models might be slightly wrong (via contamination sets), we can build predictions that are "safe" against bad data or wrong assumptions.
Tractability: Even though we are looking at worst-case scenarios, the math remains simple and fast. We don't need supercomputers; we just need to adjust the standard formulas.
Structure Preservation: The weird "Double Descent" behavior of AI models is a fundamental structural feature. It survives even when the model is "contaminated" with errors. The errors just make the uncertainty bigger, they don't break the pattern.
Practical Tool: We can create "uncertainty envelopes" that tell us exactly how much we should trust a prediction when the data is messy.

In short, the paper teaches us how to build AI models that are humble. Instead of saying, "I am 99% sure it's 70°F," the model says, "Given that my sensors might be glitching, I'm 99% sure it's between 65°F and 75°F." And it proves that this humility doesn't break the underlying math of how the model learns.

Technical Summary: Robust Predictive Uncertainty and Double Descent in Contaminated Bayesian Random Features

Problem Statement
Random Feature (RF) models are a standard mechanism for scaling kernel methods to large datasets, often interpreted through a Bayesian lens where ridge-regularized training corresponds to Maximum A Posteriori (MAP) estimation with Gaussian priors and likelihoods. However, classical Bayesian RF formulations rely on modeling assumptions (Gaussian priors on coefficients and Gaussian likelihoods for outputs) that are rarely exact in practice. Deviations caused by heavy-tailed noise, label corruption, heteroskedasticity, or distribution shifts can lead to posterior predictive distributions that are overly confident, brittle to outliers, or sensitive to prior choices. The paper addresses the question of how Bayesian RF conclusions change when prior and likelihood misspecification are explicitly accounted for, specifically investigating whether the structural properties of RF models, such as the double-descent phenomenon, persist under such uncertainty.

Methodology
The authors propose a Contamination Random Features (CRF) model, a robust Bayesian formulation that replaces single prior and likelihood specifications with credal sets (convex, weak*-closed sets of probability measures).

Contamination Sets: The model utilizes $\epsilon$ -contaminated prior sets and $\eta$ -contaminated likelihood sets. These are defined as mixtures of the baseline Gaussian specifications ( $P^N$ and $L^N$ ) with arbitrary alternative distributions ( $Q$ and $S$ ). Formally, $P_\epsilon = \{(1-\epsilon)P^N + \epsilon Q\}$ and $L_\eta = \{(1-\eta)L^N + \eta S\}$ .
Inference Rule: The authors adopt pessimistic generalized Bayesian updating (Walley, 1991). This approach yields conservative (worst-case) posterior conclusions by updating the lower and upper envelopes of the credal sets rather than a single posterior distribution.
Analytical Approach: The paper derives explicit bounds for the lower and upper posterior predictive densities. It treats the contamination parameters $\epsilon$ and $\eta$ as robustness or sensitivity parameters, interpreting them as an "ambiguity budget" for prior and data-generating assumptions.

Key Contributions

Explicit Predictive Bounds: The authors derive tractable, explicit bounds for the lower and upper posterior predictive densities induced by simultaneous prior and likelihood contamination. They prove that the lower posterior predictive density $\underline{\ell}_{pred}$ satisfies $\underline{\ell}_{pred} \leq (1-\eta)\ell_{pred}$ , where $\ell_{pred}$ is the classical Gaussian predictive density. The upper bound includes an additive worst-case term. These results suggest that moderate contamination of the prior and likelihood acts approximately as a direct contamination of the posterior predictive distribution.
Imprecise Highest Density Region (IHDR): To quantify predictive uncertainty, the paper introduces the IHDR, defined as the smallest region attaining a target lower predictive probability mass. The authors show that the IHDR can be efficiently approximated by a credible interval of the classical Gaussian posterior predictive distribution with an adjusted coverage level ( $\beta = \min\{1, \frac{1-\alpha}{1-\eta}\}$ ). This provides a computationally feasible procedure for robust predictive intervals.
Variance Bounds and Asymptotics: The paper derives bounds for the lower and upper predictive variances. Under a mild truncation approximation for the upper bound, these variance bounds are shown to be affine transformations of the classical predictive variance. Crucially, the authors prove that these bounds preserve the leading-order proportional-growth asymptotics known for RF models.
Double-Descent Preservation: The analysis demonstrates that the double-descent phase structure (the singular behavior of risk and variance near the interpolation threshold $N \approx n$ ) is preserved under contamination. The contamination parameters act as rescaling factors that amplify the magnitude of the variance peak but do not shift its location in the proportional growth regime.

Results

Theoretical Bounds: The derived bounds confirm that uncertainty envelopes around the classical Gaussian predictive distribution are directly influenced by the contamination levels $\epsilon$ and $\eta$ . The lower bound is a simple rescaling, while the upper bound involves a rescaling plus a term dependent on the truncation interval.
Asymptotic Behavior: In the proportional asymptotic regime ( $n, d, N \to \infty$ with ratios fixed), the robust model retains the same asymptotic behavior as the baseline RF model. The double-descent peak in predictive variance remains at the same location ( $\psi_1 = N/d$ ), though its height is amplified by the contamination.
Numerical Validation: Experiments on label misspecification (simulated via Huber-style outliers) confirm that increasing the contamination level $\eta$ amplifies the test Mean Squared Error (MSE) peak near the interpolation threshold without shifting its location. The bias component remains stable, while the variance component drives the double-descent behavior, consistent with the theoretical bounds.

Significance and Claims
The paper establishes a robustness theory for Bayesian random features. It claims that predictive uncertainty in RF models can remain computationally tractable and asymptotically well-behaved even under bounded prior and likelihood misspecification.

Robustness without Sacrifice: The framework provides explicit worst-case guarantees (via uncertainty envelopes and IHDRs) without abandoning the analytical tractability of the Gaussian RF model.
Structural Stability: A central claim is that the structural features of high-dimensional learning, specifically the double-descent phenomenon, are robust to model misspecification. The contamination acts as a "dilution" or amplification of uncertainty but does not alter the fundamental phase transition structure of the model.
Practical Utility: The proposed method offers a principled way to quantify uncertainty in the presence of outliers or distribution shifts, allowing practitioners to report sensitivity curves or calibrated predictive intervals based on the contamination parameters.

The authors note that fully automatic selection of contamination levels $(\epsilon, \eta)$ under arbitrary nonparametric contamination requires additional modeling assumptions and is left for future work. Similarly, the choice of truncation intervals for upper variance bounds is currently heuristic, though data-adaptive choices are identified as a direction for future research.