Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization

Tomaso A. Poggio, Andrzej Banburski, Qianli Liao

Abstract

While deep learning is successful in a number of applications, it is not yet well understood theoretically. A satisfactory theoretical characterization of deep learning however, is beginning to emerge. It covers the following questions: 1) representation power of deep networks 2) optimization of the empirical risk 3) generalization properties of gradient descent techniques --- why the expected error does not suffer, despite the absence of explicit regularization, when the networks are overparametrized? In this review we discuss recent advances in the three areas. In approximation theory both shallow and deep networks have been shown to approximate any continuous functions on a bounded domain at the expense of an exponential number of parameters (exponential in the dimensionality of the function). However, for a subset of compositional functions, deep networks of the convolutional type can have a linear dependence on dimensionality, unlike shallow networks. In optimization we discuss the loss landscape for the exponential loss function and show that stochastic gradient descent will find with high probability the global minima. To address the question of generalization for classification tasks, we use classical uniform convergence results to justify minimizing a surrogate exponential-type loss function under a unit norm constraint on the weight matrix at each layer -- since the interesting variables for classification are the weight directions rather than the weights. Our approach, which is supported by several independent new results, offers a solution to the puzzle about generalization performance of deep overparametrized ReLU networks, uncovering the origin of the underlying hidden complexity control.

Introduction

Despite the massive success of deep learning, a rigorous theoretical foundation has lagged behind empirical results. Modern models often utilize millions more parameters than data points (overparametrization), yet they consistently avoid overfitting. Furthermore, we optimize non-convex loss functions, yet we almost always find high-quality solutions. This paper addresses three core mysteries: how deep networks avoid the curse of dimensionality, why they optimize efficiently despite non-convexity, and why they generalize without explicit regularization.

Approximation: The Power of Compositionality

A fundamental question in deep learning is why deep architectures outperform shallow ones. The authors argue that the world is inherently hierarchical, and deep networks—particularly those of the convolutional type—are uniquely suited to represent these compositional functions.

While both shallow and deep networks can approximate any continuous function, they both suffer from the "curse of dimensionality," requiring an exponential number of parameters relative to the function's dimensionality. However, for functions that can be decomposed into a hierarchy of local functions (compositional functions), deep networks offer a significant advantage.

Hierarchical tree structure representing a compositional function.

As shown in the figure above, deep networks can mirror the hierarchical structure of tasks like visual recognition. For these compositional functions, deep networks achieve an accuracy $\epsilon$ with $N = O(n \epsilon^{-2/m})$ parameters, whereas shallow networks require $N = O(\epsilon^{-n/m})$. As the dimensionality $n$ grows, deep networks remain efficient while shallow ones become computationally intractable.

Comparison of shallow (a) and deep hierarchical (b) architectures and their corresponding function trees.

Optimization: Navigating the Loss Landscape

The optimization of deep networks involves minimizing a non-convex empirical risk. The authors analyze the loss landscape, specifically for exponential-type losses like cross-entropy. They find that in overparametrized networks, global minima are "completely degenerate," meaning they exist in very flat, high-volume regions of the landscape.

Stochastic Gradient Descent (SGD) is statistically more likely to find these large, flat basins than narrow local minima. Analysis of the Hessian eigenvalues at critical points reveals that at global minima (at infinity), all eigenvalues are zero, whereas at other critical points (saddles or local minima), at least one eigenvalue is non-zero. This structural difference explains why SGD effectively avoids "bad" regions.

Generalization: Implicit Complexity Control

One of the most striking insights is the discovery of implicit regularization. Even without explicit techniques like weight decay or dropout, gradient descent on exponential loss implicitly enforces a unit $L_2$ norm constraint on the weight directions.

By treating gradient descent as a continuous-time dynamical system, the authors show that the optimization process itself acts as a regularizer by maximizing the classification margin. This offers a solution to the puzzle of why overparametrized ReLU networks generalize well: the hidden complexity control is baked into the optimization dynamics.

Conclusion

This unified framework provides a theoretical basis for the "unreasonable effectiveness" of deep learning. By aligning network architecture with the compositional nature of real-world data and leveraging the implicit regularization of gradient descent, deep networks overcome the traditional challenges of dimensionality and generalization. Future work will focus on expanding this analysis to a broader range of loss functions and relaxing assumptions to better understand the trade-offs between model complexity and noise.

Summary updated

Abstract

While deep learning is successful in a number of applications, it is not yet well understood theoretically. A satisfactory theoretical characterization of deep learning however, is beginning to emerge. It covers the following questions: 1) representation power of deep networks 2) optimization of the empirical risk 3) generalization properties of gradient descent techniques --- why the expected error does not suffer, despite the absence of explicit regularization, when the networks are overparametrized? In this review we discuss recent advances in the three areas. In approximation theory both shallow and deep networks have been shown to approximate any continuous functions on a bounded domain at the expense of an exponential number of parameters (exponential in the dimensionality of the function). However, for a subset of compositional functions, deep networks of the convolutional type can have a linear dependence on dimensionality, unlike shallow networks. In optimization we discuss the loss landscape for the exponential loss function and show that stochastic gradient descent will find with high probability the global minima. To address the question of generalization for classification tasks, we use classical uniform convergence results to justify minimizing a surrogate exponential-type loss function under a unit norm constraint on the weight matrix at each layer -- since the interesting variables for classification are the weight directions rather than the weights. Our approach, which is supported by several independent new results, offers a solution to the puzzle about generalization performance of deep overparametrized ReLU networks, uncovering the origin of the underlying hidden complexity control.
BibTeX
@inproceedings{poggio2020theoretical,
  author = {Tomaso A. Poggio and Andrzej Banburski and Qianli Liao},
  title = {{Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2020},
  doi = {10.1073/pnas.1907369117},
}
Figure