# Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 66 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Builds on (most cited first, 26 of 26)

- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Learned Step Size Quantization](https://mlsanity.com/paper/1902.08153/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Distilling a Neural Network Into a Soft Decision Tree](https://mlsanity.com/paper/1711.09784/) (2017)
- [Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data](https://mlsanity.com/paper/1909.06312/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1](https://mlsanity.com/paper/1602.02830/) (2016)
- [Deep Neural Decision Trees](https://mlsanity.com/paper/1806.06988/) (2018)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Adaptive Neural Trees](https://mlsanity.com/paper/1807.06699/) (2018)
- [The Tree Ensemble Layer: Differentiability meets Conditional Computation](https://mlsanity.com/paper/2002.07772/) (2020)
- [The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent](https://mlsanity.com/paper/1904.06963/) (2019)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [Neural Random Forests](https://mlsanity.com/paper/1604.07143/) (2016)
- [A Neural Networks Committee for the Contextual Bandit Problem](https://mlsanity.com/paper/1409.8191/) (2014)
- [Efficient non-greedy optimization of decision trees](https://mlsanity.com/paper/1511.04056/) (2015)
- [Neural Decision Trees](https://mlsanity.com/paper/1702.07360/) (2017)
- [Random Forest for the Contextual Bandit Problem - extended version](https://mlsanity.com/paper/1504.06952/) (2015)
- [Stochastic Gradient Trees](https://mlsanity.com/paper/1901.07777/) (2019)
- [Learning Binary Decision Trees by Argmin Differentiation](https://mlsanity.com/paper/2010.04627/) (2020)

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

- [GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent](https://mlsanity.com/paper/2305.03515/) (2023)
- [Treeformer: Dense Gradient Trees for Efficient Attention Computation](https://mlsanity.com/paper/2208.09015/) (2022)
- [Vanilla Gradient Descent for Oblique Decision Trees](https://mlsanity.com/paper/2408.09135/) (2024)
- [A Neural Tangent Kernel Perspective of Infinite Tree Ensembles](https://mlsanity.com/paper/2109.04983/) (2021)
- [Towards a Unified Framework for Uncertainty-aware Nonlinear Variable Selection with Theoretical Guarantees](https://mlsanity.com/paper/2204.07293/) (2022)
- [Enhancing Group Fairness in Online Settings Using Oblique Decision Forests](https://mlsanity.com/paper/2310.11401/) (2023)
- [Can a Single Tree Outperform an Entire Forest?](https://mlsanity.com/paper/2411.17003/) (2024)
- [LHT: Statistically-Driven Oblique Decision Trees for Interpretable Classification](https://mlsanity.com/paper/2505.04139/) (2025)
- [Hinge Regression Tree: A Newton Method for Oblique Regression Tree Splitting](https://mlsanity.com/paper/2602.05371/) (2026)
- [Multiple Instance Learning with Trainable Decision Tree Ensembles](https://mlsanity.com/paper/2302.06601/) (2023)
- [Approximation-Free Differentiable Oblique Decision Trees](https://mlsanity.com/paper/2605.07837/) (2026)
- [Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models](https://mlsanity.com/paper/2605.23422/) (2026)
- [MIL-BERT: Classification of Arbitrarily Large Text with Performance and Explanatory Guarantees](https://mlsanity.com/paper/2608.20636/) (2026)
- [Adaptive Multi-Branching for Shallow Decision Tree Induction](https://mlsanity.com/paper/2608.29262/) (2026)

## Abstract (arXiv)

Decision trees provide a rich family of highly non-linear but efficient models, due to which they continue to be the go-to family of predictive models by practitioners across domains. But learning trees is challenging due to their discrete decision boundaries. The state-of-the-art (SOTA) techniques resort to (a) learning textitsoft trees thereby losing logarithmic inference time; or (b) using methods tailored to specific supervised learning settings, requiring access to labeled examples and loss function. In this work, by leveraging techniques like overparameterization and straight-through estimators, we propose a unified method that enables accurate end-to-end gradient based tree training and can be deployed in a variety of settings like offline supervised learning and online learning with bandit feedback. Using extensive validation on standard benchmarks, we demonstrate that our method provides best of both worlds, i.e., it is competitive to, and in some cases more accurate than methods designed textitspecifically for the supervised settings; and in bandit settings, where most existing tree learning techniques are not applicable, our models are still accurate and significantly outperform the applicable SOTA methods.