Related Experiment Video
Updated: Mar 2, 2026
08:12
A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments
Published on: March 1, 2022
3.0K
Probabilistic lower bounds for approximation by shallow perceptron networks
Věra Kůrková1, Marcello Sanguineti2
1Institute of Computer Science, Czech Academy of Sciences, Pod Vodárenskou věží, 2 - 18207 Prague, Czech Republic.
Summary
Shallow perceptron networks struggle to approximate many functions. Achieving good approximation requires a large number of network units, exceeding polynomial bounds relative to the domain size.
Area of Science:
- Computer Science
- Machine Learning
- Artificial Intelligence
Background:
- Shallow perceptron networks are fundamental neural network architectures.
- Understanding their approximation capabilities is crucial for designing efficient AI models.
- Previous research has explored limitations, but precise bounds for general functions remain an active area.
Purpose of the Study:
- To investigate the approximation limitations of shallow perceptron networks.
- To derive lower bounds on approximation errors for binary-valued functions.
- To determine the necessary network size for effective function approximation.
Main Methods:
- Derivation of lower bounds on approximation errors.
- Application of probabilistic Chernoff-Hoeffding bounds.
- Estimation of function set sizes computable by shallow networks.
Main Results:
- A significant lower bound on approximation error is established for shallow networks.
- It is proven that a large number of network units is required for good approximation.
- This requirement scales beyond polynomial in the logarithm of the domain size for random functions.
Conclusions:
- Shallow perceptron networks have inherent limitations in approximating arbitrary functions.
- Effective approximation necessitates a substantial increase in network complexity.
- The findings provide theoretical insights into the capacity of shallow neural networks.
Related Concept Videos
01:29Application of Linearization and Approximation
121
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
121
01:26Linearization and Approximation
110
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
110
01:28Accuracy, limits, and approximation
1.3K
Accuracy, limits, and approximations are common in many fields, especially in engineering calculations. These concepts are imperative for ensuring that a given value is as close as possible to its true value.
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
1.3K
01:21Linear Approximation in Time Domain
386
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
386
01:26Linear Approximation in Frequency Domain
409
Linear systems are characterized by two main properties: superposition and homogeneity. Superposition allows the response to multiple inputs to be the sum of the responses to each individual input. Homogeneity ensures that scaling an input by a scalar results in the response being scaled by the same scalar.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
409
00:59Propagation of Uncertainty from Random Error
2.0K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
2.0K