Source-linked AI summary
Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
Tomaso Poggio, Andrzej Banburski, Qianli Liao
TL;DR
Deep learning theory must explain representation, optimization, and generalization, including why overparametrized networks can generalize without explicit regularization. This review synthesizes approximation, optimization, and generalization results, finding compositional-function advantages for deep networks, high-probability global optimization, and implicit norm control. It also identifies open problems involving approximation, optimization, multilayer convergence, approximation–estimation trade-offs, and separability.
Problem
The review addresses how deep networks represent functions, optimize empirical risk, and generalize despite overparametrization and no explicit regularization.
Method
The paper synthesizes approximation theory, exponential-loss optimization, and uniform-convergence analysis with unit-norm constraints on layerwise weight directions.
Results
Deep networks avoid the curse of dimensionality for important compositional functions, stochastic gradient descent finds global minima with high probability, and gradient descent supplies implicit norm control for classification generalization.
Takeaways & Limitations
Deep convolutional architectures are theoretically advantageous for hierarchically local compositional functions, while hidden complexity control helps explain generalization of overparametrized ReLU networks.
Takeaways & Limitations
The framework leaves open fuller approximation results, general-loss local-minima classification, multilayer weight-convergence analysis, approximation–estimation trade-offs, and relaxed separability assumptions.
Abstract
from arXiv · showhide
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.
1. Introduction
Deep learning has achieved broad practical success, but its theoretical understanding has lagged. The review organizes emerging theory around approximation, optimization, and generalization in overparametrized networks.
- The review addresses approximation properties, empirical-risk optimization, and generalization properties of gradient-descent techniques.
- It asks why expected error does not suffer in overparametrized networks despite the absence of explicit regularization.
A. When Can Deep Networks Avoid the Curse of Dimensionality?.
Deep networks can avoid the curse of dimensionality for important compositional functions, especially hierarchically local ones, while stochastic gradient descent and hidden norm control address optimization and generalization.
- Deep networks theoretically avoid the curse of dimensionality for an important class of compositional functions, unlike shallow networks.
- For hierarchically local compositional functions, deep convolutional-type networks achieve this without requiring weight sharing.
- The review connects deep-network theory to overparametrization, stochastic gradient descent, exponential loss, and ReLU homogeneity.
- The hierarchical approximation construction associates network nodes with constituent functions and uses ReLU units to represent the resulting ridge functions.
- The relevant advantage of convolutional networks is locality at each hierarchical level, not weight sharing.
B. Related Work.
Related work includes recent studies of deep-network approximation and frameworks for determining network complexity needed to approximate target functions to a specified accuracy.
- Recent papers derive upper bounds showing that deep networks can avoid the curse of dimensionality for certain important function classes.
- The general approximation paradigm asks how much network complexity guarantees approximation of an unknown target function within accuracy ϵ.
C. Degree of approximation.
The approximation analysis compares shallow and deep networks using norms and function classes that formalize accuracy, complexity, smoothness, and compositional structure.
- The sup norm is used to make approximation results independent of the unknown input-data distribution.
- Approximation degree is defined as the infimum norm distance between a target function and networks with a specified number of units.
- The target-function class is specified by a smoothness and compositional subspace characterized by parameters m and d.
- The section compares one-hidden-layer networks with deep networks to characterize when depth improves function approximation.
D. Shallow and deep networks.
Both shallow and deep networks can approximate arbitrary continuous functions on compact domains, but deep networks offer substantially lower complexity guarantees for hierarchical compositional functions.
- Both shallow and deep networks are universal and can approximate arbitrarily well any continuous function of n variables on a compact domain.
- Deep networks achieve the same approximation accuracy as shallow networks for compositional functions with many fewer parameters.
- The relevant deep architectures mirror compositional graphs and use ridge-function nodes with smoothed ReLU-like activations.The results extend to more complex convolutional architectures, and weight sharing is not necessary for the stated guarantee.
- The smooth-activation theorem does not directly satisfy the nonsmooth ReLU assumption, but the result extends to nonsmooth ReLU networks.Smoothing ReLU in an arbitrarily small interval around the origin satisfies the theorem’s activation assumptions.
- For general smooth functions, shallow-network approximation requires O(ϵ−n/m) trainable parameters, reflecting the curse of dimensionality.The estimate is stated to be best possible under derivative-based prior information.
- For hierarchical compositional functions, deep networks guarantee accuracy ϵ with O(ϵ−2/m) trainable parameters.The constituent-function dimension is fixed independently of the overall input dimension n.
2. The Optimization Landscape of Deep Nets with Smooth Activation Function
The optimization analysis asks how the empirical-loss landscape behaves in deep networks, focusing on global minima and local gradient-critical points while relating the problem to noisy-gradient methods.
- The central optimization question concerns the empirical-loss landscape, including its global minima and local critical points of the gradient.
- Recent work studies whether noisy gradient descent can find global minima and establishes global or local convergence under assumptions for some shallow networks.
B. Degeneracy of global and local minima under the exponential loss.
Under exponential loss, separating critical points are characterized through degeneracy: global minima are completely degenerate, while other critical points are less degenerate and typically have nonzero Hessian eigenvalues.
- For ReLU networks with exponential-type loss, critical points that separate the data are global minima rather than non-global local minima.
- Global minima occur at ρ = ∞, where the exponential loss and Hessian vanish identically.At finite ρ, the loss has a nonzero Hessian in the discussed setting.
- Global minima are completely degenerate, with all W Hessian eigenvalues equal to zero.Here W denotes the number of network parameters.
- Other critical points are less degenerate, with at least one and typically N nonzero Hessian eigenvalues.
- For non-exponential loss and smooth nonlinearities, the stated extension is a conjecture rather than an established result.It posits many degenerate global zero-error minimizers and other critical points confined to a much lower-dimensional degenerate set.
- SGD concentrates in probability on the most degenerate minima, based on its similarity to Langevin dynamics and the Boltzmann asymptotic distribution.The figure caption states that SGD and SGDL prefer degenerate minima over non-degenerate minima of equal depth.
C. SGD and Boltzmann Equation.
The Boltzmann distribution models noisy SGD and suggests that, under suitable overparametrization, SGD favors broad, degenerate global minimizers and reaches them with high probability.
- SGDL follows a Boltzmann distribution determined by the loss and noise power.The distribution includes a normalization constant Z, loss L(f), and temperature-like parameter T.
- Degenerate minima are preferred over non-degenerate minima with the same depth.Among equal-depth basins, larger-volume regions are also more likely in high dimensions.
- High-dimensional SGD is suggested to concentrate on large, isotropic, flat minimizer regions.This follows from the preference for degeneracy and basin volume.
- Under appropriate overparametrization, SGD is conjectured to select highly degenerate global empirical-loss minimizers with high probability.
3. Generalization
The generalization analysis explains deep-network performance through complexity control on weight directions, using normalized surrogate-loss optimization and its connections to standard training methods.
- Uniform convergence motivates minimizing a surrogate loss while constraining each layer’s weight-direction norm.The relevant classification variables are the directions Vk rather than the weight magnitudes.
- Exponential-loss gradient descent with an explicit L2 unit-norm constraint is equivalent to weight normalization and closely related to batch normalization.
- Unconstrained exponential-loss gradient descent has the same critical points as weight normalization and implicitly enforces an L2 constraint on weight directions.
- The same complexity-control results apply to one-homogeneous kernel machines under separability or interpolation.
- The approach aims to explain where the complexity control underlying generalization is hidden during deep-network training.It contrasts implicit control from standard gradient descent with explicit regularization approaches.
B. Deep networks: definitions and properties.
The paper represents a deep ReLU network as a composition of layerwise matrix transformations and exploits ReLU’s positive homogeneity to separate weight magnitudes from normalized directions.
- ReLU’s positive one-homogeneity enables decomposing each layer matrix as Wk=ρkVk with ||Vk||p=1.
- The network can be expressed as f=ρ f̃, where ρ is the product of layerwise magnitudes and f̃ uses normalized weights.The normalized representation depends on the chosen matrix norm.
- For separable training data, every example satisfies f(xn)yn>0.
C. Uniform convergence bounds: minimizing a surrogate loss under norm constraint.
The paper connects uniform-convergence generalization bounds to constrained surrogate-loss minimization, then shows that normalization and unconstrained gradient descent can induce the relevant unit-norm dynamics and margin maximization.
- Uniform convergence bounds: Normalized networks write f(x)=ρ f̃(x), with Rademacher complexity scaling as RN(F)=ρRN(F̃).Fixing or progressively relaxing ρ creates a regularization-type tradeoff.
- Uniform convergence bounds: The proposed generalization approach minimizes an exponential-type loss under unit norm constraints because classification depends on weight directions.The loss family includes exponential, logistic, and cross-entropy losses.
- Uniform convergence bounds: Constrained exponential-loss minimization converges, as ρ→∞, to the maximum margin of the normalized network.The theorem uses a chosen Lp norm for each layer’s normalized weight matrix.
- Unit norm dynamics: For separable data, exponential-loss gradient dynamics drive the loss toward zero while layer weight magnitudes diverge to infinity.The only separating critical points are global minima at infinity.
- Unit norm dynamics: Unit-norm constrained gradient methods include Lagrange-multiplier and tangent-gradient approaches that approximate the true gradient method for small step sizes.
- Weight normalization: The constrained direction dynamics are the same as weight normalization dynamics, while standard unconstrained gradient descent matches them exactly for p=2.
- Weight normalization: Standard gradient descent implicitly enforces a unit L2 constraint on normalized weight directions under exponential loss.Other optimization methods may favor different norm constraints.
F. Linear networks and rates of convergence.
The section analyzes convergence dynamics for linear and normalized networks, highlighting fixed-point behavior, convergence rates, and broader implications for optimization and generalization in deep networks.
- Linear networks: Gradient descent dynamics converge toward a fixed point aligned with the support-vector combination, independently of initialization in the linear case.The associated operator is non-expanding, and the fixed point is unique for linear networks.
- Rates of convergence: ρ(t) grows proportionally to log t, while the exponential term decays proportionally to 1/t and directional error converges proportionally to 1/log t.These rates are derived from the equations governing the scale and direction dynamics.
- Weight normalization: Weight normalization converges faster to the same equilibrium than standard gradient descent because its directional dynamics differ by a factor ρ^2.The section attributes the faster rate to the modified equation for the direction variable.
- Generalization: Classical uniform-convergence analysis motivates controlling weight directions through unit norm constraints when evaluating normalized networks.The normalized-network relation includes a Rademacher-complexity term and a small offset dependent on sample size and architecture.
- Approximation: Deep convolutional networks can avoid the curse of dimensionality for hierarchical local compositional functions, whereas shallow networks generally require exponential dependence on dimensionality.The relevant advantage comes from locality at each hierarchical level rather than weight sharing itself.
- Discussion: The broader framework links overparameterization, stochastic gradient descent, exponential loss, and ReLU homogeneity to global optimization and generalization behavior.The review states that SGD reaches global minima with high probability and that gradient descent implicitly constrains weight directions.