Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Abstract

This paper presents a review of the current state of research on theoretical approaches to complexity in deep learning and their relation to generalization. Methodologically, the review is structured as a scoping review: it documents bibliographic sources, deduplication and semi-automated corpus narrowing, expert screening, and the composition of a final analytical publication set. The central question is why classical complexity measures, despite their foundational role in statistical learning theory, are insufficient for explaining the behavior of modern overparameterized neural networks. VC dimension, Rademacher complexity, PAC-Bayesian bounds, and information-theoretic approaches remain indispensable as a baseline analytical language, yet they mainly characterize worst-case hypothesis-class capacity and only partially reflect the geometry of the learned solution, the optimization trajectory, and architectural inductive biases. The main focus is therefore placed on contemporary approaches based on the loss landscape, Hessian spectra, optimization methods, and empirical scaling laws. The review develops a synthetic interpretation of the field according to which a useful theory of complexity for deep learning should describe not only the expressive capacity of a class, but also the effective complexity of the solutions actually reached by concrete algorithms on concrete data.

Keywords: complexity theory, generalization, deep learning, VC dimension, Rademacher complexity, loss landscape, Hessian, double descent, scaling laws.