# Maximum Margin Interval Trees

arXiv: https://arxiv.org/abs/1710.04234 · HTML: https://mlsanity.com/paper/1710.04234/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2017.

## Built on by (most cited first, 7 of 7)

- [Weakly Supervised Regression with Interval Targets](https://mlsanity.com/paper/2306.10458/) (2023)
- [Penalty Learning for Optimal Partitioning using Multilayer Perceptron](https://mlsanity.com/paper/2408.00856/) (2024)
- [Optimizing ROC Curves with a Sort-Based Surrogate Loss Function for Binary Classification and Changepoint Detection](https://mlsanity.com/paper/2107.01285/) (2021)
- [Interval Regression: A Comparative Study with Proposed Models](https://mlsanity.com/paper/2503.02011/) (2025)
- [Efficient line search for optimizing Area Under the ROC Curve in gradient descent](https://mlsanity.com/paper/2410.08635/) (2024)
- [Finite Sample Complexity Analysis of Binary Segmentation](https://mlsanity.com/paper/2410.08654/) (2024)
- [Learning Penalty for Optimal Partitioning via Automatic Feature Extraction](https://mlsanity.com/paper/2505.07413/) (2025)

## Abstract (arXiv)

Learning a regression function using censored or interval-valued output data is an important problem in fields such as genomics and medicine. The goal is to learn a real-valued prediction function, and the training output labels indicate an interval of possible values. Whereas most existing algorithms for this task are linear models, in this paper we investigate learning nonlinear tree models. We propose to learn a tree by minimizing a margin-based discriminative objective function, and we provide a dynamic programming algorithm for computing the optimal solution in log-linear time. We show empirically that this algorithm achieves state-of-the-art speed and prediction accuracy in a benchmark of several data sets.