Approximation rates for neural networks, whether deterministic or random, refer to how effectively these networks can approximate functions or solve problems as their complexity (e.g., number of neurons, layers, or training data) increases. The study of these rates is essential for understanding the theoretical capabilities of neural networks and how well they perform in practical applications, including scenarios involving stochastic elements or random networks. Here's an overview of the approximation rates for deterministic and random neural networks:

1. Deterministic Neural Networks

Deterministic neural networks refer to standard architectures where the weights and biases are learned through training with deterministic algorithms.

Approximation Power

• Universal Approximation Theorem: A feedforward neural network with at least one hidden layer using non-linear activation functions (e.g., ReLU, sigmoid) can approximate any continuous function on a compact set to any desired degree of accuracy, given sufficient neurons.

• Rates of Approximation:

  • Single-Layer Networks: For functions in Sobolev spaces, the approximation rate of a single-layer neural network (shallow network) is polynomial in the number of neurons. For a ReLU-activated network with $N$ hidden units, the approximation rate $\epsilon$ scales as:

  $\epsilon = O(N^{-1/d}),$

  where \( d \) is the dimension of the input space.

  • Deep Networks: The rate of approximation improves significantly with depth. Deep neural networks can achieve better approximation rates than shallow ones for the same number of neurons. For specific function classes, such as compositional functions (functions with hierarchical structures), deep networks can reach approximation rates that are exponentially faster than shallow networks.

  $\epsilon = O(e^{-cN^{1/d}}),$

  where $c$ is a positive constant and $N$ is the total number of units across layers.

Key Theoretical Results:

• Barron’s Theorem: For functions with certain smoothness properties (e.g., functions with a bounded Fourier transform), deep networks can achieve approximation rates of:

$\epsilon = O(N^{-1/2}),$

for high-dimensional input spaces, which significantly outperforms traditional polynomial rates of shallow networks.

2. Random Neural Networks

Random neural networks have weights and biases that are not necessarily trained in the typical sense but can be initialized randomly and left unchanged (as in reservoir computing) or adapted through specialized training.

Types and Applications:

• Random Feature Models: These models involve using random weights in the hidden layers, where only the output layer is trained. This approach is related to the idea of randomized approximation algorithms.
• Reservoir Computing: In this approach, a large, fixed reservoir with random weights processes inputs, and only the readout layer is trained. It is often used in temporal sequence learning tasks and dynamic systems modeling.

Approximation Rates:

• Theoretical Bounds: Random neural networks can still approximate certain classes of functions effectively:
  • Gaussian Random Feature Networks: When weights are drawn from a Gaussian distribution, and the network uses suitable activation functions, the expected approximation error can be bounded probabilistically. The rate depends on the properties of the function space and the network's architecture.
  • Concentration Inequalities: These are often used to show that, with high probability, a network with random weights achieves an approximation error close to that of a fully trained network, particularly when the number of neurons $N$ is large enough.
• Monte Carlo Approximation: Random neural networks can be related to Monte Carlo methods, where the approximation rate scales with $O(1/\sqrt{N})$ due to the law of large numbers.

Advantages and Limitations:

• Advantages:
  • Reduced Training Complexity: Since the random features are fixed, training only requires learning a linear model on top, which is computationally less intensive.
  • Stochastic Regularization: Randomness can act as a regularizer, helping to prevent overfitting and improving generalization.
• Limitations:
  • Suboptimal Approximation: Random networks might need more neurons compared to fully trained networks to reach the same level of accuracy.
  • Dependence on Activation and Distribution: The rate and effectiveness of approximation can depend heavily on the activation function used and the distribution of the random weights.

3. Comparison Between Deterministic and Random Neural Networks