# A Comprehensive Approach to Universal Piecewise Nonlinear Regression Based on Trees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2013.

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

- [Generalized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2109.09212/) (2021)
- [Second Order Regret Bounds Against Generalized Expert Sequences under Partial Bandit Feedback](https://mlsanity.com/paper/2204.06660/) (2022)
- [Data Dependent Regret Guarantees Against General Comparators for Full or Bandit Feedback](https://mlsanity.com/paper/2303.06526/) (2023)

## Abstract (arXiv)

In this paper, we investigate adaptive nonlinear regression and introduce tree based piecewise linear regression algorithms that are highly efficient and provide significantly improved performance with guaranteed upper bounds in an individual sequence manner. We use a tree notion in order to partition the space of regressors in a nested structure. The introduced algorithms adapt not only their regression functions but also the complete tree structure while achieving the performance of the "best" linear mixture of a doubly exponential number of partitions, with a computational complexity only polynomial in the number of nodes of the tree. While constructing these algorithms, we also avoid using any artificial "weighting" of models (with highly data dependent parameters) and, instead, directly minimize the final regression error, which is the ultimate performance goal. The introduced methods are generic such that they can readily incorporate different tree construction methods such as random trees in their framework and can use different regressor or partitioning functions as demonstrated in the paper.