Neural Networks and Rational Functions

Matus Telgarsky
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3387-3393, 2017.

Abstract

Neural networks and rational functions efficiently approximate each other. In more detail, it is shown here that for any ReLU network, there exists a rational function of degree $O(polylog(1/\epsilon))$ which is $\epsilon$-close, and similarly for any rational function there exists a ReLU network of size $O(polylog(1/\epsilon))$ which is $\epsilon$-close. By contrast, polynomials need degree $\Omega(poly(1/\epsilon))$ to approximate even a single ReLU. When converting a ReLU network to a rational function as above, the hidden constants depend exponentially on the number of layers, which is shown to be tight; in other words, a compositional representation can be beneficial even for rational functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-telgarsky17a, title = {Neural Networks and Rational Functions}, author = {Matus Telgarsky}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3387--3393}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/telgarsky17a/telgarsky17a.pdf}, url = {https://proceedings.mlr.press/v70/telgarsky17a.html}, abstract = {Neural networks and rational functions efficiently approximate each other. In more detail, it is shown here that for any ReLU network, there exists a rational function of degree $O(polylog(1/\epsilon))$ which is $\epsilon$-close, and similarly for any rational function there exists a ReLU network of size $O(polylog(1/\epsilon))$ which is $\epsilon$-close. By contrast, polynomials need degree $\Omega(poly(1/\epsilon))$ to approximate even a single ReLU. When converting a ReLU network to a rational function as above, the hidden constants depend exponentially on the number of layers, which is shown to be tight; in other words, a compositional representation can be beneficial even for rational functions.} }
Endnote
%0 Conference Paper %T Neural Networks and Rational Functions %A Matus Telgarsky %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-telgarsky17a %I PMLR %P 3387--3393 %U https://proceedings.mlr.press/v70/telgarsky17a.html %V 70 %X Neural networks and rational functions efficiently approximate each other. In more detail, it is shown here that for any ReLU network, there exists a rational function of degree $O(polylog(1/\epsilon))$ which is $\epsilon$-close, and similarly for any rational function there exists a ReLU network of size $O(polylog(1/\epsilon))$ which is $\epsilon$-close. By contrast, polynomials need degree $\Omega(poly(1/\epsilon))$ to approximate even a single ReLU. When converting a ReLU network to a rational function as above, the hidden constants depend exponentially on the number of layers, which is shown to be tight; in other words, a compositional representation can be beneficial even for rational functions.
APA
Telgarsky, M.. (2017). Neural Networks and Rational Functions. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3387-3393 Available from https://proceedings.mlr.press/v70/telgarsky17a.html.

Related Material