Minimum Width of Leaky-ReLU Neural Networks for Uniform Universal Approximation

Li’Ang Li, Yifei Duan, Guanghua Ji, Yongqiang Cai
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:19460-19470, 2023.

Abstract

The study of universal approximation properties (UAP) for neural networks (NN) has a long history. When the network width is unlimited, only a single hidden layer is sufficient for UAP. In contrast, when the depth is unlimited, the width for UAP needs to be not less than the critical width wmin, where d_x and d_y are the dimensions of the input and output, respectively. Recently, (Cai, 2022) shows that a leaky-ReLU NN with this critical width can achieve UAP for L^p functions on a compact domain \mathcal{K}, i.e., the UAP for L^p(\mathcal{K},\mathbb{R}^{d_y}). This paper examines a uniform UAP for the function class C(\mathcal{K},\mathbb{R}^{d_y}) and gives the exact minimum width of the leaky-ReLU NN as w_{\min}=\max(d_x+1,d_y)+1_{d_y=d_x+1}, which involves the effects of the output dimensions. To obtain this result, we propose a novel lift-flow-discretization approach that shows that the uniform UAP has a deep connection with topological theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-li23g, title = {Minimum Width of Leaky-{R}e{LU} Neural Networks for Uniform Universal Approximation}, author = {Li, Li'Ang and Duan, Yifei and Ji, Guanghua and Cai, Yongqiang}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {19460--19470}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/li23g/li23g.pdf}, url = {https://proceedings.mlr.press/v202/li23g.html}, abstract = {The study of universal approximation properties (UAP) for neural networks (NN) has a long history. When the network width is unlimited, only a single hidden layer is sufficient for UAP. In contrast, when the depth is unlimited, the width for UAP needs to be not less than the critical width $w^*_{\min}=\max(d_x,d_y)$, where $d_x$ and $d_y$ are the dimensions of the input and output, respectively. Recently, (Cai, 2022) shows that a leaky-ReLU NN with this critical width can achieve UAP for $L^p$ functions on a compact domain $\mathcal{K}$, i.e., the UAP for $L^p(\mathcal{K},\mathbb{R}^{d_y})$. This paper examines a uniform UAP for the function class $C(\mathcal{K},\mathbb{R}^{d_y})$ and gives the exact minimum width of the leaky-ReLU NN as $w_{\min}=\max(d_x+1,d_y)+1_{d_y=d_x+1}$, which involves the effects of the output dimensions. To obtain this result, we propose a novel lift-flow-discretization approach that shows that the uniform UAP has a deep connection with topological theory.} }
Endnote
%0 Conference Paper %T Minimum Width of Leaky-ReLU Neural Networks for Uniform Universal Approximation %A Li’Ang Li %A Yifei Duan %A Guanghua Ji %A Yongqiang Cai %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-li23g %I PMLR %P 19460--19470 %U https://proceedings.mlr.press/v202/li23g.html %V 202 %X The study of universal approximation properties (UAP) for neural networks (NN) has a long history. When the network width is unlimited, only a single hidden layer is sufficient for UAP. In contrast, when the depth is unlimited, the width for UAP needs to be not less than the critical width $w^*_{\min}=\max(d_x,d_y)$, where $d_x$ and $d_y$ are the dimensions of the input and output, respectively. Recently, (Cai, 2022) shows that a leaky-ReLU NN with this critical width can achieve UAP for $L^p$ functions on a compact domain $\mathcal{K}$, i.e., the UAP for $L^p(\mathcal{K},\mathbb{R}^{d_y})$. This paper examines a uniform UAP for the function class $C(\mathcal{K},\mathbb{R}^{d_y})$ and gives the exact minimum width of the leaky-ReLU NN as $w_{\min}=\max(d_x+1,d_y)+1_{d_y=d_x+1}$, which involves the effects of the output dimensions. To obtain this result, we propose a novel lift-flow-discretization approach that shows that the uniform UAP has a deep connection with topological theory.
APA
Li, L., Duan, Y., Ji, G. & Cai, Y.. (2023). Minimum Width of Leaky-ReLU Neural Networks for Uniform Universal Approximation. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:19460-19470 Available from https://proceedings.mlr.press/v202/li23g.html.

Related Material