Minimax lower bounds for ridge combinations including neural nets
Jason M. Klusowski, Andrew R. Barron · 2017
Estimation of functions of d variables is considered using ridge combinations of the form Σm k=1 c 1, k φ(Σd j=1 c 0, j, k x j -b k ) where the activation function φ is a function with bounded value and derivative. These include single-hidden layer neural networks, polynomials, and sinusoidal models. From a sample of size n of possibly noisy values at random sites X ∊ B = [−1, 1]d, the minimax mean square error is examined for functions in the closure of the l 1 hull of ridge functions with activation ϕ. It is shown to be of order d/n to a fractional power (when d is of smaller order than n), and to be of order (log d)/n to a fractional power (when d is of larger order than n). Dependence on constraints v 0 and v 1 on the l 1 norms of inner parameter co and outer parameter c 1 , respectively, is also examined. Also, lower and upper bounds on the fractional power are given. The heart of the analysis is development of information-theoretic packing numbers for these classes of functions.