[edit]

# “No Free Lunch” in Neural Architectures? A Joint Analysis of Expressivity, Convergence, and Generalization

*Proceedings of the Second International Conference on Automated Machine Learning*, PMLR 224:14/1-29, 2023.

#### Abstract

The prosperity of deep learning and automated machine learning (AutoML) is largely rooted in the development of novel neural networks – but what defines and controls the “goodness” of networks in an architecture space? Test accuracy, a golden standard in AutoML, is closely related to three aspects: (1) expressivity (how complicated functions a network can approximate over the training data); (2) convergence (how fast the network can reach low training error under gradient descent); (3) generalization (whether a trained network can be generalized from the training data to unseen samples with low test error). However, most previous theory papers focus on fixed model structures, largely ignoring sophisticated networks used in practice. To facilitate the interpretation and understanding of the architecture design by AutoML, we target connecting a bigger picture: how does the architecture jointly impact its expressivity, convergence, and generalization? We demonstrate the “no free lunch” behavior in networks from an architecture space: given a fixed budget on the number of parameters, there does not exist a single architecture that is optimal in all three aspects. In other words, separately optimizing expressivity, convergence, and generalization will achieve different networks in the architecture space. Our analysis can explain a wide range of observations in AutoML. Experiments on popular benchmarks confirm our theoretical analysis. Our codes are attached in the supplement.