PaperlayerView exact revision on arXiv

Source-linked AI summary

Model Complexity of Deep Learning: A Survey

Xia Hu, Lingyang Chu, Jian Pei, Weiqing Liu, Jiang Bian

arXiv:2103.05127v2cs.LGcs.AI

TL;DR

Deep learning’s complexity raises unresolved questions about expressive power, generalization, and optimization, while classical measures do not directly apply to its structurally different, over-parameterized models. The paper systematically surveys recent studies by separating expressive capacity from effective complexity and examining four influencing factors. It concludes that effective complexity remains under-developed and difficult to measure finely across models with different training processes.

  • Problem

    Deep learning lacks a dedicated survey of how to define and measure complexity despite fundamental questions about expressive power, generalization, and optimization.

  • Method

    The paper systematically surveys expressive capacity and effective model complexity across model framework, model size, optimization process, and data complexity.

  • Results

    The survey organizes expressive-capacity studies around depth efficiency, width efficiency, expressible functional space, and VC dimension or Rademacher complexity, and effective-complexity studies around general measures and high-capacity low-reality phenomena.

  • Takeaways & Limitations

    Effective complexity can inform optimization, regularization, generalization, compression, and model selection by reflecting the information volume represented by trained models.

  • Takeaways & Limitations

    The effects of data complexity and optimization process on expressive capacity remain rarely explored, and effective complexity measures are still largely under-developed.

Abstract

from arXiv · show

Model complexity is a fundamental problem in deep learning. In this paper we conduct a systematic overview of the latest studies on model complexity in deep learning. Model complexity of deep learning can be categorized into expressive capacity and effective model complexity. We review the existing studies on those two categories along four important factors, including model framework, model size, optimization process and data complexity. We also discuss the applications of deep learning model complexity including understanding model generalization, model optimization, and model selection and design. We conclude by proposing several interesting future directions.

1 Introduction

Deep learning model complexity is central to understanding expressive power, generalization, and optimization, but classical complexity analyses do not transfer directly to deep models. This survey addresses the lack of a dedicated overview by organizing recent work on the topic.

  • Deep learning raises fundamental questions about expressive power, generalization capability, and optimization despite its strong application performance.
  • Traditional model-specific measures include tree depth and leaf count for decision trees, and VC dimension, Rademacher complexity, and Fisher information for logistic regression.
  • Deep learning complexity research has grown recently, but no existing survey had synthesized this emerging subject before this paper.
  • Classical complexity measures cannot be directly applied to deep learning because deep models differ structurally and are often over-parameterized.
  • Parameter count alone has limited usefulness for measuring complexity in over-parameterized deep learning models.

2 Deep Learning Model Complexity

The survey distinguishes expressive capacity from effective model complexity and organizes both around structural and training-related factors. It emphasizes that architecture and size shape hypothesis spaces, while data and optimization further constrain them.

  • The survey divides deep learning model complexity into expressive capacity and effective model complexity, then groups studies by important influencing factors.
  • Expressive capacity concerns the upper complexity that a model family can express, whereas effective complexity concerns a specific parameterized model within that family.
  • Model framework and model size mainly affect a model’s static structure, while optimization process and data complexity mainly affect its dynamic parametric part.
  • Under a fixed framework, increasing depth expands the hypothesis space, so a deeper model’s expressive capacity does not exceed that of the corresponding shallower model.
  • Data distribution and optimization algorithms can further reduce the hypothesis space, but their effects on expressive capacity remain rarely explored.
  • Effective complexity supports analysis of optimization, regularization, generalization, compression, and model selection by reflecting information volume in trained models.

3 Expressive Capacity of Deep Learning Models

The survey reviews expressive capacity through depth efficiency, width efficiency, expressible functional spaces, and classic statistical complexity measures. These perspectives examine how architecture and parameterization determine the functions deep models can represent.

  • Expressive capacity describes how well a deep learning model can approximate complex problems and the upper complexity of a parametric model family.
  • Depth efficiency: Depth efficiency analyzes how architectural depth contributes to model performance such as accuracy.
  • Width efficiency: Width efficiency analyzes how layer widths affect the expressive capacity of deep learning models.
  • Expressible functional space: Expressible functional space studies the functions obtainable from a specified framework and size by varying model parameters.
  • VC Dimension and Rademacher Complexity: VC dimension and Rademacher complexity provide classic measures of expressive capacity in machine learning.

3.1 Depth Efficiency

Studies of depth efficiency compare deep and shallow networks by reducing them to analyzable functions or measuring their representation capacity. Across these analyses, depth can represent certain functions with substantially fewer neurons or parameters, while composition and region reuse explain this advantage.

  • Model Reduction: Model-reduction studies compare deep and shallow networks by analyzing the resources required to represent the same function families.The reviewed approaches reduce neural networks to functions and compare representation efficiency across depths.
  • Model Reduction: For sum-product networks, shallow representations require exponentially growing neuron counts, whereas deep representations require only linear growth for the same functions.The cited families include functions represented by deep SPNs with structured input sizes and depths.
  • Model Reduction: A hierarchical deep network approximates designed compositional functions to the same degree as a shallow network with fewer parameters: O(ϵ^-2/r) versus O(ϵ^-d/r).The comparison concerns shallow Gaussian networks and hierarchical binary tree networks.
  • Model Reduction: Hadamard-induced functions cannot be sparsely represented by one-hidden-layer Signum networks with both limited neurons and limited output-weight L1-norm.The obstruction is tied to functions nearly orthogonal to the class of Signum perceptrons.
  • Model Reduction: A function induced by S(k) requires k neurons per layer with two hidden Heaviside layers, but at least 2^k hidden neurons in one layer.This gives a direct depth-versus-width comparison for Heaviside networks.
  • Expressive Capacity Measures: Expressive-capacity measures show depth increasing representational complexity through exponential growth in linear regions, Betti-number bounds, and reusable layer-wise computations.For piecewise-linear networks, the maximum number of linear regions increases exponentially with depth; for deep networks, B(S) is bounded by O(2^M).

3.2 Width Efficiency

Width efficiency studies how layer width affects the expressive capacity of deep models. ReLU networks can approximate broad function classes with width bounded by input dimension plus four, while shallow-wide and narrow-deep networks exhibit asymmetric approximation limits.

  • 3.2 Width Efficiency: Width efficiency analyzes how layer width affects the expressive capacity of deep learning models.It complements depth-efficiency studies and helps validate their insights.
  • 3.2 Width Efficiency: ReLU networks can approximate any Lebesgue-integrable function to arbitrary L1 accuracy while each hidden layer has width at most d + 4.Here d is the input dimension.
  • 3.2 Width Efficiency: A shallow ReLU network of depth 3 and width 2k^2 cannot be approximated to arbitrary accuracy by a bounded-parameter narrow network with depth at most k + 2 and width at most k^3/2.The result establishes a quantitative separation between the two architectures.
  • 3.2 Width Efficiency: There exists a family of shallow ReLU networks that narrow networks cannot approximate when their depth is constrained by polynomial bounds.
  • 3.2 Width Efficiency: Depth-efficiency lower bounds are exponential, whereas width-efficiency lower bounds are polynomial; however, depth is not proven strictly more effective because a polynomial width upper bound remains unknown.

3.3 Expressible Functional Space

Studies of expressible functional space characterize which functions deep networks can represent under specific architectures, activations, and sizes. Results span ReLU approximation, polynomial-network varieties and bottlenecks, and tensor-decomposition correspondences across architectures.

  • 3.3 Expressible Functional Space: Expressible-functional-space studies characterize functions represented by deep models with specified frameworks and sizes, using model-specific or cross-model approaches.
  • 3.3 Expressible Functional Space: Every piecewise linear function on R^d can be represented by a ReLU network with at most ⌈log2(d + 1)⌉ hidden layers.Piecewise linear functions are dense in compactly supported continuous functions, which are dense in Lp(R^d).
  • 3.3 Expressible Functional Space: Every function in Lp(R^d) can be approximated to arbitrary Lp norm by a ReLU network with at most ⌈log2(d + 1)⌉ hidden layers.
  • 3.3 Expressible Functional Space: For Sobolev-space approximation, studies establish upper and lower bounds on the model sizes required to approximate functions.
  • 3.3 Expressible Functional Space: For polynomial networks, effective complexity is defined as the dimension of the associated functional variety, whose dimension can be studied through tensor decompositions.Two-layer polynomial networks connect to CP decompositions, while deeper networks connect to iterated tensor decompositions.
  • 3.3 Expressible Functional Space: A too-narrow layer can bottleneck a deep polynomial network so it cannot fill the ambient polynomial space; architectures that fill it may aid optimization and training.
  • 3.3 Expressible Functional Space: Tensor-decomposition rank measures network complexity because decomposition rank corresponds to network width, enabling comparisons among RNNs, CNNs, and shallow FCNNs.The corresponding TT, CP, and HT decompositions map to recurrent, shallow fully connected, and convolutional structures.

3.4 VC Dimension and Rademacher Complexity

VC dimension and Rademacher complexity quantify expressive capacity for deep networks, with bounds depending on parameters, depth, norms, width, and input dimension. Their practical guidance can be weak for over-parameterized models because these measures may be too high.

  • 3.4 VC Dimension and Rademacher Complexity: VC dimension and Rademacher complexity are widely used measures for analyzing the expressive capacity of deep learning models.
  • 3.4 VC Dimension and Rademacher Complexity: For linear-threshold feedforward networks with L ≥ 3, the VC dimension is Θ(W log W), where W is the number of parameters.
  • 3.4 VC Dimension and Rademacher Complexity: For piecewise-polynomial networks, the VC dimension has upper bound O(WL^2 + WL log WL) and lower bound Ω(WL), later improved to Ω(WL log(W/L)).
  • 3.4 VC Dimension and Rademacher Complexity: For piecewise-linear networks such as ReLU networks, VC dimension is bounded below by Ω(WL log(W/L)) and above by O(WL log W).
  • 3.4 VC Dimension and Rademacher Complexity: A two-layer ReLU-network Rademacher lower bound improves an earlier bound by a factor of √m, where m is hidden-layer width.
  • 3.4 VC Dimension and Rademacher Complexity: For adversarially trained networks, a Rademacher-complexity lower bound depends explicitly on input dimension d.
  • 3.4 VC Dimension and Rademacher Complexity: In practice, VC dimension and Rademacher complexity can provide weak guidance because deep models often have more parameters than training samples.

4 Effective Complexity of Deep Learning Models

Effective complexity measures the functions actually represented by parameterized deep models, not merely their architecture, and is studied through linear-region geometry, robustness, training dynamics, and the gap between capacity and realized complexity.

  • Concept and motivation: Effective complexity reflects functions represented by specific parameterizations and can differ between models sharing the same architecture.A useful measure must detect parameter-value differences that structure alone cannot capture.
  • General measures: Linear regions and their density provide a basis for measuring effective complexity in piecewise-linear networks such as ReLU and Maxout.Raghu et al. also measure the number of regions crossed by an input trajectory and its transformed length.
  • General measures: Effective complexity grows exponentially with depth and polynomially with width, while initialization affects complexity and Batch Normalization reduces trajectory length.Layer perturbations can produce exponentially larger perturbations downstream.
  • General measures: Complexity measures correlate with generalization-related robustness: data augmentation and ReLU correspond to stronger robustness, whereas full-batch training and random labels correspond to weaker robustness.These findings connect effective complexity measures with behavior near the training-data manifold.
  • Training dynamics: Training iterations increase effective complexity, overfitting correlates positively with that increase, and L1 or L2 regularization suppresses it.Complexity therefore tracks changes associated with training and regularization.
  • Training dynamics: Increasing effective complexity improves test performance when it is sufficiently below or above training-set size, but hurts performance when it is approximately equal to that size.This conclusion is stated for the effective-complexity measure based on data distribution, training error, and training procedure.
  • High-capacity low-reality phenomenon: The high-capacity low-reality phenomenon describes a gap in which deep models’ practical complexity may be far below their theoretical expressive capacity.Shallow mimics can match deep-model accuracy when trained from deep-model outputs, and average region counts can grow linearly rather than exponentially with neuron count.
  • Applications and open problems: Effective complexity supports analysis of optimization, regularization, generalization, and model compression, while cross-model comparison remains an open problem.The survey identifies comparison across different architectures as a promising direction.

5 Application Examples of Deep Learning Model Complexity

Model complexity is applied to explain generalization, monitor and evaluate optimization, and select or design architectures by balancing predictive accuracy against complexity.

  • Generalization: Over-parameterized deep networks can generalize well despite having more parameters than optimal solutions and training samples.This observation motivates studying why larger and more complex networks can generalize better.
  • Generalization: Generalization analyses use expressive-capacity measures such as Rademacher complexity and basis-path norms, while invariance is proposed as a desirable property for complexity measures.Invariance accounts for different parameterizations that produce the same prediction.
  • Generalization: Norms, robustness, and sharpness satisfy some proposed complexity-measure requirements, but not all.The requirements include lower complexity for real-label training than random-label training and for models with better generalization.
  • Generalization: Sensitivity-based complexity measures empirically correlate with generalization: poor-generalization operations have high sensitivity, while good-generalization operations have low sensitivity.Full-batch training is associated with high sensitivity; data augmentation is associated with low sensitivity.
  • Model optimization: Effective complexity makes optimization traceable by monitoring model changes, training progress, and the effects of optimization improvements and regularization.Regularization effectiveness can be demonstrated through its impact on complexity.
  • Model optimization: During training, average linear-region boundary volume is proportional to neuron count and independent of depth, suggesting deep models do not always learn more complex functions than shallow ones.Hanin and Rolnick use boundary volume as a ReLU complexity measure.
  • Model selection and design: Model selection and design balances prediction accuracy with complexity, seeking models complex enough to fit data without being unnecessarily over-complicated.Effective complexity measures are presented as a premise for sound model-selection strategies.
  • Model selection and design: Neural architecture search considers the accuracy-complexity tradeoff because overly complex models can take too long to train, while design spaces can be compared through complexity distributions.The survey discusses Progressive NAS, ENAS, DARTS, and network design-space comparisons.

6 Conclusions and Future Directions

The survey organizes deep-learning model complexity into expressive capacity and effective complexity, reviews their determinants and applications, and identifies substantial unresolved challenges.

  • Conclusion: The survey reviews expressive capacity and effective complexity across model framework, model size, optimization process, and data complexity.It also covers generalization, optimization, and model selection and design applications.
  • Conclusion: Deep learning model complexity remains in its infant stage, leaving many challenges for future work.The conclusion frames the field as promising but incomplete.
  • Expressive capacity: A central expressive-capacity question is how much capacity a task requires and whether a narrow layer limits capacity despite many total parameters.The survey highlights sufficient-capacity bounds and layer-width bottlenecks.
  • Expressive capacity: Width bottlenecks can restrict expressive power in ReLU and polynomial networks, and may affect model design, selection, compression, and pruning.The cited studies identify restrictions tied to input dimensionality, early-layer widths, and very narrow polynomial-network layers.
  • Effective complexity: Effective-complexity measurement remains under-developed because measures must capture fine-grained differences between parameterizations, optimization procedures, and related settings.Existing approaches include piecewise-linear properties, the Fisher-Rao metric, and trainable-sample size.
  • Cross-model comparison: Cross-model comparison remains limited for expressive capacity and effective complexity across architectures and model sizes.Existing comparisons cover shallow FCNNs, CNNs, and RNNs, while more sophisticated models remain unexplored.
Loading 2103.05127v2…