2020/02/24 by Jiefu Zhang, Zhang, Jiefu, Leonardo Zepeda-Núñez +5
Computer Science · Physics and Astronomy · #Computational Physics and Python Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Neural Networks and Applications #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.2002.10561
openalex publication_date 2020/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The task of using machine learning to approximate the mapping x↦∑i=1d xi2 with xi∈[-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 find the sparse network embedded in the dense network is similar to finding the needle in a haystack, using a given number of samples of the function. We demonstrate that the cost (measured by sample complexity) of finding the needle is directly related to the Barron norm of the function. While only a small number of samples is 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. In order to control the size of the generalization gap, we find that the use of explicit regularization becomes increasingly more important as d increases. The numerically observed sample complexity with explicit regularization scales as O(d2.5), which is in fact better than the theoretically predicted sample complexity that scales as O(d4). Without explicit regularization (also called implicit regularization), the numerically observed sample complexity is significantly higher and is close to O(d4.5).