Abstract
We propose a computationally and statistically efficient divide-and-conquer (DAC) algorithm to fit sparse Cox regression to massive datasets where the sample size $n_0$ is exceedingly large and the covariate dimension $p$ is not small but $n_0 \gg p$. The proposed algorithm, $DAC_{lin}$, achieves computational efficiency through a one-step linear approximation followed by a least square approximation (LSA) to the partial likelihood (PL). These sequences of linearization enable us to maximize the PL with only a small subset and perform penalized estimation via a fast approximation to the PL. The algorithm is applicable for the analysis of both time-independent and time-dependent survival data. Simulations suggest that the proposed DAC algorithm substantially outperforms the full sample-based estimators and existing DAC algorithms with respect to computational speed, while achieving similar statistical efficiency as full sample-based estimators. The proposed algorithm was applied to an extraordinarily large time-independent survival dataset and an extraordinarily large time-dependent survival dataset for the prediction of heart failure-specific readmission within 30 days among Medicare heart failure patients.
Introduction
In the era of Big Data, researchers frequently encounter massive health insurance claims and Electronic Health Record (EHR) datasets containing millions of patients ($n_0$) and hundreds of potential predictors ($p$). When the objective is to predict "time-to-event" outcomes—such as the time until hospital readmission or mortality—the Cox Proportional Hazards Model is the standard statistical tool.
However, standard Cox regression implementations face two primary bottlenecks when scaled to the petabyte level. First is the computational scale: standard software packages struggle to process millions of rows, particularly when dealing with time-dependent covariates that expand datasets into hundreds of millions of records. Second is variable selection: identifying the most relevant predictors usually requires penalized estimation (e.g., LASSO), which is computationally prohibitive on massive datasets. While existing "Divide-and-Conquer" (DAC) strategies exist, they often require solving penalized problems on every subset, which remains slow and unoptimized for the unique mathematical structure of survival data.
The $DAC_{lin}$ Methodology
To address these challenges, we introduce $DAC_{lin}$, an algorithm that utilizes a three-step sequence of approximations to bypass the Big Data bottleneck:
- Initial Estimate: The algorithm begins by calculating a standard, unpenalized estimate on a single, manageable subset of the data.
- One-Step Update: It then performs a "one-step" linear approximation across all other data subsets. This allows the model to aggregate information from the entire dataset to create a highly accurate unpenalized estimate without ever loading the full dataset into memory simultaneously.
- Least Square Approximation (LSA): This step transforms the complex optimization problem into a simple pseudo-likelihood problem based on a sample of size $p$ (the number of features).
By the time the algorithm performs variable selection (the shrinkage step), it is working with a reduced mathematical space of size $p \times p$. This effectively decouples the task of learning coefficients from the task of selecting variables, allowing the heavy lifting to be performed linearly.
Empirical Evaluation
Simulation Studies
The $DAC_{lin}$ algorithm was evaluated against full-sample adaptive LASSO methods using simulations with up to 1,000,000 subjects. The results demonstrated that $DAC_{lin}$ provides massive speedups without sacrificing accuracy. In scenarios with 50 predictors, $DAC_{lin}$ was approximately 40 times faster than full-sample approaches. Even as the feature space grew to 200 predictors, it maintained a 10x speed advantage. Crucially, the Global Mean Squared Error (GMSE) remained nearly identical to the full-sample approach, proving that researchers do not need to trade statistical precision for computational speed.
Medicare Heart Failure Case Study
The algorithm's real-world feasibility was tested using Medicare Heart Failure data (2000–2012). The analysis was split into two components:
- Time-independent set: Approximately 9.5 million patients with 574 baseline covariates.
- Time-dependent set: A massive expansion accounting for daily environmental factors (e.g., air pollution and temperature), resulting in over 245 million records.
On the time-dependent dataset, $DAC_{lin}$ completed the analysis in 36.5 hours on a modest computing cluster. Standard methods would likely have failed due to memory constraints or required weeks to converge. The model successfully identified established risk factors for heart failure readmission, such as renal failure and malnutrition, while uncovering a novel association: a 10 $\mu g/m^3$ increase in daily fine particulate matter ($PM_{2.5}$) was associated with a 0.5% increase in the risk of 30-day readmission.
Discussion and Limitations
While $DAC_{lin}$ offers a robust solution for large-scale survival analysis, it is designed specifically for the $n_0 \gg p$ regime. If the number of predictors ($p$) approaches the sample size ($n$), the approximations used in the LSA step may become less stable. Additionally, like all LASSO-based methods, the algorithm can exhibit bias when signals are very weak or when variables are highly correlated.
Future work may extend the $DAC_{lin}$ framework to other penalty functions, such as SCAD or MCP, to further refine variable selection in high-dimensional survival contexts. Nevertheless, $DAC_{lin}$ represents a significant step forward in making complex survival models accessible for the largest available healthcare datasets.
Summary updated