Minimum Width for Universal Approximation in $W^{1,p}$ Spaces

The minimum width for universal approximation has been extensively studied for the $L^p$ norm, the $L^{\infty }$ norm, and more recently the $W^{1,\infty }$ norm. A notable observation is that the minimum width for the $L^{\infty }$ norm is strictly larger than that for the $L^p$ norm for some input/output dimensions; however, no other non-trivial separation between norms is known. In this work, we study the minimum width for the $W^{1,p}$ norm with finite $p$ and ask whether it is separated from the $L^p$ norm and from the $W^{1,\infty }$ norm. We first show that for networks with leaky-ReLU-like activation functions, if the output dimension $d_{\mathrm{out}}$ is larger than $3/2$ times the input dimension $d_{\mathrm{in}}$ and $p\le d_{\mathrm{out}}-d_{\mathrm{in}}$, then the minimum width for the $W^{1,p}$ norm is $d_{\mathrm{out}}$. This value coincides with that for the $L^p$ norm and if $d_{\mathrm{out}}\le 2d_{\mathrm{in}}$, it is strictly smaller than that for the $W^{1,\infty }$ norm. We then show that the $W^{1,p}$ norm is separated from the $L^p$ norm through a finer analysis of the case $d_{\mathrm{out}}=2d_{\mathrm{in}}-1$ with $d_{\mathrm{in}}\ge 3$, where we characterize the minimum width for all $p$. Here, the minimum width coincides with that for the $L^p$ norm if $p\le d_{\mathrm{in}}-1$, increases by one when $p$ exceeds $d_{\mathrm{in}}-1$, and coincides with that for the $W^{1,\infty }$ norm if $p>d_{\mathrm{in}}$. Furthermore, if $d_{\mathrm{in}}$ is odd, it increases by one once more when $p$ exceeds $d_{\mathrm{in}}$. Hence, the $W^{1,p}$ norm is separated from both the $L^p$ norm and the $W^{1,\infty }$ norm. In addition, unlike the $L^p$ norm, the minimum width for the $W^{1,p}$ norm depends on $p$ and even on the parity of $d_{\mathrm{in}}$. We also extend our results to general input and output dimensions, and a general class of activation functions.