  Despite the extreme popularity of deep learning in science and industry, its
formal understanding is limited. This thesis puts forth notions of rank as key
for developing a theory of deep learning, focusing on the fundamental aspects
of generalization and expressiveness. In particular, we establish that
gradient-based training can induce an implicit regularization towards low rank
for several neural network architectures, and demonstrate empirically that this
phenomenon may facilitate an explanation of generalization over natural data
(e.g., audio, images, and text). Then, we characterize the ability of graph
neural networks to model interactions via a notion of rank, which is commonly
used for quantifying entanglement in quantum physics. A central tool underlying
these results is a connection between neural networks and tensor
factorizations. Practical implications of our theory for designing explicit
regularization schemes and data preprocessing algorithms are presented.
