Some recent work has shown separation between the expressive power of depth-2 and depth-3 neural networks. These separation results are shown by constructing functions and input distributions, so that the function is well-approximable by a depth-3 neural network of polynomial size but it cannot be well-approximated under the chosen input distribution by any depth-2 neural network of polynomial size. These results are not robust and require carefully chosen functions as well as input distributions. We show a similar separation between the expressive power of depth-2 and depth-3 sigmoidal neural networks over a large class of input distributions, as long as the weights are polynomially bounded. While doing so, we also show that depth-2 sigmoidal neural networks with small width and small weights can be wellapproximated by low-degree multivariate polynomials.
This paper proves a new separation results from 3-layer neural networks to 2-layer neural networks. The core of the analysis is a proof that any 2-layer neural networks can be well approximated by a polynomial function with reasonably low degrees. Then the authors constructs a highly non-smooth function can be represented by a 3-layer network, but impossible to approximate by any polynomial-degree polynomial function.
Similar results about polynomial approximation can be found in [1] (Theorem 4). To me, the result proved in [1] is spiritually very similar to propositions 3-4. The authors need to justify the difference.
The main strength of the new separation result is that it holds for a larger class of input distributions. Comparing to Daniely (2017) which requires the input distribution to be spherically uniform, the new result only needs the distribution to be lower bounded by 1/poly(d) in a small ball of radius 1/poly(d). Conceptually I don't think this is a much weaker condition. For a "truly" non-uniform distribution, one should allow its density function to be very close to zero at certain regions of the ball. Nevertheless, the result is a step forward from Daniely (2017) and the paper is well written.
I am still in doubt of the practical value of such kind of separation results. The paper proves the separation by constructing a very specific function that cannot be approximated by 2-layer networks. This function has a super large Lipschitz constant, which we don't expect to see in practice. Consider the function f(x)=cos(Nx). When N is chosen large enough, the function f can not be well approximated by any 2-layer network with polynomial size. Does it imply that the family of cosine functions is rich enough so that it is a better family to learn than 2-layer neural networks? I guess the answer would be negative. In addition, the paper doesn't show that any 2-layer network can be well approximated by a 3-layer network, which is a missing piece in justifying the richness of 3-layer nets.
Finally, the constructed "hard" function has order d^5 Lipschitz constant, but Theorem 7 assumes that the 2-layer networks' weight must be bounded by O(d^2). This assumption is crucial to the proof but not well justified (especially considering the d^5 factor in the function definition).
[1] On the Computational Efficiency of Training Neural Networks, Livni et al., NIPS'14