Abstract: The task of using the machine learning to approximate the mapping x ↦ $\sum\limits_{i = 1}^d {x_i^2}$ with x_i ∈ [-1, 1] seems to be a trivial one. Given the knowledge of the separable structure of the function, one can design a sparse network to represent the function very accurately, or even exactly. When such structural information is not available, and we may only use a dense neural network, the optimization procedure to fnd the sparse network embedded in the dense network is similar to fnding the needle in a haystack, using a given number of samples of the function. We demonstrate that the cost (measured by sample complexity) of fnding the needle is directly related to the Barron norm of the function. While only a small number of samples are needed to train a sparse network, the dense network trained with the same number of samples exhibits large test loss and a large generalization gap. To control the size of the generalization gap, we fnd that the use of the explicit regularization becomes increasingly more important as d increases. The numerically observed sample complexity with explicit regularization scales as $\mathcal{O}$(d^2.5), which is in fact better than the theoretically predicted sample complexity that scales as $\mathcal{O}$(d⁴). Without the explicit regularization (also called the implicit regularization), the numerically observed sample complexity is signifcantly higher and is close to $\mathcal{O}$(d^4.5).

Key words: Machine learning, Sample complexity, Generalization error