Understanding Complexity and the Bias-Variance Tradeoff in High Dimensions: Theory and Data Evidence

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The past decade has witnessed a significant rise in the usage of very large machine-learning models in modern data problems; these models have shown success in a variety of tasks, such as image classification, language translation, and speech recognition. More recently, machine learning is entering new fields, such as robotics, autonomous driving, and medicine. However, these models are often not robust to perturbations and are vulnerable to attacks by adversaries. These shortcomings warrant an urgent and insightful understanding of the "black-box" nature of these models. The principal investigator plans to understand these models by characterizing their "complexity" in a technical manner. A new complexity measure, based on the principle of minimum description length, sheds insight into classical statistical foundations as well as informing how and when these new high-dimensional models will work. This novel complexity measure is promising to enable applications to mission-critical fields like precision medicine, where the collection of a labeled dataset is expensive, by sample-size calculations and improving model selection with limited data. This research has both theoretical and applied impacts in the fields of statistics and machine learning including deep learning. In the duration of the project, graduate students will be trained in theory, domain-driven data science, and open-source software development. The research will be further disseminated through courses, an upcoming book, and presentations at workshops and conferences. Deep neural networks (DNNs) in many cases generalize well in the sense that a DNN trained on one task often performs well on similar unseen data for the same task. They can do so despite being highly overparameterized, i.e., the number of parameters is much larger than the number of training samples. Occam's razor and the bias-variance trade-off wisdom suggest to prefer a simple model when choosing from amongst models of varying complexity with similar performance. The good performance of DNNs, despite the overparametrization, has led many researchers to question the validity of the classical statistical principle of bias-variance trade-off (and preferring a simple model) for high-dimensional settings common in modern machine learning (ML) and statistical tasks. In this project, the principal investigator begins by reconsidering the definition of a valid complexity measure – which forms the basis of Occam’s razor and the bias-variance trade-off principle – for high-dimensional models. Finding one such measure for high-dimensional models has remained a difficult task. Merely counting the number of parameters is not a valid complexity measure, especially when the number of training examples is small. The principle of minimum description length will be used to provide a systematic approach to understanding the complexity of high-dimensional linear models, kernel methods, and finally DNNs. The complexity measure will serve as a basis for understanding key concepts such as the bias-variance trade-off and for further analysis into high-dimensional models. The theoretical results will be augmented with an extensive set of data-inspired experiments. After establishing the bias-variance trade-off with the new complexity measures, these measures will then be investigated for (i) selecting a simple model from amongst a set of competitive models, where simple will be defined via the MDL-based complexity and not the number of parameters, and (ii) regularizing or pruning a large (pre-trained) model, for example, in a transfer learning setting with limited dataset, by trading off the training performance with the complexity of the model. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.