A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks

We study the fundamental limits to the expressive power of neural networks.\nGiven two sets $F$, $G$ of real-valued functions, we first prove a general\nlower bound on how well functions in $F$ can be approximated in $L^p(\\mu)$ norm\nby functions in $G$, for any $p \\geq 1$ and any probability measure $\\mu$. The\nlower bound depends on the packing number of $F$, the range of $F$, and the\nfat-shattering dimension of $G$. We then instantiate this bound to the case\nwhere $G$ corresponds to a piecewise-polynomial feed-forward neural network,\nand describe in details the application to two sets $F$: H{\\"o}lder balls and\nmultivariate monotonic functions. Beside matching (known or new) upper bounds\nup to log factors, our lower bounds shed some light on the similarities or\ndifferences between approximation in $L^p$ norm or in sup norm, solving an open\nquestion by DeVore et al. (2021). Our proof strategy differs from the sup norm\ncase and uses a key probability result of Mendelson (2002).\n