A Note on the Representation Power of GHHs
This work addresses a theoretical gap in understanding the representation limits of GHHs and neural networks, which is incremental but clarifies foundational bounds in machine learning.
The paper proves that at least n nestings of nested absolute-value functions in generalized hinging hyperplanes (GHH) are necessary for universal representation of arbitrary continuous piecewise linear (CPWL) functions, providing an almost tight lower bound, and also shows that one-hidden-layer neural networks lack universal approximation power over the entire domain.
In this note we prove a sharp lower bound on the necessary number of nestings of nested absolute-value functions of generalized hinging hyperplanes (GHH) to represent arbitrary CPWL functions. Previous upper bound states that $n+1$ nestings is sufficient for GHH to achieve universal representation power, but the corresponding lower bound was unknown. We prove that $n$ nestings is necessary for universal representation power, which provides an almost tight lower bound. We also show that one-hidden-layer neural networks don't have universal approximation power over the whole domain. The analysis is based on a key lemma showing that any finite sum of periodic functions is either non-integrable or the zero function, which might be of independent interest.