2021

On the Approximation Power of Two-Layer Networks of Random ReLUs

Hsu, Daniel, Sanford, Clayton, Servedio, Rocco A. et al.

Understand

This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching upper- and lower-bounds for $L_2$-approximation in terms of the Lipschitz constant, the desired accuracy, and the dimension of the problem, as well as similar results in terms of Sobolev norms.

Our positive results employ tools from harmonic analysis and ridgelet representation theory, while our lower-bounds are based on (robust versions of) dimensionality arguments.

Built on

A general moment problem
Ralph P. Boas, Jr · 1941
Earlier work this paper cites.
Almost orthogonal series
Richard Bellman · 1944
Earlier work this paper cites.
Fourier Series and Integrals
Harry Dym and Henry P. McKean · 1972
Earlier work this paper cites.
Exponential inequalities for sums of random vectors
Vadim Vladimirovich Yurinskiĭ · 1976
Earlier work this paper cites.
Real and Complex Analysis
Walter Rudin · 1987
Earlier work this paper cites.
Approximation by superpositions of a sigmoidal function
George Cybenko · 1989
Earlier work this paper cites.
On the approximate realization of continuous mappings by neural networks
Ken-Ichi Funahashi · 1989
Earlier work this paper cites.
Multilayer feedforward networks are universal approximators
Kurt Hornik, Maxwell Stinchcombe, and Halbert White · 1989
Earlier work this paper cites.
Orthogonal Polynomials , volume XXIII of Americam Mathematical Society Colloquium Publications
Gabor Szegö · 1989
Earlier work this paper cites.
Universal approximation bounds for superpositions of a sigmoidal function
Andrew R. Barron · 1993
Earlier work this paper cites.
An integral representation of functions using three-layered networks and their approximation bounds
Noboru Murata · 1996
Earlier work this paper cites.
Priors for infinite networks
Radford M. Neal · 1996
Earlier work this paper cites.
On best approximation by ridge functions
V.E Maiorov · 1998
Earlier work this paper cites.

Similar

The Calderón reproducing formula, windowed X-ray transforms, and radon transforms in L p L^{p} -spaces
Boris Rubin · 1998
Cited alongside, same era.
Harmonic analysis of neural networks
Emmanuel J. Candès · 1999
Cited alongside, same era.
Real Analysis: Modern Techniques and Their Applications
Gerald B. Folland · 1999
Cited alongside, same era.
Approximation theory of the MLP model in neural networks
Allan Pinkus · 1999
Cited alongside, same era.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2008
Cited alongside, same era.
Kernel methods for deep learning
Youngmin Cho and Lawrence K. Saul · 2009
Cited alongside, same era.
Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning
Ali Rahimi and Benjamin Recht · 2009
Cited alongside, same era.
On the representational efficiency of restricted Boltzmann machines
James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel · 2013
Cited alongside, same era.
Learning polynomials with neural networks
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang · 2014
Cited alongside, same era.
Analysis of Boolean functions
Ryan O’Donnell · 2014
Cited alongside, same era.
The power of depth for feedforward neural networks
Ronen Eldan and Ohad Shamir · 2016
Cited alongside, same era.
Benefits of depth in neural networks
Matus Telgarsky · 2016
Cited alongside, same era.

Then

Depth separation for neural networks
Amit Daniely · 2017
Later among the works it cites.
A first course in Sobolev spaces
Giovanni Leoni · 2017
Later among the works it cites.
Depth-width tradeoffs in approximating natural functions with neural networks
Itay Safran and Ohad Shamir · 2017
Later among the works it cites.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Later among the works it cites.
Approximation by combinations of ReLU and squared ReLU ridge functions with ℓ 1 \ell^{1} and ℓ 0 \ell^{0} controls
Jason M. Klusowski and Andrew R. Barron · 2018
Later among the works it cites.
On the approximation properties of random ReLU features
Original
Yitong Sun, Anna Gilbert, and Ambuj Tewari · 2018
Later among the works it cites.
Neural tangent kernels, transportation mappings, and universal approximation
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian · 2019
Later among the works it cites.
Depth separations in neural networks: What is actually being separated?
Itay Safran, Ronen Eldan, and Ohad Shamir · 2019
Later among the works it cites.
On the power and limitations of random features for understanding neural networks
Gilad Yehudai and Ohad Shamir · 2019
Later among the works it cites.
Approximate is good enough: Probabilistic variants of dimensional and margin complexity
Pritish Kamath, Omar Montasser, and Nathan Srebro · 2020
Later among the works it cites.
On the approximation lower bound for neural nets with random weights
Original
Sho Sonoda, Ming Li, Feilong Cao, Changqin Huang, and Yu Guang Wang · 2020
Later among the works it cites.
The connection between approximation, depth separation and learnability in neural networks, 2021
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…