Multivariate Dyadic Regression Trees for Sparse Learning Problems

Han Liu, Xi ChenNeurIPS 2010

Introduction

This paper introduces Multivariate Dyadic Regression Trees (MDRTs), a novel nonparametric method designed for high-dimensional problems where multiple outputs depend on a small, shared subset of variables. By using a unique sparsity-inducing penalty, MDRTs automatically adapt to both the smoothness of the underlying function and the hidden sparsity of the data, achieving nearly optimal statistical convergence rates.

The Challenge of High-Dimensional Multivariate Data

In many modern data science applications—such as predicting gene expression levels or chemical concentrations—researchers face two major hurdles:

  1. Multivariate Outputs: The need to predict several related quantities simultaneously.
  2. The Curse of Dimensionality: Datasets often contain a massive number of potential input variables ($d$), but the true relationship might only depend on a tiny subset ($r \ll d$).

Standard tools like CART (Classification and Regression Trees) offer flexibility but lack strong theoretical guarantees in high-dimensional, sparse settings. Conversely, parametric models (like Lasso) provide robust theory but often fail when the underlying relationship is non-linear or complex. The authors aim to bridge this gap with a tree-based method that is both flexible and theoretically "optimal" for sparse, high-dimensional multivariate regression.

Proposed Method: MDRTs

The authors propose Multivariate Dyadic Regression Trees. The term "dyadic" indicates that the tree only splits variables exactly at their midpoints. This constraint simplifies the search space and allows for rigorous mathematical analysis.

The core innovations include:

  • Sparsity-Inducing Penalty: Unlike traditional trees that only penalize the number of leaf nodes, MDRTs use a new penalty term that explicitly accounts for the number of active variables used across the entire tree. This forces the model to select only the most relevant features.
  • Local Polynomial Fits: Instead of predicting a constant value at each leaf, MDRTs can fit $m$-th order polynomials, allowing them to capture smoother, more complex functions.
  • Two-Stage Algorithm: Because finding the "perfect" tree is computationally impossible in high dimensions, the authors provide a greedy "Grow and Prune" strategy. They also introduce a Randomized Greedy version to help the algorithm escape local optima and discover better variable subsets.

Datasets and Evaluation

The researchers evaluated MDRTs using both controlled simulations and real-world benchmarks:

  • Synthetic Data: High-dimensional ($d=100$) datasets with varying levels of correlation and non-linearity (linear, additive non-linear, and complex interactions).
  • Chemometrics (Chem): Data from a simulated polyethylene reactor ($n=56, d=22, p=6$).
  • Boston Housing: A classic dataset ($n=506, d=10$) where the authors added 10 "fake" noise variables to test the model's ability to ignore irrelevant data.
  • Space ga: Election data involving spatial coordinates across 3,107 US counties.

Key Insights

  • Theoretical Adaptation: MDRTs do not need to be told how smooth the function is or how many variables are relevant. The mathematical proof shows the estimator "self-tunes" to the optimal rate of convergence ($n^{-2\alpha/(2\alpha+r)}$) automatically.
  • VC-Dimension Grounding: The novel penalty is derived from bounding the Vapnik-Chervonenkis (VC) dimension of the function class, providing a solid bridge between algorithmic tree-building and statistical learning theory.
  • Joint Sparsity: By forcing all output dimensions to share the same tree structure (and thus the same active variables), the model gains significant power in identifying the true underlying features compared to building separate trees for each output.

Key Results

MDRTs demonstrated strong empirical performance across multiple tests, particularly in variable selection and error reduction.

  • Superior Variable Selection: In the Boston Housing test with added noise, MDRTs with linear leaf fits ($M=1$) consistently ignored the artificial noise variables, whereas CART and other variants often mistakenly included them.
  • Lower Error on Real-World Data: On the Chemometrics and Housing datasets, MDRTs achieved significantly lower Mean Squared Error (MSE) than standard CART. For example, on the Housing data, the randomized MDRT (R, M=1) achieved an MSE of ~20.18 compared to CART's 25.91.
Results on real-world datasets showing MDRT outperforming CART
  • Robustness to Interactions: MDRTs performed exceptionally well on "Model 3" in the synthetic tests, which featured complex three-way interactions that typically baffle simpler additive models. The randomized greedy approach with linear fits (R, M=1) significantly outperformed CART in both variable selection accuracy and MSE.
Performance on synthetic Model 3 with complex interactions

Limitations and Future Work

  • Greedy Heuristics: While the greedy algorithm is fast, it isn't guaranteed to find the mathematically optimal tree. The randomized version helps, but a gap remains between the theory (which assumes the best tree is found) and practical implementation.
  • Large Constants: The theoretical penalty constants are pessimistic. In practice, users must rely on cross-validation to find the right regularization strength ($\lambda$), as the theoretical values would result in overly pruned trees.
  • Computational Scaling: Building these trees in extremely high dimensions with high-order polynomials ($M > 1$) can still be computationally demanding. Future work could focus on further optimizing the split-selection process.

Summary updated

BibTeX
@inproceedings{liu2010multivariate,
  author = {Han Liu and Xi Chen},
  title = {{Multivariate Dyadic Regression Trees for Sparse Learning Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
}
Figure