📊 statistics

Clustered random forests with correlated data for optimal estimation and inference under potential covariate shift

This paper introduces Clustered Random Forests, an algorithm that leverages within-cluster correlations to improve prediction accuracy and inference for clustered data, while demonstrating that optimal weight selection depends on the target covariate distribution under potential covariate shift.

Original authors: Elliot H. Young, Peter Bühlmann

Published 2026-01-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Elliot H. Young, Peter Bühlmann

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 trying to predict the future temperature in a city. You have a lot of data, but it's not just a random list of numbers. The data comes in groups (clusters). For example, you have temperature readings from the same weather station taken every hour for a week.

In a standard weather model (a "Random Forest"), the computer treats every single reading as if it were completely independent. It doesn't realize that the temperature at 10:00 AM is closely related to the temperature at 10:05 AM because they come from the same station. It's like asking a group of friends for advice, but treating their answers as if they were strangers who never spoke to each other. This ignores the fact that friends often agree with each other, which actually contains valuable information.

This paper introduces a new tool called Clustered Random Forests. Here is how it works, broken down simply:

1. The Problem: Ignoring the "Group Hug"

When data comes in clusters (like repeated measurements from the same person, or students in the same classroom), the items inside the group are "correlated." They influence each other.

Old Way: Standard Random Forests ignore this. They treat every data point as a lonely island. This leads to predictions that are a bit "wobbly" (high variance) and confidence intervals (the range where the answer is likely to be) that are too wide.
New Way: The authors' method acknowledges the "group hug." It uses a special math trick (weighted least squares) to say, "Hey, these points are related, so let's trust them together more than we trust random strangers." This makes the predictions steadier and the confidence intervals tighter.

2. The Speed Trick: Fast as Lightning

Usually, when you try to account for these complex relationships between data points, the math gets incredibly heavy and slow. It's like trying to solve a puzzle where every piece is glued to every other piece.

The Paper's Claim: The authors found a way to do this complex math almost as fast as the standard, simple method. They use a clever shortcut (conjugate gradient descent) that keeps the speed "linear."
Analogy: Imagine a standard method takes 1 hour to sort a deck of cards. A traditional "correlated" method might take 100 hours. This new method takes 1 hour and 5 minutes. It's fast enough to use on massive datasets without waiting forever.

3. The "Covariate Shift" Surprise: One Size Does Not Fit All

This is the most surprising part of the paper.

The Scenario: Imagine you trained your model on data from New York (cold winters, hot summers). Now you want to use it to predict weather in Miami (warm year-round). This change in the environment is called "covariate shift."
The Old Belief: For independent data, the best way to handle this shift is usually just to re-weight the data based on how different the new place is.
The New Discovery: The authors found that for correlated data, the "best" way to weigh the groups changes depending on where you are trying to predict.
- Analogy: Think of a team of hikers. If you want to predict how fast they will walk on a flat path (Training Data), you might weigh the team based on their average speed. But if you want to predict their speed on a steep mountain (Test Data), the "best" way to weigh the team changes completely.
- The Warning: If you use a method that optimizes for the training data (like standard cross-validation or likelihood-based methods), it might pick the "wrong" weights for the new environment. The paper shows this can lead to terrible predictions—sometimes even worse than just ignoring the correlations entirely!
- The Solution: Their method lets you tell the computer, "I want the best prediction for this specific new environment," and it adjusts the weights accordingly.

4. Real-World Proof

The authors tested this in two ways:

Simulations: They created fake data where they knew the answer. They showed that their method was more accurate and gave tighter confidence intervals than standard methods, especially when the data distribution changed.
Real Data (HIV Patients): They looked at CD4 cell counts (a health marker) for HIV patients over time. Since each patient has multiple measurements, the data is clustered.
- Result: Their method predicted the cell counts with the same accuracy as the standard method but with significantly smaller margins of error (tighter confidence intervals). For one patient, the uncertainty dropped by 40%.

Summary

The paper presents a smarter, faster version of the popular "Random Forest" algorithm for grouped data.

It listens to the group: It uses the relationships between data points to make better predictions.
It's fast: It doesn't slow down the computer.
It adapts: It realizes that the "best" way to handle grouped data changes depending on the specific question or environment you are asking about, preventing the model from failing when the data shifts.

The authors have even made this available as a software package (called corrRF) so others can use it.

Technical Summary: Clustered Random Forests with Correlated Data

Problem Statement

Real-world datasets frequently exhibit clustered structures arising from repeated measurements, longitudinal studies, or geographical groupings. In such settings, observations within a cluster are often correlated, violating the independent and identically distributed (i.i.d.) assumption standard to many machine learning algorithms. While parametric mixed-effects models can account for these correlations, they rely on specific parametric assumptions regarding the mean and covariance structures; misspecification of these structures can lead to substantial bias and inconsistent estimation.

Existing nonparametric approaches, such as Random Forests (RF), typically ignore intra-cluster correlations or attempt to model them via rigid parametric covariance structures (e.g., REEM trees, Mixed Effects Random Forests). These existing methods often suffer from computational intractability (cubic complexity) or fail to guarantee variance reduction over standard RFs. Furthermore, a critical gap exists in understanding how optimal estimation and inference behave under covariate distribution shift when data are correlated. Standard methods optimized for the training distribution may perform arbitrarily poorly when the test distribution shifts, a phenomenon less studied in correlated data settings compared to independent data.

Methodology: Clustered Random Forests (CRF)

The authors propose Clustered Random Forests (CRF), a nonparametric extension of the Random Forest algorithm designed specifically for clustered data. The core innovation lies in modifying the leaf-wise prediction mechanism of the constituent decision trees.

Algorithmic Framework

Clustered Decision Trees (CDT): Instead of using Ordinary Least Squares (OLS) to estimate the mean within a leaf (as in standard RFs), CRFs employ Weighted Least Squares (WLS).
- The prediction in a leaf is a weighted average of observations, where weights are derived from a cluster-wise weight matrix $W_i(\rho)$ .
- These weights are designed to account for intra-cluster correlations. The authors focus on parametric classes of weights, specifically equicorrelated (exchangeable) and AR(1) structures, which allow for computationally efficient fitting.
Weight Estimation:
- Unlike likelihood-based methods (e.g., REEM, MERF) that estimate covariance parameters via maximum likelihood on residuals, CRF estimates the weight parameter $\rho$ to minimize the Mean Squared Prediction Error (MSPE) under a specific target covariate distribution $Q$ .
- This allows the algorithm to adapt to covariate shift. The optimal weight $\rho^*$ is a function of the target distribution $Q$ .
- The estimation utilizes a "covariance model-free" ethos, estimating $\rho$ based on minimizing an empirical estimator of the integrated variance over the target distribution $Q$ , rather than assuming a specific generative model for the errors.
Honesty and Subsampling:
- The algorithm enforces the honesty property (Wager and Athey, 2018): data used to determine splits, estimate weights, and make predictions are strictly separated.
- It employs a "bootstrap of little bags" subsampling strategy to construct the forest and estimate variance, enabling the construction of valid confidence intervals.

Computational Efficiency

A significant technical achievement is the development of algorithms that fit CRFs in approximately linear time relative to the number of observations. By leveraging the structure of equicorrelated and AR(1) weight matrices, the authors utilize conjugate gradient descent to solve the WLS problems, avoiding the cubic $O(M^3)$ complexity associated with inverting dense matrices in existing mixed-effects forest methods.

Key Theoretical Contributions

1. Asymptotic Rates and Minimax Optimality

The authors derive asymptotic upper bounds for the general $Q$ -covariate shifted MSPE. They demonstrate that there exist splitting rules and subsampling regimes within the CRF framework that achieve minimax optimal rates for pointwise estimation of Lipschitz mean functions. These rates match those of standard random forests for i.i.d. data, despite the added complexity of correlation.

2. Covariate Shift and Optimal Weights

A central theoretical finding is that for correlated data, the optimal weight parameter $\rho$ that minimizes MSPE is not invariant to covariate shifts.

Theorem 2 establishes that the optimal weights for a target distribution $Q$ can differ arbitrarily from those optimal for the training distribution.
Consequently, methods that estimate weights based solely on the training distribution (e.g., via cross-validation or likelihood maximization on training residuals) can be arbitrarily suboptimal under covariate shift, performing worse than even standard unweighted Random Forests.
This contrasts with independent data settings where re-weighting schemes (like importance weighting) are well-understood; in correlated settings, the optimal weighting strategy is intrinsically linked to the target distribution $Q$ .

3. Inference and Asymptotic Normality

The paper proves that variance-dominating CRFs are asymptotically Gaussian pointwise and uniformly over a class of distributions. This result holds under specific subsampling rates that ensure variance dominance over bias. This theoretical guarantee allows for the construction of asymptotically valid confidence intervals for the conditional mean function, with widths that converge at faster rates than standard RFs due to the variance reduction achieved by accounting for correlations.

Empirical Results

The authors validate their theoretical findings through simulations and a real-world application:

Covariate Shift Simulation: In a setting with equicorrelated data, CRFs optimized for a shifted test distribution ( $Q = \text{Unif}[1, 2]$ ) significantly outperformed standard RFs, training-error-optimized forests (TRAIN), and likelihood-based forests (REEM). Notably, TRAIN and REEM forests performed worse than standard RFs under the shift, confirming the theoretical risk of ignoring distributional shifts in weight estimation.
Inference Simulation: In settings with AR(2) correlated errors, CRFs achieved tighter confidence intervals (reduced width) while maintaining nominal coverage (95%) compared to standard RFs. This resulted in lower mean squared error for the point estimates.
Real-World Application (HIV CD4 Counts): Analyzing CD4 cell counts from HIV seroconverters, CRFs provided personalized predictions with 20–40% reduction in estimated variance compared to standard RFs, demonstrating practical utility in medical prediction tasks with repeated measures.

Significance and Claims

The paper claims to provide a practical and theoretically grounded extension of Random Forests to clustered data that:

Leverages Correlation: Improves prediction accuracy and inference precision by explicitly modeling intra-cluster dependence without relying on rigid parametric mean models.
Addresses Covariate Shift: Identifies and solves a critical flaw in existing correlated-data methods: the failure to adapt weights to the target covariate distribution. The authors argue that optimal nonparametric estimation under covariate shift for correlated data requires a user-specified target distribution to determine weights.
Ensures Scalability: Overcomes the computational barriers of previous mixed-effects forest methods, offering a solution with linear-time complexity comparable to standard Random Forests.
Enables Valid Inference: Provides the first asymptotic theory for variance-dominating clustered forests that supports the construction of tight, valid confidence intervals.

The authors position their work as a bridge between the flexibility of nonparametric machine learning and the rigorous handling of dependence structures, offering a new perspective on the covariate shift problem in the context of correlated data.