UCLA

Deep neural networks are are able to optimize and generalize better than classical learning theory would suggest. In the past several years, this overperformance has been linked to overparameterization: learning is easier when the loss landscape is high-dimensional. However, much of the existing theory on overparameterization lives in scaling regimes that do not reflect practice, such as ones with extremely large input dimension or level of overparameterization. In this dissertation, we bridge this gap by investigating optimization and generalization in moderate-dimensional regimes of data dimension and model parameterization.In Chapter 2, we study the loss landscape of shallow and deep, mildly overparameterized ReLU neural networks on a generic dataset under the squared loss. We show by count and volume that most activation patterns correspond to parameter regions with no bad local minima. To make these results quantitative, a natural framework is to consider the smallest eigenvalue of the neural tangent kernel (NTK). Existing bounds for the smallest eigenvalue of the NTK require distributional assumptions on the data and are limited to high-dimensional input data. In Chapter 3, we bound the smallest eigenvalue of the NTK while removing both of these requirements. In Chapter 4, we investigate the generalization of neural networks with moderate-dimensional input data trained with gradient descent. We consider noisy input data that can be decomposed into a signal and a noise component, and characterize the generalization error of leaky ReLU networks in terms of the signal-to-noise ratio of the data.The core of this thesis develops theoretical frameworks capable of understanding the behavior of neural networks in moderate dimensions. This bridges the gap between existing theory in high dimensions and the scaling used in practice. This is a necessary step towards building a theory which can predict the performance of models over different choices of hyperparameters beyond limiting cases.In the remainder of this thesis, we apply ideas from learning theory to graph neural networks (GNNs). In Chapter 5, we study the phenomenon of oversquashing in graph neural networks, and frame it in terms of spectral properties of the underlying graph. In Chapter 6, we propose an algorithm drawing on this perspective which optimizes the connectivity of GNNs to improve optimization.