On the expressive power of decision tree ensembles

Decision trees are widely used in machine learning, statistics and data mining. Predictive models based on decision trees show outstanding results in terms of accuracy and training time. Especially on heterogeneous tabular datasets. Performance, simplicity and integrity make this family of algorithms one of the most popular in data science. One important hyper-parameter of decision tree training algorithms is maximum depth of the trees. This paper proves theoretical result that shows how maximum depth of decision trees limits the expressive power of ensemble. This result is applicable to such tree based algorithms as plain Decision Tree, Random Forest, GBDT and others.