Depth Separation for Neural Networks

By Amit Daniely. 2017

80 citations recorded by the source corpus.

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}$. As many functions of the above form can be well approximated by poly-size depth three networks with poly-bounded weights, this establishes a separation between depth two and depth three networks w.r.t.\ the uniform distribution on $\mathbb{S}^{d-1}\times \mathbb{S}^{d-1}$.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Theoretical Guarantees for Model Auditing with Finite Adversaries (2019, background): “The latter results characterize how well certain functions can be approximated using neural networks, see [16, 17, 20–25] and references therein.”
Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, background): “These choices can be difﬁcult and only preliminary research has been done (see, e.g., Daniely (2017), Telgarsky (2016) and references therein).”
On the Ability of Neural Nets to Express Distributions (2017, background): “[Dan17] shows such a separation but with respect to the uniform distribution on the sphere.”
Limits to Depth Efficiencies of Self-Attention (2020, background): “Beyond overwhelming empirical signals for this notion [Simonyan and Zisserman, 2014, He et al., 2016], depth-efﬁciency was theoretically supported from a variety of angles [Cohen et al., 2016, Eldan and Shamir, 2016, Raghu et al., 2017, Daniely, 2017].”
DEEP NEURAL NETWORKS FOR ESTIMATION AND INFERENCE (2020, background): “These choices can be difficult and only preliminary research has been done (see, e.g., Daniely (2017), Telgarsky (2016) and references therein).”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “Superior expressiveness of deeper networks, long suspected, is now conﬁrmed by theory, albeit for fairly limited learning problems (Eldan & Shamir, 2015; Raghu et al., 2016; Lee et al., 2017; Cohen et al., 2017; Daniely, 2017; Arora et al., 2018).”