A Class of Random-Kernel Network Models
This addresses the efficiency of neural network approximations for machine learning practitioners, though it appears incremental as it builds on random feature models.
The paper tackles the problem of approximating functions with random-kernel networks, showing that deeper models can achieve this with fewer Monte Carlo samples than shallow ones, establishing a depth separation theorem in sample complexity.
We introduce random-kernel networks, a multilayer extension of random feature models where depth is created by deterministic kernel composition and randomness enters only in the outermost layer. We prove that deeper constructions can approximate certain functions with fewer Monte Carlo samples than any shallow counterpart, establishing a depth separation theorem in sample complexity.