On Explicit Super-Expressive Approximation for Neural Networks

Research Question and Approach

This paper addresses the challenge of "super-expressive" neural network approximation, where a network with a fixed architecture (constant width and depth) can approximate a target function to arbitrary accuracy by adjusting its weights. While previous research established the existence of such networks, these studies often lacked quantitative, non-asymptotic bounds on how large the parameters must grow as the target error decreases. The authors resolve this by employing the Chinese Remainder Theorem (CRT) as a constructive encoding mechanism to map input domain partitions to quantized function values.

For Lipschitz continuous functions, the authors construct a network with a fixed width of max{D, 4} and a depth of 5. They provide an explicit relationship between the target accuracy (epsilon) and the required parameter magnitude (P), showing that log(P) scales as O(epsilon^(-2D) * log(1/epsilon)).

For more complex Holder-smooth functions, the authors extend this to a network of width max{2D, D + 5N + 1} and depth r + 9. A key finding is that increased smoothness of the target function improves the scaling law, reducing the complexity exponent from 2D to 2D/(r + gamma). This provides a dual perspective to traditional approximation theory, where network architecture typically grows to accommodate higher accuracy while parameters remain bounded.

This work bridges a significant theoretical gap by providing explicit, non-asymptotic parameter bounds for fixed-architecture networks. By moving beyond existence proofs to concrete, constructive formulas, the paper offers a rigorous foundation for understanding the trade-offs between network size, parameter precision, and approximation error. This is particularly relevant for theoretical deep learning, as it completes the picture of how super-expressive networks can theoretically represent complex functions without requiring architectural scaling.