{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T02:40:08Z","timestamp":1774838408791,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA9550-18-1-0166"],"award-info":[{"award-number":["FA9550-18-1-0166"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-17-1-0405"],"award-info":[{"award-number":["W911NF-17-1-0405"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-FMitF-1836978, SaTC-Frontiers-1804648, CCF-1652140"],"award-info":[{"award-number":["CCF-FMitF-1836978, SaTC-Frontiers-1804648, CCF-1652140"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,1,16]]},"abstract":"<jats:p>\n            To verify safety and robustness of neural networks, researchers have successfully applied\n            <jats:italic>abstract interpretation<\/jats:italic>\n            , primarily using the interval abstract domain. In this paper, we study the theoretical power and limits of the interval domain for neural-network verification.\n          <\/jats:p>\n          <jats:p>\n            First, we introduce the\n            <jats:italic>interval universal approximation<\/jats:italic>\n            (IUA) theorem. IUA shows that neural networks not only can approximate any continuous function\n            <jats:italic>f<\/jats:italic>\n            (universal approximation) as we have known for decades, but we can find a neural network, using any well-behaved activation function, whose interval bounds are an arbitrarily close approximation of the set semantics of\n            <jats:italic>f<\/jats:italic>\n            (the result of applying\n            <jats:italic>f<\/jats:italic>\n            to a set of inputs). We call this notion of approximation\n            <jats:italic>interval approximation<\/jats:italic>\n            . Our theorem generalizes the recent result of Baader et al. from ReLUs to a rich class of activation functions that we call\n            <jats:italic>squashable functions<\/jats:italic>\n            . Additionally, the IUA theorem implies that we can always construct provably robust neural networks under \u2113\n            <jats:sub>\u221e<\/jats:sub>\n            -norm using almost any practical activation function.\n          <\/jats:p>\n          <jats:p>\n            Second, we study the computational complexity of constructing neural networks that are amenable to precise interval analysis. This is a crucial question, as our constructive proof of IUA is exponential in the size of the approximation domain. We boil this question down to the problem of approximating the range of a neural network with squashable activation functions. We show that the range approximation problem (RA) is a \u0394\n            <jats:sub>2<\/jats:sub>\n            -intermediate problem, which is strictly harder than\n            <jats:italic>NP<\/jats:italic>\n            -complete problems, assuming\n            <jats:italic>coNP<\/jats:italic>\n            \u2284\n            <jats:italic>NP<\/jats:italic>\n            . As a result,\n            <jats:italic>IUA is an inherently hard problem<\/jats:italic>\n            : No matter what abstract domain or computational tools we consider to achieve interval approximation, there is no efficient construction of such a universal approximator. This implies that it is hard to construct a provably robust network, even if we have a robust network to start with.\n          <\/jats:p>","DOI":"10.1145\/3498675","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T17:03:12Z","timestamp":1642006992000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Interval universal approximation for neural networks"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0815-1343","authenticated-orcid":false,"given":"Zi","family":"Wang","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4577-175X","authenticated-orcid":false,"given":"Aws","family":"Albarghouthi","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5181-1100","authenticated-orcid":false,"given":"Gautam","family":"Prakriya","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5877-0436","authenticated-orcid":false,"given":"Somesh","family":"Jha","sequence":"additional","affiliation":[{"name":"University of Wisconsin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680839111"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314614"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) (Proceedings of Machine Learning Research","volume":"301","author":"Anil Cem","year":"2019","unstructured":"Cem Anil , James Lucas , and Roger Grosse . 2019 . Sorting Out Lipschitz Function Approximation . In Proceedings of the 36th International Conference on Machine Learning, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) (Proceedings of Machine Learning Research , Vol. 97). PMLR, Long Beach, California, USA. 291\u2013 301 . http:\/\/proceedings.mlr.press\/v97\/anil19a.html Cem Anil, James Lucas, and Roger Grosse. 2019. Sorting Out Lipschitz Function Approximation. In Proceedings of the 36th International Conference on Machine Learning, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) (Proceedings of Machine Learning Research, Vol. 97). PMLR, Long Beach, California, USA. 291\u2013301. http:\/\/proceedings.mlr.press\/v97\/anil19a.html"},{"key":"e_1_2_2_4_1","volume-title":"Universal Approximation with Certified Networks. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=B1gX8kBtPr","author":"Baader Maximilian","year":"2020","unstructured":"Maximilian Baader , Matthew Mirman , and Martin Vechev . 2020 . Universal Approximation with Certified Networks. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=B1gX8kBtPr Maximilian Baader, Matthew Mirman, and Martin Vechev. 2020. Universal Approximation with Certified Networks. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=B1gX8kBtPr"},{"key":"e_1_2_2_5_1","unstructured":"James Bergstra Guillaume Desjardins Pascal Lamblin and Yoshua Bengio. 2009. Quadratic polynomials learn better image features. Technical report 1337.  James Bergstra Guillaume Desjardins Pascal Lamblin and Yoshua Bengio. 2009. Quadratic polynomials learn better image features. Technical report 1337."},{"key":"e_1_2_2_6_1","volume-title":"4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). arxiv:1511","author":"Clevert Djork-Arn\u00e9","year":"2016","unstructured":"Djork-Arn\u00e9 Clevert , Thomas Unterthiner , and Sepp Hochreiter . 2016 . Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs) . In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). arxiv:1511 .07289 Djork-Arn\u00e9 Clevert, Thomas Unterthiner, and Sepp Hochreiter. 2016. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs). In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). arxiv:1511.07289"},{"key":"e_1_2_2_7_1","unstructured":"Jeremy E. J. Cohen Todd Huster and Ra Cohen. 2019. Universal Lipschitz Approximation in Bounded Depth Neural Networks. arxiv:1904.04861.  Jeremy E. J. Cohen Todd Huster and Ra Cohen. 2019. Universal Lipschitz Approximation in Bounded Depth Neural Networks. arxiv:1904.04861."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512770"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02551274"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68167-2_19"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00058"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_47"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Geoffrey Gordon, David Dunson, and Miroslav Dud\u00edk (Eds.) (Proceedings of Machine Learning Research","volume":"323","author":"Glorot Xavier","year":"2011","unstructured":"Xavier Glorot , Antoine Bordes , and Yoshua Bengio . 2011 . Deep Sparse Rectifier Neural Networks . In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Geoffrey Gordon, David Dunson, and Miroslav Dud\u00edk (Eds.) (Proceedings of Machine Learning Research , Vol. 15). PMLR, Fort Lauderdale, FL, USA. 315\u2013 323 . https:\/\/proceedings.mlr.press\/v15\/glorot11a.html Xavier Glorot, Antoine Bordes, and Yoshua Bengio. 2011. Deep Sparse Rectifier Neural Networks. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Geoffrey Gordon, David Dunson, and Miroslav Dud\u00edk (Eds.) (Proceedings of Machine Learning Research, Vol. 15). PMLR, Fort Lauderdale, FL, USA. 315\u2013323. https:\/\/proceedings.mlr.press\/v15\/glorot11a.html"},{"key":"e_1_2_2_16_1","volume-title":"Explaining and Harnessing Adversarial Examples. In International Conference on Learning Representations. arxiv:1412","author":"Goodfellow Ian","year":"2015","unstructured":"Ian Goodfellow , Jonathon Shlens , and Christian Szegedy . 2015 . Explaining and Harnessing Adversarial Examples. In International Conference on Learning Representations. arxiv:1412 .6572 Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and Harnessing Adversarial Examples. In International Conference on Learning Representations. arxiv:1412.6572"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2019.00494"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.4208\/jcm.1901-m2018-0160"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(89)90020-8"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1419"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63387-9_5"},{"key":"e_1_2_2_22_1","unstructured":"Patrick Kidger and Terry Lyons. 2019. Universal approximation with deep narrow networks. arXiv preprint arXiv:1905.08539.  Patrick Kidger and Terry Lyons. 2019. Universal approximation with deep narrow networks. arXiv preprint arXiv:1905.08539."},{"key":"e_1_2_2_23_1","unstructured":"Alex Krizhevsky Ilya Sutskever and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems. 1097\u20131105.  Alex Krizhevsky Ilya Sutskever and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems. 1097\u20131105."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80131-5"},{"key":"e_1_2_2_25_1","volume-title":"Advances in Neural Information Processing Systems 31","author":"Lin Hongzhou","unstructured":"Hongzhou Lin and Stefanie Jegelka . 2018. ResNet with one-neuron hidden layers is a Universal Approximator . In Advances in Neural Information Processing Systems 31 , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc. , 6169\u20136178. http:\/\/papers.nips.cc\/paper\/7855-resnet-with-one-neuron-hidden-layers-is-a-universal-approximator.pdf Hongzhou Lin and Stefanie Jegelka. 2018. ResNet with one-neuron hidden layers is a Universal Approximator. In Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc., 6169\u20136178. http:\/\/papers.nips.cc\/paper\/7855-resnet-with-one-neuron-hidden-layers-is-a-universal-approximator.pdf"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70139-4"},{"key":"e_1_2_2_27_1","unstructured":"Tomas Mikolov Ilya Sutskever Kai Chen Greg S Corrado and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems. 3111\u20133119.  Tomas Mikolov Ilya Sutskever Kai Chen Greg S Corrado and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems. 3111\u20133119."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research","volume":"3586","author":"Mirman Matthew","year":"2018","unstructured":"Matthew Mirman , Timon Gehr , and Martin Vechev . 2018 . Differentiable Abstract Interpretation for Provably Robust Neural Networks . In Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research , Vol. 80). PMLR, 3578\u2013 3586 . https:\/\/proceedings.mlr.press\/v80\/mirman18b.html Matthew Mirman, Timon Gehr, and Martin Vechev. 2018. Differentiable Abstract Interpretation for Provably Robust Neural Networks. In Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research, Vol. 80). PMLR, 3578\u20133586. https:\/\/proceedings.mlr.press\/v80\/mirman18b.html"},{"key":"e_1_2_2_29_1","unstructured":"Vinod Nair and Geoffrey E Hinton. 2010. Rectified linear units improve restricted boltzmann machines. In ICML.  Vinod Nair and Geoffrey E Hinton. 2010. Rectified linear units improve restricted boltzmann machines. In ICML."},{"key":"e_1_2_2_30_1","volume-title":"Neural networks and deep learning","author":"Nielsen Michael A","year":"2018","unstructured":"Michael A Nielsen . 2015. Neural networks and deep learning . 2018 , Determination press San Francisco , CA. Michael A Nielsen. 2015. Neural networks and deep learning. 2018, Determination press San Francisco, CA."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775051.2677009"},{"key":"e_1_2_2_32_1","unstructured":"Gagandeep Singh Timon Gehr Matthew Mirman Markus P\u00fcschel and Martin Vechev. 2018. Fast and effective robustness certification. In Advances in Neural Information Processing Systems. 10802\u201310813.  Gagandeep Singh Timon Gehr Matthew Mirman Markus P\u00fcschel and Martin Vechev. 2018. Fast and effective robustness certification. In Advances in Neural Information Processing Systems. 10802\u201310813."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290354"},{"key":"e_1_2_2_34_1","volume-title":"Evaluating Robustness of Neural Networks with Mixed Integer Programming. In 7th International Conference on Learning Representations, ICLR 2019","author":"Tjeng Vincent","year":"2019","unstructured":"Vincent Tjeng , Kai Y. Xiao , and Russ Tedrake . 2019 . Evaluating Robustness of Neural Networks with Mixed Integer Programming. In 7th International Conference on Learning Representations, ICLR 2019 , New Orleans, LA, USA , May 6-9, 2019. OpenReview.net. https:\/\/openreview.net\/forum?id=HyGIdiRqtm Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. 2019. Evaluating Robustness of Neural Networks with Mixed Integer Programming. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. https:\/\/openreview.net\/forum?id=HyGIdiRqtm"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277203.3277323"},{"key":"e_1_2_2_37_1","volume-title":"Towards Fast Computation of Certified Robustness for ReLU Networks. In International Conference on Machine Learning (ICML).","author":"Weng Tsui-Wei","year":"2018","unstructured":"Tsui-Wei Weng , Huan Zhang , Hongge Chen , Zhao Song , Cho-Jui Hsieh , Duane Boning , Inderjit S. Dhillon , and Luca Daniel . 2018 . Towards Fast Computation of Certified Robustness for ReLU Networks. In International Conference on Machine Learning (ICML). Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S. Dhillon, and Luca Daniel. 2018. Towards Fast Computation of Certified Robustness for ReLU Networks. In International Conference on Machine Learning (ICML)."},{"key":"e_1_2_2_38_1","unstructured":"Cihang Xie Mingxing Tan Boqing Gong Alan Yuille and Quoc V Le. 2020. Smooth Adversarial Training. arXiv preprint arXiv:2006.14536.  Cihang Xie Mingxing Tan Boqing Gong Alan Yuille and Quoc V Le. 2020. Smooth Adversarial Training. arXiv preprint arXiv:2006.14536."},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020","volume":"11032","author":"Zhang Yuhao","year":"2020","unstructured":"Yuhao Zhang , Aws Albarghouthi , and Loris D\u2019Antoni . 2020 . Robustness to Programmable String Transformations via Augmented Abstract Training . In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 , 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research , Vol. 119). PMLR, 11023\u2013 11032 . http:\/\/proceedings.mlr.press\/v119\/zhang20b.html Yuhao Zhang, Aws Albarghouthi, and Loris D\u2019Antoni. 2020. Robustness to Programmable String Transformations via Augmented Abstract Training. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 11023\u201311032. http:\/\/proceedings.mlr.press\/v119\/zhang20b.html"},{"key":"e_1_2_2_40_1","volume-title":"Certified Robustness to Programmable Transformations in LSTMs. CoRR, abs\/2102.07818","author":"Zhang Yuhao","year":"2021","unstructured":"Yuhao Zhang , Aws Albarghouthi , and Loris D\u2019Antoni . 2021. Certified Robustness to Programmable Transformations in LSTMs. CoRR, abs\/2102.07818 ( 2021 ), arxiv:2102.07818. arxiv:2102.07818 Yuhao Zhang, Aws Albarghouthi, and Loris D\u2019Antoni. 2021. Certified Robustness to Programmable Transformations in LSTMs. CoRR, abs\/2102.07818 (2021), arxiv:2102.07818. arxiv:2102.07818"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498675","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498675","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:28Z","timestamp":1750188628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":40,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2022,1,16]]}},"alternative-id":["10.1145\/3498675"],"URL":"https:\/\/doi.org\/10.1145\/3498675","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"2022-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}