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