The investigation of machine learning model complexity dates back to decades ago. A series of early studies in 1990s discuss the complexity of classical machine learning models [1]}, [2]}, [3]}, [4]}. One representative model is decision tree [5]}, whose complexity is always measured by tree depth [3]} and number of leaf nodes [1]}. Another frequent subject in model complexity analysis is logistic regression, which is the foundation of a large number of parameterized models. The model complexity of logistic regression is investigated from the perspectives of Vapnik-Chervonenicks theory [8]}, [9]}, Rademacher complexity [10]}, Fisher Information matrix [4]}, and the razor of model [12]}. Here, the razor of model is a theoretical index of the complexity of a parametric family of models comparing to the true distribution.
However, deep learning models are dramatically different from those classical machine learning models discussed decades ago [13]}. The complexity analysis of classical machine learning models cannot be directly applied or straightforwardly extended to deep models.
