{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:22:36Z","timestamp":1767183756412,"version":"3.44.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1838179","ECCS-2037304"],"award-info":[{"award-number":["IIS-1838179","ECCS-2037304"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005801","name":"Facebook","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005801","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s10107-024-02153-5","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T09:31:29Z","timestamp":1731058289000},"page":"737-769","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Neural spectrahedra and semidefinite lifts: global convex optimization of degree-two polynomial activation neural networks in polynomial-time"],"prefix":"10.1007","volume":"213","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0079-8126","authenticated-orcid":false,"given":"Burak","family":"Bartan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mert","family":"Pilanci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"issue":"1","key":"2153_CR1","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1080\/23307706.2017.1397554","volume":"5","author":"A Agrawal","year":"2018","unstructured":"Agrawal, A., Verschueren, R., Diamond, S., Boyd, S.: A rewriting system for convex optimization problems. J. Control Decision 5(1), 42\u201360 (2018)","journal-title":"J. Control Decision"},{"key":"2153_CR2","unstructured":"Allen-Zhu, Z., Li, Y.: Backward feature correction: how deep learning performs deep learning. arXiv preprint arXiv:2001.04413 (2020)"},{"key":"2153_CR3","unstructured":"Arora, R., Basu, A., Mianjy, P., Mukherjee, A.: Understanding deep neural networks with rectified linear units. In: 6th International Conference on Learning Representations, ICLR 2018 (2018)"},{"key":"2153_CR4","unstructured":"Bartan, B., Pilanci, M.: Neural spectrahedra and semidefinite lifts: global convex optimization of polynomial activation neural networks in fully polynomial-time. CoRR arXiv:2101.02429 (2021)"},{"key":"2153_CR5","unstructured":"Belilovsky, E., Eickenberg, M., Oyallon, E.: Greedy layerwise learning can scale to imagenet. CoRR arXiv:1812.11446 (2018)"},{"key":"2153_CR6","unstructured":"Bienstock, D., Mu\u00f1oz, G., Pokutta, S.: Principled deep neural network training through linear programming (2018)"},{"key":"2153_CR7","doi-asserted-by":"crossref","unstructured":"Blondel, M., Fujino, A., Ueda, N.: Convex factorization machines. In: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) (2015)","DOI":"10.1007\/978-3-319-23525-7_2"},{"key":"2153_CR8","unstructured":"Blondel, M., Niculae, V., Otsuka, T., Ueda, N.: Multi-output polynomial networks and factorization machines. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS\u201917, pp. 3351\u20133361. Curran Associates Inc., Red Hook (2017)"},{"key":"2153_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press, Cambridge (2004)"},{"key":"2153_CR10","doi-asserted-by":"crossref","unstructured":"Burer, S.: Copositive programming. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 201\u2013218. Springer (2012)","DOI":"10.1007\/978-1-4614-0769-0_8"},{"issue":"83","key":"2153_CR11","first-page":"1","volume":"17","author":"S Diamond","year":"2016","unstructured":"Diamond, S., Boyd, S.: CVXPY: A Python-embedded modeling language for convex optimization. J. Mach. Learn. Res. 17(83), 1\u20135 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"2153_CR12","unstructured":"Du, S., Lee, J.: On the power of over-parametrization in neural networks with quadratic activation. In: J.\u00a0Dy, A.\u00a0Krause (eds.) Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol.\u00a080, pp. 1329\u20131338. PMLR, Stockholmsm\u00e4ssan, Stockholm Sweden (2018). http:\/\/proceedings.mlr.press\/v80\/du18a.html"},{"key":"2153_CR13","unstructured":"Ergen, T., Pilanci, M.: Convex geometry of two-layer Relu networks: Implicit autoencoding and interpretable models. In: International Conference on Artificial Intelligence and Statistics, pp. 4024\u20134033. PMLR (2020)"},{"key":"2153_CR14","unstructured":"Ergen, T., Pilanci, M.: Implicit convex regularizers of CNN architectures: Convex optimization of two- and three-layer networks in polynomial time. arXiv preprint arXiv:2006.14798 (2020)"},{"key":"2153_CR15","unstructured":"Ergen, T., Pilanci, M.: Revealing the structure of deep neural networks via convex duality. arXiv preprint arXiv:2002.09773 (2020)"},{"key":"2153_CR16","doi-asserted-by":"crossref","unstructured":"Fickus, M., Mixon, D.G., Nelson, A.A., Wang, Y.: Phase retrieval from very few measurements. arXiv preprint arXiv:1307.7176 (2013)","DOI":"10.1016\/j.laa.2014.02.011"},{"key":"2153_CR17","unstructured":"Gamarnik, D., K\u0131z\u0131lda\u011f, E.C., Zadik, I.: Stationary points of shallow neural networks with quadratic activation function. arXiv preprint arXiv:1912.01599 (2020)"},{"key":"2153_CR18","unstructured":"Gilad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Cryptonets: applying neural networks to encrypted data with high throughput and accuracy. In: International Conference on Machine Learning, pp. 201\u2013210 (2016)"},{"key":"2153_CR19","unstructured":"Goel, S., Kanade, V., Klivans, A., Thaler, J.: Reliably learning the Relu in polynomial time. In: Kale, S., Shamir, O. (eds.) Proceedings of the 2017 Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 65, pp. 1004\u20131042. PMLR, Amsterdam (2017)"},{"key":"2153_CR20","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"2153_CR21","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. JACM 48(4), 798\u2013859 (2001)","journal-title":"JACM"},{"key":"2153_CR22","unstructured":"Hesamifard, E., Takabi, H., Ghasemi, M.: Cryptodl: towards deep learning over encrypted data. In: Annual Computer Security Applications Conference (ACSAC 2016), Los Angeles, California, USA, vol.\u00a011 (2016)"},{"issue":"1","key":"2153_CR23","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable CSPS? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"key":"2153_CR24","unstructured":"Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. In: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7\u20139, 2015, Conference Track Proceedings (2015). arXiv:1412.6980"},{"key":"2153_CR25","unstructured":"Lacotte, J., Pilanci, M.: All local minima are global for two-layer Relu neural networks: The hidden convex optimization landscape. arXiv preprint arXiv:2006.05900 (2020)"},{"issue":"224","key":"2153_CR26","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/0024-3795(95)00271-R","volume":"223","author":"M Laurent","year":"1995","unstructured":"Laurent, M., Poljak, S.: On a positive semidefinite relaxation of the cut polytope. Linear Algebra Appl. 223(224), 439\u2013461 (1995)","journal-title":"Linear Algebra Appl."},{"key":"2153_CR27","doi-asserted-by":"publisher","unstructured":"Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Discrete Optimization, Handbooks in Operations Research and Management Science, vol.\u00a012, pp. 393\u2013514. Elsevier (2005). https:\/\/doi.org\/10.1016\/S0927-0507(05)12008-8. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0927050705120088","DOI":"10.1016\/S0927-0507(05)12008-8"},{"key":"2153_CR28","unstructured":"Lederer, J.: No spurious local minima: on the optimization landscapes of wide and deep neural networks (2020)"},{"key":"2153_CR29","unstructured":"Livni, R., Shalev-Shwartz, S., Shamir, O.: On the computational efficiency of training neural networks. NIPS\u201914, pp. 855\u2013863 (2014)"},{"key":"2153_CR30","unstructured":"Mannelli, S.S., Vanden-Eijnden, E., Zdeborov\u00e1, L.: Optimization and generalization of shallow neural networks with quadratic activation functions. arXiv preprint arXiv:2006.15459 (2020)"},{"key":"2153_CR31","doi-asserted-by":"publisher","unstructured":"Mishra, P., Lehmkuhl, R., Srinivasan, A., Zheng, W., Popa, R.A.: Delphi: a cryptographic inference system for neural networks. PPMLP\u201920 p. 27-30 (2020). https:\/\/doi.org\/10.1145\/3411501.3419418","DOI":"10.1145\/3411501.3419418"},{"key":"2153_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7838-7","volume-title":"The geometry of Minkowski spacetime: An introduction to the mathematics of the special theory of relativity","author":"GL Naber","year":"2012","unstructured":"Naber, G.L.: The geometry of Minkowski spacetime: An introduction to the mathematics of the special theory of relativity, vol. 92. Springer, Berlin (2012)"},{"key":"2153_CR33","doi-asserted-by":"crossref","unstructured":"Nesterov, Y., Wolkowicz, H., Ye, Y.: Semidefinite programming relaxations of nonconvex quadratic optimization. In: Handbook of Semidefinite Programming, pp. 361\u2013419. Springer (2000)","DOI":"10.1007\/978-1-4615-4381-7_13"},{"key":"2153_CR34","doi-asserted-by":"publisher","first-page":"153098","DOI":"10.1109\/ACCESS.2020.3017436","volume":"8","author":"S Obla","year":"2020","unstructured":"Obla, S., Gong, X., Aloufi, A., Hu, P., Takabi, D.: Effective activation functions for homomorphic evaluation of deep neural networks. IEEE Access 8, 153098\u2013153112 (2020)","journal-title":"IEEE Access"},{"issue":"3","key":"2153_CR35","doi-asserted-by":"publisher","first-page":"1042","DOI":"10.1007\/s10957-016-0892-3","volume":"169","author":"B O\u2019Donoghue","year":"2016","unstructured":"O\u2019Donoghue, B., Chu, E., Parikh, N., Boyd, S.: Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3), 1042\u20131068 (2016)","journal-title":"J. Optim. Theory Appl."},{"key":"2153_CR36","unstructured":"O\u2019Donoghue, B., Chu, E., Parikh, N., Boyd, S.: SCS: Splitting conic solver, version 2.1.2. https:\/\/github.com\/cvxgrp\/scs (2019)"},{"key":"2153_CR37","unstructured":"Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., Chintala, S.: Pytorch: an imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems 32 pp. 8024\u20138035 (2019). http:\/\/papers.neurips.cc\/paper\/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf"},{"key":"2153_CR38","unstructured":"Pilanci, M., Ergen, T.: Neural networks are convex regularizers: exact polynomial-time convex optimization formulations for two-layer networks. In: Proceedings of the International Conference on Machine Learning (ICML 2020) (2020)"},{"issue":"3","key":"2153_CR39","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/S003614450444614X","volume":"49","author":"I P\u00f3lik","year":"2007","unstructured":"P\u00f3lik, I., Terlaky, T.: A survey of the s-lemma. SIAM Rev. 49(3), 371\u2013418 (2007). https:\/\/doi.org\/10.1137\/S003614450444614X","journal-title":"SIAM Rev."},{"key":"2153_CR40","unstructured":"Ramachandran, P., Zoph, B., Le, Q.: Searching for activation functions. arXiv preprint arXiv:1710.05941 (2018)"},{"key":"2153_CR41","unstructured":"Sahiner, A., Ergen, T., Pauly, J., Pilanci, M.: Vector-output Relu neural network problems are copositive programs: convex analysis of two layer networks and polynomial-time algorithms. arXiv preprint arXiv:2012.13329 (2020)"},{"key":"2153_CR42","unstructured":"Sahiner, A., Mardani, M., Ozturkler, B., Pilanci, M., Pauly, J.: Convex regularization behind neural reconstruction. arXiv preprint arXiv:2012.05169 (2020)"},{"issue":"13","key":"2153_CR43","doi-asserted-by":"publisher","first-page":"3361","DOI":"10.1109\/TSP.2019.2916743","volume":"67","author":"M Soltani","year":"2019","unstructured":"Soltani, M., Hegde, C.: Fast and provable algorithms for learning two-layer polynomial neural networks. IEEE Trans. Signal Process. 67(13), 3361\u20133371 (2019). https:\/\/doi.org\/10.1109\/TSP.2019.2916743","journal-title":"IEEE Trans. Signal Process."},{"issue":"2","key":"2153_CR44","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1109\/TIT.2018.2854560","volume":"65","author":"M Soltanolkotabi","year":"2019","unstructured":"Soltanolkotabi, M., Javanmard, A., Lee, J.D.: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Trans. Inf. Theor. 65(2), 742\u2013769 (2019). https:\/\/doi.org\/10.1109\/TIT.2018.2854560","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"6","key":"2153_CR45","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"key":"2153_CR46","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","author":"H Wolkowicz","year":"2012","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, vol. 27. Springer, Berlin (2012)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02153-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02153-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02153-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T00:41:51Z","timestamp":1757119311000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02153-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":46,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["2153"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02153-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"14 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"No participants, not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"No participants, not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}