arXiv Machine Learning
4d ago

Vectorized Dynamic Histograms for Sparse Oblique Forests

The paper presents optimizations for Sparse Oblique (SPO) forests in Google’s Yggdrasil Decision Forests, addressing training speed issues caused by runtime sampling of sparse linear feature combinations. By fixing inefficiencies and introducing two new methods—hierarchical AVX2/AVX-512 vectorized histogram filling and runtime‑dynamic histograms—the authors achieve 2–5× speedups for both Gradient Boosted Trees and Random Forests, bringing SPO‑RF training time on par with axis‑aligned RFs. Extensive evaluation on 19 datasets, including up to 10.5 million rows and 1.6 million features, demonstrates these improvements without compromising accuracy.

By Ariel Lubonja, Jungsang Yoon, Haoyin Xu, Yue Wan, Yilin Xu, Richard Stotz, Mathieu Guillame-Bert, Joshua T. Vogelstein, Randal Burns