Nonregular and minimax estimation of individualized thresholds in high dimension with binary responses

Huijie Feng, Yang Ning, Jiwei ZhaoThe Annals of Statistics 2019 · arXiv

TL;DR

This paper tackles the challenging problem of estimating individualized thresholds for predicting binary outcomes in high-dimensional settings, where the number of predictors ($d$) far exceeds the number of observations ($n$). The authors introduce a novel penalized M-estimation framework using a smoothed loss function and an efficient path-following algorithm, achieving minimax-optimal estimation rates and computational efficiency. This work is crucial for applications like personalized medicine and diagnostics where understanding individual-specific decision boundaries is key.

What Problem Does This Paper Address?

In many fields, such as clinical diagnostics, personalized medicine, and econometrics, we want to predict a binary outcome (e.g., disease presence/absence, treatment success/failure) based on a continuous measurement ($X$) and a set of covariates ($Z$). Often, a simple linear threshold ($θ^T Z$) is used to adjust the decision boundary for $X$ based on an individual's characteristics ($Z$). The goal is to find the optimal threshold that best separates the two outcome classes.

The core challenge is that the "ideal" threshold is defined using the discontinuous sign function, making direct optimization computationally intractable. Furthermore, when the number of covariates ($d$) is very large compared to the sample size ($n$), standard statistical methods struggle. This "high-dimensional" and "nonregular" setting leads to nonstandard theoretical guarantees and computational hurdles. The paper aims to bridge this gap by developing a statistically sound and computationally efficient method for estimating these individualized thresholds.

Methods

The authors propose a two-pronged approach:

  1. Smoothed Surrogate Loss Function: To overcome the discontinuity of the sign function, they introduce a smoothed surrogate loss function. By shrinking the bandwidth of this smoother towards zero, it asymptotically approximates the original 0-1 loss, ensuring statistical consistency. Crucially, this smoothed loss is differentiable, allowing for gradient-based optimization.
  2. Penalized M-Estimation and Path-Following Algorithm: They formulate the problem as minimizing a penalized empirical risk function using the smoothed loss. To handle the high dimensionality and potential non-convexity, they employ an $\ell_1$ penalty (promoting sparsity in the threshold coefficients) and a path-following algorithm. This algorithm efficiently computes solutions across a range of regularization parameters, starting from a large value and gradually decreasing it. It leverages a proximal-gradient method with warm starts from previous stages to achieve a global geometric rate of convergence.

Datasets

  • Simulated Data: The authors generate synthetic data from two models: a binary response model and a conditional mean model.
  • Real Data: The proposed method is applied to the ChAMP (Chondral Lesions And Meniscus Procedures) study dataset, which involves patients undergoing knee surgery.

Key Insights and Ideas

  • Bridging Computation and Theory: The paper successfully connects a computationally challenging problem (non-smooth loss) with theoretical guarantees in a high-dimensional setting. The smoothed loss is key to enabling both.
  • Nonstandard Convergence Rates: The derived convergence rate $(s\log d/n)^{\beta/(2\beta+1)}$ is slower than typical Lasso rates but is shown to be minimax-optimal up to a logarithmic factor. This highlights the inherent difficulty of the problem.
  • Statistical-Computational Trade-off: The path-following algorithm offers a favorable trade-off: while the statistical rates might be slower than some linear models, the computational cost (number of stages) can be lower, especially as the smoothness parameter $\beta$ decreases.
  • Adaptivity: The use of Lepski's method allows for adaptive estimation of unknown sparsity ($s$) and smoothness ($\beta$), a crucial feature for practical applications where these parameters are not known beforehand.

Key Results

  • Statistical Guarantees: The proposed estimator achieves a finite sample error bound of $(s\log d/n)^{\beta/(2\beta+1)}$ in $\ell_2$ norm, which is proven to be minimax rate optimal up to a logarithmic factor.
  • Computational Efficiency: The path-following algorithm achieves a geometric rate of convergence for computing the entire solution path.
  • Simulation Performance: Simulations show that the proposed method outperforms standard logistic regression and SVM, especially in high-dimensional settings, and validates the algorithm's convergence properties.
  • Real Data Application: The method successfully identifies relevant predictors in the ChAMP study, demonstrating its practical utility in identifying individualized thresholds for clinical outcomes.

Limitations and Future Work

  • Unknown $s$ and $\beta$: While the paper develops adaptive procedures for unknown $s$ or $\beta$, it notes that simultaneously adapting to both unknown $s$ and $\beta$ is an open problem due to the lack of a strict ordering in multivariate grids.
  • Extensions: The authors suggest several avenues for future research:
  • Extending the framework to covariates with more complex structures (e.g., group sparsity).
  • Developing statistical inference procedures (e.g., confidence intervals) for the estimated thresholds.
  • Handling response variables with more than two groups.

Summary updated

Abstract

Given a large number of covariates Z, we consider the estimation of a high-dimensional parameter θ in an individualized linear threshold θTZ for a continuous variable X, which minimizes the disagreement between sign(X−θTZ) and a binary response Y. While the problem can be formulated into the M-estimation framework, minimizing the corresponding empirical risk function is computationally intractable due to discontinuity of the sign function. Moreover, estimating θ even in the fixed-dimensional setting is known as a nonregular problem leading to nonstandard asymptotic theory. To tackle the computational and theoretical challenges in the estimation of the high-dimensional parameter θ, we propose an empirical risk minimization approach based on a regularized smoothed non-convex loss function. The Fisher consistency of the proposed method is guaranteed as the bandwidth of the smoothed loss is shrunk to 0. Statistically, we show that the finite sample error bound for estimating θ in ℓ2 norm is (slogd/n)β/(2β+1), where d is the dimension of θ, s is the sparsity level, n is the sample size and β is the smoothness of the conditional density of X given the response Y and the covariates Z. The convergence rate is nonstandard and slower than that in the classical Lasso problems. Furthermore, we prove that the resulting estimator is minimax rate optimal up to a logarithmic factor. The Lepski’s method is developed to achieve the adaption to the unknown sparsity s or smoothness β. Computationally, an efficient path-following algorithm is proposed to compute the solution path. We show that this algorithm achieves geometric rate of convergence for computing the whole path. Finally, we evaluate the finite sample performance of the proposed estimator in simulation studies and a real data analysis from the ChAMP (Chondral Lesions And Meniscus Procedures) Trial.
BibTeX
@article{feng2019nonregular,
  author = {Huijie Feng and Yang Ning and Jiwei Zhao},
  title = {{Nonregular and minimax estimation of individualized thresholds in high dimension with binary responses}},
  journal = {The Annals of Statistics},
  year = {2019},
}
Figure