Fetching the paper…

Reading the bibliography…

2017

Depth Separation for Neural Networks

Daniely, Amit

Original
PDF
Post on X

Understand

Let $f:\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}\to\mathbb{S}$ be a function of the form $f(\mathbf{x},\mathbf{x}') = g(\langle\mathbf{x},\mathbf{x}'\rangle)$ for $g:[-1,1]\to \mathbb{R}$.

We give a simple proof that shows that poly-size depth two neural networks with (exponentially) bounded weights cannot approximate $f$ whenever $g$ cannot be approximated by a low degree polynomial.
Moreover, for many $g$'s, such as $g(x)=\sin(\pi d^3x)$, the number of neurons must be $2^{\Omega\left(d\log(d)\right)}$.
Furthermore, the result holds w.r.t.\ the uniform distribution on $\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}$.

Depth Separation for Neural Networks · Around

Built on

Approximation by superpositions of a sigmoidal function
G. 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.
Approximation and estimation bounds for artificial neural networks
Andrew R Barron · 1994
Earlier work this paper cites.

Similar

Shallow vs. deep sum-product networks
Olivier Delalleau and Yoshua Bengio · 2011
Cited alongside, same era.
Spherical Harmonics and Approximations on the Unit Sphere: An Introduction , volume 2044
K. Atkinson and W. Han · 2012
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.
On the expressive power of deep learning: A tensor analysis
Nadav Cohen, Or Sharir, and Amnon Shashua · 2016
Cited alongside, same era.

Then

The power of depth for feedforward neural networks
Ronen Eldan and Ohad Shamir · 2016
Later among the works it cites.
Depth separation in relu networks for approximating smooth non-linear functions
Original
Itay Safran and Ohad Shamir · 2016
Later among the works it cites.
Representation benefits of deep feedforward networks
Original
Matus Telgarsky · 2016
Later among the works it cites.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…