Oracle inequalities for the lasso in the Cox model

Jian Huang, Tingni Sun, Zhiliang Ying, Yi Yu, Cun-Hui ZhangThe Annals of Statistics 2013 · DOI · arXiv

Abstract

This paper investigates the absolute penalized maximum partial likelihood estimator—the Lasso—within the context of sparse, high-dimensional Cox proportional hazards regression models. In these settings, the number of covariates $p$ can significantly exceed the sample size $n$. We establish oracle inequalities for the Lasso estimator based on natural extensions of compatibility and cone invertibility factors applied to the Hessian matrix of the partial likelihood. Our methodology demonstrates that these factors provide sharper oracle inequalities compared to those based on restricted eigenvalues, as compatibility and cone invertibility factors are inherently larger. Furthermore, we address the unique challenge of the Cox model where the Hessian matrix is derived from time-dependent covariates in censored risk sets, making the matrix itself a random variable. Under mild regularity conditions, we prove that these factors remain bounded from below by positive constants, even in high-dimensional scenarios where $p$ grows faster than $n$. This allows the compatibility and cone invertibility factors to be treated as stable constants in our theoretical guarantees.

Introduction

In modern clinical research, survival analysis is the primary tool for modeling the time until an event of interest occurs, such as disease recurrence or mortality. The Cox proportional hazards model is the gold standard for this task. However, the advent of high-throughput technologies like genomics has introduced a "high-dimensional" challenge: researchers often collect data on thousands of potential predictors ($p$) from a relatively small cohort of patients ($n$).

When $p \gg n$, traditional maximum likelihood estimation fails. While the Lasso ($\ell_1$-regularization) has become a popular solution for variable selection and shrinkage in linear regression, its theoretical justification in the Cox model is significantly more complex. This complexity arises because the Cox partial likelihood is not a sum of independent terms; it is a dynamic construction based on the relative timing of events and the composition of risk sets over time. This paper provides the necessary mathematical foundation to justify the use of Lasso in these sophisticated survival models.

Theoretical Framework

The $\ell_1$-Penalized Maximum Partial Likelihood

The authors analyze the estimator $\hat{\beta}$ that minimizes the negative log-partial likelihood plus an $\ell_1$ penalty term $\lambda \|\beta\|_1$. The primary goal is to prove "oracle inequalities"—bounds that show the Lasso estimator performs nearly as well as an "oracle" who knows the true set of relevant variables in advance.

Handling Temporal Randomness

Unlike standard regression where the design matrix is often treated as fixed, the "design" in a Cox model is inherently random. The Hessian matrix (the second derivative of the log-partial likelihood) depends on which subjects remain in the risk set at each event time. To navigate this, the authors utilize the mathematical framework of counting processes and martingales. This allows the theory to encompass time-dependent covariates, where the value of a predictor (e.g., a patient's blood pressure or dosage level) changes throughout the study.

Key Innovations: Compatibility and Cone Invertibility

A central contribution of this work is the adaptation of the compatibility factor and the cone invertibility factor to the Cox model.

  1. Sharper Bounds: Most previous high-dimensional proofs relied on the "restricted eigenvalue" condition. The authors demonstrate that compatibility factors provide sharper (tighter) error bounds because the compatibility factor is always greater than or equal to the corresponding restricted eigenvalue.
  2. Stability in High Dimensions: A major hurdle in high-dimensional theory is ensuring that the Hessian matrix remains "well-behaved" (invertible in the relevant directions) even when $p$ is large. The authors prove that for the Cox model, these random factors are bounded away from zero with high probability, provided the covariates are bounded and the model is sparse.

Main Results

The paper's findings are formalized in Theorems 3.1 and 3.2, which provide non-asymptotic upper bounds on the estimation error.

  • Estimation Error: The $\ell_1$ distance between the estimated coefficients $\hat{\beta}$ and the true coefficients $\beta^o$ is bounded by a term proportional to $\frac{d_0 \lambda}{\kappa^2}$, where $d_0$ is the number of non-zero coefficients in the true model and $\kappa$ is the compatibility factor.
  • Optimal Penalty: The theory suggests that a penalty parameter $\lambda$ on the order of $\sqrt{\frac{\log p}{n}}$ is sufficient to achieve these oracle properties, ensuring that the model ignores noise while retaining signal.
  • Finite Sample Validity: Unlike asymptotic theory which describes behavior as $n$ approaches infinity, these results are non-asymptotic. They provide guarantees that are applicable to the finite sample sizes typically found in clinical trials.

Conclusion and Limitations

This research confirms that the Lasso is a theoretically sound method for high-dimensional survival analysis, even when predictors are time-varying. It bridges the gap between the well-understood theory of Lasso in linear models and the more intricate world of partial likelihoods.

However, some constraints remain. The theory relies on the sparsity assumption—the idea that only a small subset of the measured variables truly influences survival. Additionally, while the paper provides a theoretical range for the penalty parameter $\lambda$, practical application still relies on empirical methods like cross-validation. The authors identify the theoretical analysis of cross-validated Lasso in the Cox model as a significant open problem for future study.

Summary updated

Abstract

We study the absolute penalized maximum partial likelihood estimator in sparse, high-dimensional Cox proportional hazards regression models where the number of time-dependent covariates can be larger than the sample size. We establish oracle inequalities based on natural extensions of the compatibility and cone invertibility factors of the Hessian matrix at the true regression coefficients. Similar results based on an extension of the restricted eigenvalue can be also proved by our method. However, the presented oracle inequalities are sharper since the compatibility and cone invertibility factors are always greater than the corresponding restricted eigenvalue. In the Cox regression model, the Hessian matrix is based on time-dependent covariates in censored risk sets, so that the compatibility and cone invertibility factors, and the restricted eigenvalue as well, are random variables even when they are evaluated for the Hessian at the true regression coefficients. Under mild conditions, we prove that these quantities are bounded from below by positive constants for time-dependent covariates, including cases where the number of covariates is of greater order than the sample size. Consequently, the compatibility and cone invertibility factors can be treated as positive constants in our oracle inequalities.
BibTeX
@article{huang2013oracle,
  author = {Jian Huang and Tingni Sun and Zhiliang Ying and Yi Yu and Cun-Hui Zhang},
  title = {{Oracle inequalities for the lasso in the Cox model}},
  journal = {The Annals of Statistics},
  year = {2013},
  doi = {10.1214/13-aos1098},
}
Figure