Research map / Learning theory and algorithms / Prediction and decision losses

A faster training algorithm for regression trees with linear leaves, and an analysis of its complexity

NeurIPS 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Tree ensemble optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Speeds up the Tree Alternating Optimization (TAO) algorithm for regression trees with linear leaves while producing exactly the same results, with a complexity analysis.

Problem

Training regression trees with linear predictors in the leaves: greedy CART-style recursive partitioning gives larger, less accurate trees, while the TAO algorithm guarantees monotonic objective decrease but is slow.

Approach

Modify the TAO algorithm so that it yields exactly the same output as the original but runs much faster, supported by an analysis of its computational complexity.

Key results

• The modified TAO produces exactly the same result as the original TAO but is much faster, per the abstract.

Experimental setup

Baselines: CART

Builds on: Tree Alternating Optimization CART

Closest papers by meaning

• Smaller, more accurate regression forests using tree alternating optimization (ICML 2020 · similarity 0.91)
• Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach (ICML 2024 · similarity 0.88)
• Regression Trees Know Calculus (NeurIPS 2025 · similarity 0.87)
• Minimax Rates and Spectral Distillation for Tree Ensembles (NeurIPS 2026 · similarity 0.86)
• Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.85)
• Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.85)