{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T16:18:52Z","timestamp":1776183532755,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":108,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2103300, 2203741"],"award-info":[{"award-number":["2103300, 2203741"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585209","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1671-1684","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning Polynomial Transformations via Generalized Tensor Decompositions"],"prefix":"10.1145","author":[{"given":"Sitan","family":"Chen","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA \/ Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanzhi","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA \/ Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anru R.","family":"Zhang","sequence":"additional","affiliation":[{"name":"Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Jayadev Acharya Ashkan Jafarpour Alon Orlitsky and Ananda Theertha Suresh. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. arXiv preprint arXiv:1402.4746. \t\t\t\t  Jayadev Acharya Ashkan Jafarpour Alon Orlitsky and Ananda Theertha Suresh. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. arXiv preprint arXiv:1402.4746."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_3_2_1_3_1","unstructured":"Zeyuan Allen-Zhu and Yuanzhi Li. 2021. Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions. arXiv preprint arXiv:2106.02619. \t\t\t\t  Zeyuan Allen-Zhu and Yuanzhi Li. 2021. Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions. arXiv preprint arXiv:2106.02619."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2697055"},{"key":"e_1_3_2_1_5_1","volume-title":"Conference on Learning Theory. 1135\u20131164","author":"Anderson Joseph","year":"2014","unstructured":"Joseph Anderson , Mikhail Belkin , Navin Goyal , Luis Rademacher , and James Voss . 2014 . The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures . In Conference on Learning Theory. 1135\u20131164 . Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James Voss. 2014. The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures. In Conference on Learning Theory. 1135\u20131164."},{"key":"e_1_3_2_1_6_1","volume-title":"Cryptographic hardness of random local functions. Computational complexity, 25, 3","author":"Applebaum Benny","year":"2016","unstructured":"Benny Applebaum . 2016. Cryptographic hardness of random local functions. Computational complexity, 25, 3 ( 2016 ), 667\u2013722. Benny Applebaum. 2016. Cryptographic hardness of random local functions. Computational complexity, 25, 3 (2016), 667\u2013722."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_2_1_8_1","volume-title":"International Conference on Machine Learning. 224\u2013232","author":"Arora Sanjeev","year":"2017","unstructured":"Sanjeev Arora , Rong Ge , Yingyu Liang , Tengyu Ma , and Yi Zhang . 2017 . Generalization and equilibrium in generative adversarial nets (gans) . In International Conference on Machine Learning. 224\u2013232 . Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. 2017. Generalization and equilibrium in generative adversarial nets (gans). In International Conference on Machine Learning. 224\u2013232."},{"key":"e_1_3_2_1_9_1","volume-title":"Conference on learning theory. 113\u2013149","author":"Arora Sanjeev","year":"2015","unstructured":"Sanjeev Arora , Rong Ge , Tengyu Ma , and Ankur Moitra . 2015 . Simple, efficient, and neural algorithms for sparse coding . In Conference on learning theory. 113\u2013149 . Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. 2015. Simple, efficient, and neural algorithms for sparse coding. In Conference on learning theory. 113\u2013149."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055482"},{"key":"e_1_3_2_1_11_1","volume-title":"Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. Advances in Neural Information Processing Systems, 25","author":"Arora Sanjeev","year":"2012","unstructured":"Sanjeev Arora , Rong Ge , Ankur Moitra , and Sushant Sachdeva . 2012. Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. Advances in Neural Information Processing Systems, 25 ( 2012 ). Sanjeev Arora, Rong Ge, Ankur Moitra, and Sushant Sachdeva. 2012. Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. Advances in Neural Information Processing Systems, 25 (2012)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000512"},{"key":"e_1_3_2_1_13_1","volume-title":"International Conference on Learning Representations.","author":"Arora Sanjeev","year":"2018","unstructured":"Sanjeev Arora , Andrej Risteski , and Yi Zhang . 2018 . Do GANs learn the distribution? some theory and empirics . In International Conference on Learning Representations. Sanjeev Arora, Andrej Risteski, and Yi Zhang. 2018. Do GANs learn the distribution? some theory and empirics. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_14_1","volume-title":"Approximability of Discriminators Implies Diversity in GANs. In International Conference on Learning Representations.","author":"Bai Yu","year":"2018","unstructured":"Yu Bai , Tengyu Ma , and Andrej Risteski . 2018 . Approximability of Discriminators Implies Diversity in GANs. In International Conference on Learning Representations. Yu Bai, Tengyu Ma, and Andrej Risteski. 2018. Approximability of Discriminators Implies Diversity in GANs. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_15_1","volume-title":"Black box approximation of tensors in hierarchical Tucker format. Linear algebra and its applications, 438, 2","author":"Ballani Jonas","year":"2013","unstructured":"Jonas Ballani , Lars Grasedyck , and Melanie Kluge . 2013. Black box approximation of tensors in hierarchical Tucker format. Linear algebra and its applications, 438, 2 ( 2013 ), 639\u2013657. Jonas Ballani, Lars Grasedyck, and Melanie Kluge. 2013. Black box approximation of tensors in hierarchical Tucker format. Linear algebra and its applications, 438, 2 (2013), 639\u2013657."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090818X"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00043"},{"key":"e_1_3_2_1_20_1","first-page":"14699","article-title":"Efficient distance approximation for structured high-dimensional distributions via learning","volume":"33","author":"Bhattacharyya Arnab","year":"2020","unstructured":"Arnab Bhattacharyya , Sutanu Gayen , Kuldeep S Meel , and NV Vinodchandran . 2020 . Efficient distance approximation for structured high-dimensional distributions via learning . Advances in Neural Information Processing Systems , 33 (2020), 14699 \u2013 14711 . Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S Meel, and NV Vinodchandran. 2020. Efficient distance approximation for structured high-dimensional distributions via learning. Advances in Neural Information Processing Systems, 33 (2020), 14699\u201314711.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451066"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Enric Boix-Adsera Guy Bresler and Frederic Koehler. 2021. Chow-liu++: Optimal prediction-centric learning of tree ising models. arXiv preprint arXiv:2106.03969. \t\t\t\t  Enric Boix-Adsera Guy Bresler and Frederic Koehler. 2021. Chow-liu++: Optimal prediction-centric learning of tree ising models. arXiv preprint arXiv:2106.03969.","DOI":"10.1109\/FOCS52979.2021.00049"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1808"},{"key":"e_1_3_2_1_25_1","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Bresler Guy","unstructured":"Guy Bresler , Elchanan Mossel , and Allan Sly . 2008. Reconstruction of Markov random fields from samples: Some observations and algorithms . In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques . Springer , 343\u2013356. Guy Bresler, Elchanan Mossel, and Allan Sly. 2008. Reconstruction of Markov random fields from samples: Some observations and algorithms. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, 343\u2013356."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399541"},{"key":"e_1_3_2_1_27_1","unstructured":"Minshuo Chen Wenjing Liao Hongyuan Zha and Tuo Zhao. 2020. Statistical guarantees of generative adversarial networks for distribution estimation. arXiv preprint arXiv:2002.03938. \t\t\t\t  Minshuo Chen Wenjing Liao Hongyuan Zha and Tuo Zhao. 2020. Statistical guarantees of generative adversarial networks for distribution estimation. arXiv preprint arXiv:2002.03938."},{"key":"e_1_3_2_1_28_1","unstructured":"Sitan Chen Aravind Gollakota Adam R. Klivans and Raghu Meka. 2022. Hardness of noise-free learning for two-hidden-layer neural networks. In NeurIPS. \t\t\t\t  Sitan Chen Aravind Gollakota Adam R. Klivans and Raghu Meka. 2022. Hardness of noise-free learning for two-hidden-layer neural networks. In NeurIPS."},{"key":"e_1_3_2_1_29_1","unstructured":"Sitan Chen Jerry Li and Yuanzhi Li. 2022. Learning (very) simple generative models is hard. In NeurIPS. \t\t\t\t  Sitan Chen Jerry Li and Yuanzhi Li. 2022. Learning (very) simple generative models is hard. In NeurIPS."},{"key":"e_1_3_2_1_30_1","unstructured":"Sitan Chen Jerry Li Yuanzhi Li and Raghu Meka. 2022. Minimax Optimality (Probably) Doesn\u2019t Imply Distribution Learning for GANs. arXiv preprint arXiv:2201.07206. \t\t\t\t  Sitan Chen Jerry Li Yuanzhi Li and Raghu Meka. 2022. Minimax Optimality (Probably) Doesn\u2019t Imply Distribution Learning for GANs. arXiv preprint arXiv:2201.07206."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1270689"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_1_33_1","volume-title":"Independent component analysis, a new concept? Signal processing, 36, 3","author":"Comon Pierre","year":"1994","unstructured":"Pierre Comon . 1994. Independent component analysis, a new concept? Signal processing, 36, 3 ( 1994 ), 287\u2013314. Pierre Comon. 1994. Independent component analysis, a new concept? Signal processing, 36, 3 (1994), 287\u2013314."},{"key":"e_1_3_2_1_34_1","volume-title":"Handbook of Blind Source Separation: Independent component analysis and applications","author":"Comon Pierre","unstructured":"Pierre Comon and Christian Jutten . 2010. Handbook of Blind Source Separation: Independent component analysis and applications . Academic press . Pierre Comon and Christian Jutten. 2010. Handbook of Blind Source Separation: Independent component analysis and applications. Academic press."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007417612269"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"e_1_3_2_1_37_1","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","volume":"8","author":"Dasgupta Sanjoy","year":"2007","unstructured":"Sanjoy Dasgupta and Leonard J Schulman . 2007 . A probabilistic analysis of EM for mixtures of separated, spherical Gaussians . Journal of Machine Learning Research , 8 (2007), 203 \u2013 226 . Sanjoy Dasgupta and Leonard J Schulman. 2007. A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. Journal of Machine Learning Research, 8 (2007), 203\u2013226.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00067"},{"key":"e_1_3_2_1_39_1","unstructured":"Constantinos Daskalakis Andrew Ilyas Vasilis Syrgkanis and Haoyang Zeng. 2017. Training gans with optimism. arXiv preprint arXiv:1711.00141. \t\t\t\t  Constantinos Daskalakis Andrew Ilyas Vasilis Syrgkanis and Haoyang Zeng. 2017. Training gans with optimism. arXiv preprint arXiv:1711.00141."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451006"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898346995"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1721"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00026"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_3_2_1_45_1","volume-title":"Conference on Learning Theory. 1645\u20131682","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas , Daniel M Kane , Alistair Stewart , and Yuxin Sun . 2021 . Outlier-robust learning of ising models under dobrushin\u2019s condition . In Conference on Learning Theory. 1645\u20131682 . Ilias Diakonikolas, Daniel M Kane, Alistair Stewart, and Yuxin Sun. 2021. Outlier-robust learning of ising models under dobrushin\u2019s condition. In Conference on Learning Theory. 1645\u20131682."},{"key":"e_1_3_2_1_46_1","unstructured":"William Fedus Mihaela Rosca Balaji Lakshminarayanan Andrew M Dai Shakir Mohamed and Ian Goodfellow. 2017. Many paths to equilibrium: GANs do not need to decrease a divergence at every step. arXiv preprint arXiv:1710.08446. \t\t\t\t  William Fedus Mihaela Rosca Balaji Lakshminarayanan Andrew M Dai Shakir Mohamed and Ian Goodfellow. 2017. Many paths to equilibrium: GANs do not need to decrease a divergence at every step. arXiv preprint arXiv:1710.08446."},{"key":"e_1_3_2_1_47_1","unstructured":"Soheil Feizi Farzan Farnia Tony Ginart and David Tse. 2017. Understanding gans: the lqg setting. arXiv preprint arXiv:1710.10793. \t\t\t\t  Soheil Feizi Farzan Farnia Tony Ginart and David Tse. 2017. Understanding gans: the lqg setting. arXiv preprint arXiv:1710.10793."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/060670705"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548495"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_1_51_1","volume-title":"Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. arXiv preprint arXiv:1504.05287","author":"Ge Rong","unstructured":"Rong Ge and Tengyu Ma. 2015. Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. arXiv preprint arXiv:1504.05287 . Rong Ge and Tengyu Ma. 2015. Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. arXiv preprint arXiv:1504.05287."},{"key":"e_1_3_2_1_52_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. 1802\u20131811","author":"Gidel Gauthier","year":"2019","unstructured":"Gauthier Gidel , Reyhane Askari Hemmat , Mohammad Pezeshki , R\u00e9mi Le Priol , Gabriel Huang , Simon Lacoste-Julien , and Ioannis Mitliagkas . 2019 . Negative momentum for improved game dynamics . In The 22nd International Conference on Artificial Intelligence and Statistics. 1802\u20131811 . Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, R\u00e9mi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. 2019. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics. 1802\u20131811."},{"key":"e_1_3_2_1_53_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 3557\u20133566","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel . 2020 . Learning ising and potts models with latent variables . In International Conference on Artificial Intelligence and Statistics. 3557\u20133566 . Surbhi Goel. 2020. Learning ising and potts models with latent variables. In International Conference on Artificial Intelligence and Statistics. 3557\u20133566."},{"key":"e_1_3_2_1_54_1","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2011. Candidate one-way functions based on expander graphs . In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation . Springer , 76\u201387. Oded Goldreich. 2011. Candidate one-way functions based on expander graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 76\u201387."},{"key":"e_1_3_2_1_55_1","volume-title":"Generative adversarial nets. Advances in neural information processing systems, 27","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow , Jean Pouget-Abadie , Mehdi Mirza , Bing Xu , David Warde-Farley , Sherjil Ozair , Aaron Courville , and Yoshua Bengio . 2014. Generative adversarial nets. Advances in neural information processing systems, 27 ( 2014 ). Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. Advances in neural information processing systems, 27 (2014)."},{"key":"e_1_3_2_1_56_1","series-title":"SIAM journal on matrix analysis and applications, 31, 4","volume-title":"Hierarchical singular value decomposition of tensors","author":"Grasedyck Lars","year":"2010","unstructured":"Lars Grasedyck . 2010. Hierarchical singular value decomposition of tensors . SIAM journal on matrix analysis and applications, 31, 4 ( 2010 ), 2029\u20132054. Lars Grasedyck. 2010. Hierarchical singular value decomposition of tensors. SIAM journal on matrix analysis and applications, 31, 4 (2010), 2029\u20132054."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256050740"},{"key":"e_1_3_2_1_58_1","article-title":"A review on generative adversarial networks: Algorithms, theory, and applications","author":"Gui Jie","year":"2021","unstructured":"Jie Gui , Zhenan Sun , Yonggang Wen , Dacheng Tao , and Jieping Ye . 2021 . A review on generative adversarial networks: Algorithms, theory, and applications . IEEE Transactions on Knowledge and Data Engineering. Jie Gui, Zhenan Sun, Yonggang Wen, Dacheng Tao, and Jieping Ye. 2021. A review on generative adversarial networks: Algorithms, theory, and applications. IEEE Transactions on Knowledge and Data Engineering.","journal-title":"IEEE Transactions on Knowledge and Data Engineering."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746579"},{"key":"e_1_3_2_1_60_1","first-page":"1","article-title":"Foundations of the PARAFAC procedure: Models and conditions for an\" explanatory\" multi-mode factor analysis","volume":"16","author":"RA","year":"1970","unstructured":"RA HARSHMAN. 1970 . Foundations of the PARAFAC procedure: Models and conditions for an\" explanatory\" multi-mode factor analysis . UCLA Working Papers in Phonetics , 16 (1970), 1 \u2013 84 . RA HARSHMAN. 1970. Foundations of the PARAFAC procedure: Models and conditions for an\" explanatory\" multi-mode factor analysis. UCLA Working Papers in Phonetics, 16 (1970), 1\u201384.","journal-title":"UCLA Working Papers in Phonetics"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168314"},{"key":"e_1_3_2_1_62_1","volume-title":"Statistical inference and the sum of squares method. Ph. D. Dissertation","author":"Hopkins Samuel","unstructured":"Samuel Hopkins . 2018. Statistical inference and the sum of squares method. Ph. D. Dissertation . Cornell University . Samuel Hopkins. 2018. Statistical inference and the sum of squares method. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_64_1","volume-title":"Conference on Learning Theory. 1683\u20131722","author":"Hopkins Samuel B","year":"2019","unstructured":"Samuel B Hopkins , Tselil Schramm , and Jonathan Shi . 2019 . A robust spectral algorithm for overcomplete tensor decomposition . In Conference on Learning Theory. 1683\u20131722 . Samuel B Hopkins, Tselil Schramm, and Jonathan Shi. 2019. A robust spectral algorithm for overcomplete tensor decomposition. In Conference on Learning Theory. 1683\u20131722."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_1_67_1","volume-title":"Independent component analysis. Studies in informatics and control, 11, 2","author":"Hyv\u00e4rinen Aapo","year":"2002","unstructured":"Aapo Hyv\u00e4rinen , Juha Karhunen , and Erkki Oja . 2002. Independent component analysis. Studies in informatics and control, 11, 2 ( 2002 ), 205\u2013207. Aapo Hyv\u00e4rinen, Juha Karhunen, and Erkki Oja. 2002. Independent component analysis. Studies in informatics and control, 11, 2 (2002), 205\u2013207."},{"key":"e_1_3_2_1_68_1","volume-title":"Unsupervised feature extraction by time-contrastive learning and nonlinear ica. Advances in Neural Information Processing Systems, 29","author":"Hyvarinen Aapo","year":"2016","unstructured":"Aapo Hyvarinen and Hiroshi Morioka . 2016. Unsupervised feature extraction by time-contrastive learning and nonlinear ica. Advances in Neural Information Processing Systems, 29 ( 2016 ). Aapo Hyvarinen and Hiroshi Morioka. 2016. Unsupervised feature extraction by time-contrastive learning and nonlinear ica. Advances in Neural Information Processing Systems, 29 (2016)."},{"key":"e_1_3_2_1_69_1","volume-title":"Independent component analysis: algorithms and applications. Neural networks, 13, 4-5","author":"Hyv\u00e4rinen Aapo","year":"2000","unstructured":"Aapo Hyv\u00e4rinen and Erkki Oja . 2000. Independent component analysis: algorithms and applications. Neural networks, 13, 4-5 ( 2000 ), 411\u2013430. Aapo Hyv\u00e4rinen and Erkki Oja. 2000. Independent component analysis: algorithms and applications. Neural networks, 13, 4-5 (2000), 411\u2013430."},{"key":"e_1_3_2_1_70_1","volume-title":"Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12, 3","author":"Hyv\u00e4rinen Aapo","year":"1999","unstructured":"Aapo Hyv\u00e4rinen and Petteri Pajunen . 1999. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12, 3 ( 1999 ), 429\u2013439. Aapo Hyv\u00e4rinen and Petteri Pajunen. 1999. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12, 3 (1999), 429\u2013439."},{"key":"e_1_3_2_1_71_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. 859\u2013868","author":"Hyvarinen Aapo","year":"2019","unstructured":"Aapo Hyvarinen , Hiroaki Sasaki , and Richard Turner . 2019 . Nonlinear ICA using auxiliary variables and generalized contrastive learning . In The 22nd International Conference on Artificial Intelligence and Statistics. 859\u2013868 . Aapo Hyvarinen, Hiroaki Sasaki, and Richard Turner. 2019. Nonlinear ICA using auxiliary variables and generalized contrastive learning. In The 22nd International Conference on Artificial Intelligence and Statistics. 859\u2013868."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316299"},{"key":"e_1_3_2_1_73_1","unstructured":"Samy Jelassi Arthur Mensch Gauthier Gidel and Yuanzhi Li. 2022. Adam is no better than normalized SGD: Dissecting how adaptivity improves GAN performance. https:\/\/openreview.net\/forum?id=D9SuLzhgK9 \t\t\t\t  Samy Jelassi Arthur Mensch Gauthier Gidel and Yuanzhi Li. 2022. Adam is no better than normalized SGD: Dissecting how adaptivity improves GAN performance. https:\/\/openreview.net\/forum?id=D9SuLzhgK9"},{"key":"e_1_3_2_1_74_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 2207\u20132217","author":"Khemakhem Ilyes","year":"2020","unstructured":"Ilyes Khemakhem , Diederik Kingma , Ricardo Monti , and Aapo Hyvarinen . 2020 . Variational autoencoders and nonlinear ica: A unifying framework . In International Conference on Artificial Intelligence and Statistics. 2207\u20132217 . Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. 2020. Variational autoencoders and nonlinear ica: A unifying framework. In International Conference on Artificial Intelligence and Statistics. 2207\u20132217."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1154382"},{"key":"e_1_3_2_1_76_1","unstructured":"Diederik P Kingma and Max Welling. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114. \t\t\t\t  Diederik P Kingma and Max Welling. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_1_80_1","volume-title":"Equations for secant varieties of Veronese and other varieties. Annali di Matematica Pura ed Applicata, 192, 4","author":"Landsberg Joseph M","year":"2013","unstructured":"Joseph M Landsberg and Giorgio Ottaviani . 2013. Equations for secant varieties of Veronese and other varieties. Annali di Matematica Pura ed Applicata, 192, 4 ( 2013 ), 569\u2013606. Joseph M Landsberg and Giorgio Ottaviani. 2013. Equations for secant varieties of Veronese and other varieties. Annali di Matematica Pura ed Applicata, 192, 4 (2013), 569\u2013606."},{"key":"e_1_3_2_1_81_1","volume-title":"International Conference on Machine Learning. 5799\u20135808","author":"Lei Qi","year":"2020","unstructured":"Qi Lei , Jason Lee , Alex Dimakis , and Constantinos Daskalakis . 2020 . SGD learns one-layer networks in wgans . In International Conference on Machine Learning. 5799\u20135808 . Qi Lei, Jason Lee, Alex Dimakis, and Constantinos Daskalakis. 2020. SGD learns one-layer networks in wgans. In International Conference on Machine Learning. 5799\u20135808."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1137\/0614071"},{"key":"e_1_3_2_1_83_1","unstructured":"Yuanzhi Li and Zehao Dou. 2020. Making Method of Moments Great Again?\u2013How can GANs learn distributions. arXiv preprint arXiv:2003.04033. \t\t\t\t  Yuanzhi Li and Zehao Dou. 2020. Making Method of Moments Great Again?\u2013How can GANs learn distributions. arXiv preprint arXiv:2003.04033."},{"key":"e_1_3_2_1_84_1","volume-title":"International Conference on Machine Learning. 2062\u20132070","author":"Li Yuanzhi","year":"2017","unstructured":"Yuanzhi Li and Yingyu Liang . 2017 . Provable alternating gradient descent for non-negative matrix factorization with strong correlations . In International Conference on Machine Learning. 2062\u20132070 . Yuanzhi Li and Yingyu Liang. 2017. Provable alternating gradient descent for non-negative matrix factorization with strong correlations. In International Conference on Machine Learning. 2062\u20132070."},{"key":"e_1_3_2_1_85_1","unstructured":"Tengyuan Liang. 2018. How well generative adversarial networks learn distributions. arXiv preprint arXiv:1811.03179. \t\t\t\t  Tengyuan Liang. 2018. How well generative adversarial networks learn distributions. arXiv preprint arXiv:1811.03179."},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.54"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax001"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_89_1","volume-title":"International Conference on Machine Learning. 811\u2013819","author":"Novikov Alexander","year":"2014","unstructured":"Alexander Novikov , Anton Rodomanov , Anton Osokin , and Dmitry Vetrov . 2014 . Putting MRFs on a tensor train . In International Conference on Machine Learning. 811\u2013819 . Alexander Novikov, Anton Rodomanov, Anton Osokin, and Dmitry Vetrov. 2014. Putting MRFs on a tensor train. In International Conference on Machine Learning. 811\u2013819."},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.07.024"},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1137\/090752286"},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1058686"},{"key":"e_1_3_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.17"},{"key":"e_1_3_2_1_94_1","volume-title":"Conference on Learning Theory. 1402\u20131416","author":"Risteski Andrej","year":"2016","unstructured":"Andrej Risteski . 2016 . How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods . In Conference on Learning Theory. 1402\u20131416 . Andrej Risteski. 2016. How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods. In Conference on Learning Theory. 1402\u20131416."},{"key":"e_1_3_2_1_95_1","unstructured":"Nicolas Schreuder Victor-Emmanuel Brunel and Arnak Dalalyan. 2021. Statistical guarantees for generative models without domination. In Algorithmic Learning Theory. 1051\u20131071. \t\t\t\t  Nicolas Schreuder Victor-Emmanuel Brunel and Arnak Dalalyan. 2021. Statistical guarantees for generative models without domination. In Algorithmic Learning Theory. 1051\u20131071."},{"key":"e_1_3_2_1_96_1","unstructured":"Shashank Singh Ananya Uppal Boyue Li Chun-Liang Li Manzil Zaheer and Barnab\u00e1s P\u00f3czos. 2018. Nonparametric Density Estimation under Adversarial Losses. In NeurIPS. \t\t\t\t  Shashank Singh Ananya Uppal Boyue Li Chun-Liang Li Manzil Zaheer and Barnab\u00e1s P\u00f3czos. 2018. Nonparametric Density Estimation under Adversarial Losses. In NeurIPS."},{"key":"e_1_3_2_1_97_1","volume-title":"Lisa Maria Kreusser, and Carola-Bibiane Sch\u00f6nlieb","author":"Stanczuk Jan","year":"2021","unstructured":"Jan Stanczuk , Christian Etmann , Lisa Maria Kreusser, and Carola-Bibiane Sch\u00f6nlieb . 2021 . Wasserstein GANs work because they fail (to approximate the Wasserstein distance). arXiv preprint arXiv:2103.01678. Jan Stanczuk, Christian Etmann, Lisa Maria Kreusser, and Carola-Bibiane Sch\u00f6nlieb. 2021. Wasserstein GANs work because they fail (to approximate the Wasserstein distance). arXiv preprint arXiv:2103.01678."},{"key":"e_1_3_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2632162"},{"key":"e_1_3_2_1_99_1","first-page":"9089","article-title":"Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses","volume":"32","author":"Uppal Ananya","year":"2019","unstructured":"Ananya Uppal , Shashank Singh , and Barnabas Poczos . 2019 . Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses . Advances in Neural Information Processing Systems , 32 (2019), 9089 \u2013 9100 . Ananya Uppal, Shashank Singh, and Barnabas Poczos. 2019. Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses. Advances in Neural Information Processing Systems, 32 (2019), 9089\u20139100.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"},{"key":"e_1_3_2_1_101_1","volume-title":"Density matrix renormalization group and periodic boundary conditions: A quantum information perspective. Physical review letters, 93, 22","author":"Verstraete Frank","year":"2004","unstructured":"Frank Verstraete , Diego Porras , and J Ignacio Cirac . 2004. Density matrix renormalization group and periodic boundary conditions: A quantum information perspective. Physical review letters, 93, 22 ( 2004 ), 227205. Frank Verstraete, Diego Porras, and J Ignacio Cirac. 2004. Density matrix renormalization group and periodic boundary conditions: A quantum information perspective. Physical review letters, 93, 22 (2004), 227205."},{"key":"e_1_3_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1287\/12-SSY073"},{"key":"e_1_3_2_1_103_1","volume-title":"Learning distributions generated by one-layer ReLU networks. Advances in neural information processing systems, 32","author":"Wu Shanshan","year":"2019","unstructured":"Shanshan Wu , Alexandros G Dimakis , and Sujay Sanghavi . 2019. Learning distributions generated by one-layer ReLU networks. Advances in neural information processing systems, 32 ( 2019 ). Shanshan Wu, Alexandros G Dimakis, and Sujay Sanghavi. 2019. Learning distributions generated by one-layer ReLU networks. Advances in neural information processing systems, 32 (2019)."},{"key":"e_1_3_2_1_104_1","volume-title":"Sparse logistic regression learns all discrete pairwise graphical models. Advances in Neural Information Processing Systems, 32","author":"Wu Shanshan","year":"2019","unstructured":"Shanshan Wu , Sujay Sanghavi , and Alexandros G Dimakis . 2019. Sparse logistic regression learns all discrete pairwise graphical models. Advances in Neural Information Processing Systems, 32 ( 2019 ). Shanshan Wu, Sujay Sanghavi, and Alexandros G Dimakis. 2019. Sparse logistic regression learns all discrete pairwise graphical models. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_105_1","unstructured":"Ke Ye and Lek-Heng Lim. 2018. Tensor network ranks. arXiv preprint arXiv:1801.02662. \t\t\t\t  Ke Ye and Lek-Heng Lim. 2018. Tensor network ranks. arXiv preprint arXiv:1801.02662."},{"key":"e_1_3_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2841377"},{"key":"e_1_3_2_1_107_1","unstructured":"Qibin Zhao Guoxu Zhou Shengli Xie Liqing Zhang and Andrzej Cichocki. 2016. Tensor ring decomposition. arXiv preprint arXiv:1606.05535. \t\t\t\t  Qibin Zhao Guoxu Zhou Shengli Xie Liqing Zhang and Andrzej Cichocki. 2016. Tensor ring decomposition. arXiv preprint arXiv:1606.05535."},{"key":"e_1_3_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3152733"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585209","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:01Z","timestamp":1750178821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":108,"alternative-id":["10.1145\/3564246.3585209","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585209","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}