Abstract
Sparse Linear Isotonic Models (SLIMs) address the challenge of high-dimensional data where predictors and response variables exhibit monotone, non-linear relationships. By integrating rank-based estimation with isotonic regression, SLIMs identify relevant features and their functional forms without requiring prior knowledge of directionality. This paper details a two-step algorithm—the Kendall’s tau Dantzig Selector followed by standardized isotonic regression—and demonstrates its superior performance over standard linear models in synthetic high-dimensional settings. We show that SLIMs achieve the "gold standard" sample complexity of $O(s \log p)$ while providing significantly better prediction accuracy in the presence of non-linearities.
Introduction
In high-dimensional statistics, linear models are often preferred for their interpretability and performance when the number of features ($p$) exceeds the sample size ($n$). However, real-world relationships are frequently non-linear. While Additive Isotonic Models (AIMs) were designed to accommodate monotone transformations, they suffer from two major drawbacks: the requirement to pre-specify directionality (increasing vs. decreasing) for each feature and high computational complexity in high dimensions. Sparse Linear Isotonic Models (SLIMs) bridge this gap by leveraging sparsity and rank-based correlations to decouple feature selection from functional form estimation.
Methods
The SLIM framework models the conditional expectation as: $$E[y|x] = \sum_{j=1}^{p} \tilde{\theta}_j f_j(x_j)$$ where $\tilde{\theta}$ is a sparse vector and each $f_j$ is a monotone increasing function. The sign of $\tilde{\theta}_j$ automatically handles whether the overall effect of feature $j$ is increasing or decreasing, removing the need for a "direction oracle."
The estimation process follows a two-step algorithm:
- Sparsity Estimation: The Kendall’s tau Dantzig Selector (KDS) is employed to identify active features. Because Kendall’s tau is a rank-based correlation, it is invariant to monotone transformations, allowing the algorithm to estimate feature importance and direction without knowing the actual shapes of $f_j$.
- Functional Estimation: Once the active features are identified, the functions are fitted using Standardized Isotonic Regression. This step utilizes a Cyclic Block Coordinate Descent approach, with sub-problems solved efficiently via the Pooled Adjacent Violators Algorithm (PAVA).
Results
The model was evaluated using synthetic datasets with $p = 500$ features and $s = 10$ relevant features across various monotone transformations, including cubic, exponential, and logarithmic forms.
Prediction Accuracy
SLIMs (referred to as LIM in experimental results) significantly outperform standard linear models in terms of prediction error. As shown in the figure below, the linear model fails to capture the non-linear "bends" in the monotone functions, leading to high bias. In contrast, SLIM's prediction error decreases consistently as the sample size $n$ increases.
Function Approximation
Visual analysis confirms that the estimated functions $\hat{f}_j$ accurately track the true underlying non-linear curves. The algorithm successfully recovers diverse monotone shapes from noisy high-dimensional data, as illustrated across the ten relevant features in the following visualization.
Discussion
SLIMs offer a powerful alternative to linear models by providing non-parametric flexibility with the theoretical efficiency of sparse linear methods. By leveraging rank-based statistics, the authors decouple the problem of variable selection from shape estimation, making high-dimensional non-linear estimation computationally feasible. While current theoretical guarantees rely on transelliptical data distributions, the empirical success of SLIMs suggests broad applicability in fields like genomics and finance where monotone but non-linear relationships are prevalent. Future work should focus on validating these models on real-world high-dimensional datasets and exploring joint estimation techniques.
Summary updated