Learning the mapping x _i=1d x_i^2: the cost of finding the needle in a haystack

DOI10.1007/S42967-020-00078-2MaRDI QIDQ2667355zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 24 November 2021

Published in Communications on Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.10561

zbMATH Keywords

generalization errormachine learningsample complexity

Mathematics Subject Classification ID

Neural nets and related approaches to inference from stochastic processes (62M45) Statistical aspects of big data and data science (62R07) Numerical summation of series (65B10) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: The task of using machine learning to approximate the mapping $mathbfxmapstosu{m}_{i=1}^d{x}_i^2$ with $x_{i}in[-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 $mathcalO(d^{2.5})$, which is in fact better than the theoretically predicted sample complexity that scales as $mathcalO(d^4)$. Without explicit regularization (also called implicit regularization), the numerically observed sample complexity is significantly higher and is close to $mathcalO(d^{4.5})$.

Recommendations

• scientific article; zbMATH DE number 2087696
• The Barron space and the flow-induced function spaces for neural network models
• Just interpolate: kernel ``ridgeless regression can generalize
• Sparse deep neural networks using \(L_{1,\infty}\)-weight normalization
• An analysis of training and generalization errors in shallow and deep networks

Cites work

• Breaking the curse of dimensionality with convex neural networks
• Early Stopping for Kernel Boosting Algorithms: A General Analysis With Localized Complexities
• Error bounds for approximations with deep ReLU networks
• On early stopping in gradient descent learning
• Spurious valleys in one-hidden-layer neural network optimization landscapes
• Universal approximation bounds for superpositions of a sigmoidal function

Cited in

(2)

• Efficient long-range convolutions for point clouds
• Wide-band butterfly network: stable and efficient inversion via multi-frequency neural networks

Describes a project that uses

Uses Software

• AlexNet
• Keras
• ImageNet
• Adam
• TensorFlow

This page was built for publication: Learning the mapping \(\mathbf{x}\mapsto \sum\limits_{i=1}^d x_i^2\): the cost of finding the needle in a haystack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2667355)