Minimax lower bounds for ridge combinations including neural nets
Estimation of functions of d variables is considered using ridge combinations of the form Σ<sup>m</sup><inf>k=1</inf> c<inf>1, k</inf>φ(Σ<sup>d</sup><inf>j=1</inf>c<inf>0, j, k</inf>x<inf>j</inf>-b<inf>k</inf>) 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]<sup>d</sup>, the minimax mean square error is examined for functions in the closure of the ℓ<inf>1</inf> 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<inf>0</inf> and v<inf>1</inf> on the ℓ<inf>1</inf> norms of inner parameter co and outer parameter c<inf>1</inf>, 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.