Research map / Learning theory and algorithms / Combinatorial and search optimization
Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes optimal dynamic programming methods for piecewise constant, piecewise simple linear, and piecewise multiple linear regression trees, with special depth-two solvers that scale one or more orders of magnitude beyond prior optimal methods.
Problem
Optimal regression trees are NP-hard and existing optimal methods (MIP, CP, and DP such as OSRT) scale poorly; no scalable optimal DP method existed for piecewise linear regression trees.
Approach
Extends the STreeD depth-two precomputation trick to regression by rewriting SSE as sums of (y, y^2, 1) per instance, and derives per-instance sufficient statistics for simple linear regression so that depth-two trees with linear leaves can be solved efficiently; also introduces the first optimal DP for multiple linear (elastic net) leaves.
Key results
- SRT-C is on average 18 times faster than OSRT (geometric mean), and 131 times faster at depth three.
- The depth-two algorithm improves run time of SRT-C and SRT-SL by factors of about 8 and 10 on average.
- SRT-SL achieves the best out-of-sample R2 on most datasets among piecewise linear methods, with SRT-L as runner-up; both significantly outperform GUIDE-SL and GUIDE-L.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SRT-C instead of OSRT for piecewise constant regression trees | Piecewise constant regression trees · Benchmark problem instances | run time: 18 times faster on average; 131 times faster for depth three | Helped |
| Use SRT-C instead of GUIDE for piecewise constant regression trees | Piecewise constant regression trees · Out-of-sample benchmarks | R2 | Helped |
| Use SRT-SL instead of GUIDE-SL for piecewise simple linear regression | Piecewise simple linear regression trees · Out-of-sample benchmarks | R2 | Helped |
| Add the depth-two solver (ablation) | SRT-C · Regression tree search | run time: factor 8 | Helped |
| Add the depth-two solver (ablation) | SRT-SL · Regression tree search | run time: factor 10 | Helped |
| Add the depth-two solver (ablation) | SRT-C · Trees of depth three | run time: factor 20 | Helped |
| Add the depth-two solver (ablation) | SRT-SL · Trees of depth three | run time: factor 12 | Helped |
Surprising findings
- SRT-SL runs nearly as fast as SRT-C and much faster than OSRT, so fitting simple linear models in leaves is cheaper than fitting constants in prior optimal methods.
- OSRT exceeds memory limits for datasets with 10^6 or more instances, and several baselines time out on the Household data set.
Limitations
- Multiple linear regression has no special depth-two algorithm; scales worse with instances due to coordinate descent.
- Only binary features are used for tree splits; continuous features are binarized with at most 10 splits.
- Out-of-sample differences from heuristics are small and mostly not significant; complexity tuning remains understudied.
Experimental setup
Datasets: Airfoil Auction Auto MPG Energy (C) Energy (H) Household Optical Net. Real Estate Seoul Bike Servo Synch. Yacht
Benchmarks: UCI regression datasets (12 datasets)
Metrics: run time out-of-sample R2 training R2 number of trees computed within time limit
Baselines: CART GUIDE IAI ORT DTIP OSRT IAI-L ORT-L GUIDE-SL GUIDE-L LR
Builds on: STreeD OSRT DL8.5 Demirovic et al. 2022 depth-two solver GLMNet
Closest papers by meaning
- CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees (ICML 2026 · similarity 0.90)
- Optimal Sparse Regression Trees (AAAI 2023 · similarity 0.88)
- A faster training algorithm for regression trees with linear leaves, and an analysis of its complexity (NeurIPS 2025 · similarity 0.88)
- Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound (AAAI 2025 · similarity 0.87)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.86)
- Regression Trees Know Calculus (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.