Learning Sparse Compositional Functions with Norm-Constrained Neural Networks

This paper replaces parameter counting with a Frobenius product-norm complexity measure for overparameterized ReLU networks and proves that norm-constrained deep models can learn sparse compositional functions without incurring the curse of dimensionality. The main approximation result shows that any Hölder function h ∈ C^α([0,1]^d) can be approximated by a deep ReLU network with depth 2⌈log2(d+r)⌉+2 and L∞ error scaling as K^{-2α/(2+d(D+1))}, where K is the Frobenius norm budget, so capacity is controlled by norm rather than width. For sparse compositional functions encoded by DAGs, the paper derives the first norm-based approximation rates, with error governed by the most restrictive node along a critical path and by local input dimensions din(v), not the ambient dimension d. Concrete cases include multi-index models f(x)=g(Ax), binary trees, and constant-depth compositional architectures; in the multi-index case, the rate depends on intrinsic dimension s and becomes independent of d, while binary trees reduce dimension dependence to log2 d. The statistical result converts these approximation bounds into excess-risk guarantees for empirical risk minimization with clipped outputs: with K balanced as K ≍ n^{1/(2(γ+1))}, the excess risk decays polynomially in n at a rate determined by local smoothness and intrinsic dimension. The analysis uses explicit network constructions for square, multiplication, and d-fold monomials, plus a norm-preserving rescaling lemma, showing that shallow-but-wide subnetworks can operate in the fully overparameterized regime while still generalizing.