Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks

Let fstar be a function on ℝd with an assumption of a spectral norm v_fstar . For various noise settings, we show that mathbbE|hatf - fstar |2 ≤ left(v4_fstarfraclog dnright)1/3 , where n is the sample size and hatf is either a penalized least squares estimator or a greedily obtained version of such using linear combinations of sinusoidal, sigmoidal, ramp, ramp-squared or other smooth ridge functions. The candidate fits may be chosen from a continuum of functions, thus avoiding the rigidity of discretizations of the parameter space. On the other hand, if the candidate fits are chosen from a discretization, we show that mathbbE|hatf - fstar |2 ≤ left(v3_fstarfraclog dnright)2/5 . This work bridges non-linear and non-parametric function estimation and includes single-hidden layer nets. Unlike past theory for such settings, our bound shows that the risk is small even when the input dimension d of an infinite-dimensional parameterized dictionary is much larger than the available sample size. When the dimension is larger than the cube root of the sample size, this quantity is seen to improve the more familiar risk bound of v_fstarleft(fracdlog (n/d)nright)1/2 , also investigated here.