VC Dimensions for Deep Neural Networks with Bounded-Rank Weight Matrices
Guan, Junyi
Guan, Junyi
Author
Supervisor
Department
Machine Learning
Embargo End Date
2024-01-01
Type
Thesis
Date
2024
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Deep neural networks (DNNs) have seen immense success in the past decade, yet their lack of interpretability remains a challenge. Recent research on the VC (Vapnik-Chervonenkis) dimension of DNNs has provided valuable insights into the underlying mechanisms of deep learning's powerful generalization capabilities. Understanding the VC dimension offers a promising path toward unraveling the enigma of deep learning, ultimately leading to more interpretable and trustworthy AI systems. In this paper, we study the VC dimensions for DNNs with piecewise polynomial activations and bounded-rank weight matrices. Our main results show that the VC dimensions for DNNs with weight matrices that have bounded rank $r$ are at most $\mathcal{O}(nrL^2\log (nrL))$, where $n$ is the width of the network, and $L$ is the depth of the network. We also construct a ReLU DNN with bounded rank $r$ that can achieve the VC dimension $\Omega(nr)$, which confirms that the upper bound we obtain is nearly tight for large $n$. Based on these bounds, we compare the generalization power in terms of VC dimensions for various DNN architectures.
Citation
J. Guan, "VC Dimensions for Deep Neural Networks with Bounded-Rank Weight Matrices"MS. Thesis, Machine Learning, MBZUAI, Abu Dhabi, UAE, 2024