{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005541,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718223","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1762-1773","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Omnipredicting Single-Index Models with Multi-index Models"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-6800","authenticated-orcid":false,"given":"Lunjia","family":"Hu","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0109-9201","authenticated-orcid":false,"given":"Kevin","family":"Tian","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4614-323X","authenticated-orcid":false,"given":"Chutong","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728423"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580873"},{"key":"e_1_3_2_1_3_1","unstructured":"Niko Brummer and Johan du Preez. 2013. The PAV algorithm optimizes binary proper scoring rules. arXiv preprint arXiv:1304.2331."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1442786"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.) (Proceedings of Machine Learning Research","volume":"8213","author":"Diakonikolas Ilias","year":"2022","unstructured":"Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. 2022. Hardness of Learning a Single Neuron with Adversarial Label Noise. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.) (Proceedings of Machine Learning Research, Vol. 151). PMLR, 8199\u20138213. https:\/\/proceedings.mlr.press\/v151\/diakonikolas22a.html"},{"key":"e_1_3_2_1_8_1","unstructured":"Ilias Diakonikolas Daniel Kane and Lisheng Ren. 2023. Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. In Proceedings of the 40th International Conference on Machine Learning Andreas Krause Emma Brunskill Kyunghyun Cho Barbara Engelhardt Sivan Sabato and Jonathan Scarlett (Eds.) (Proceedings of Machine Learning Research Vol. 202). PMLR 7922\u20137938. https:\/\/proceedings.mlr.press\/v202\/diakonikolas23b.html"},{"volume-title":"To appear in FOCS 2024","author":"Diakonikolas Ilias","key":"e_1_3_2_1_9_1","unstructured":"Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2023. Agnostically Learning Multi-index Models with Queries. arXiv preprint arXiv:2312.16616, To appear in FOCS 2024"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 31st Conference On Learning Theory, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research","volume":"1930","author":"Dudeja Rishabh","year":"2018","unstructured":"Rishabh Dudeja and Daniel Hsu. 2018. Learning Single-Index Models in Gaussian Space. In Proceedings of the 31st Conference On Learning Theory, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research, Vol. 75). PMLR, 1887\u20131930. https:\/\/proceedings.mlr.press\/v75\/dudeja18a.html"},{"key":"e_1_3_2_1_11_1","unstructured":"Cynthia Dwork Chris Hays Nicole Immorlica Juan C. Perdomo and Pranay Tankala. 2024. From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs. Personal communication"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451064"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"V. Feldman P. Gopalan S. Khot and A. K. Ponnuswami. 2006. New Results for Learning Noisy Parities and Halfspaces. In 47 th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society 563\u2013574.","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"1754","author":"Gajjar Aarshvi","year":"2024","unstructured":"Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco, and Yi Li. 2024. Agnostic Active Learning of Single Index Models with Linear Sample Complexity. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 1715\u20131754. https:\/\/proceedings.mlr.press\/v247\/gajjar24a.html"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.98"},{"key":"e_1_3_2_1_16_1","volume-title":"Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems","author":"Gollakota Aravind","year":"2023","unstructured":"Aravind Gollakota, Parikshit Gopalan, Adam R. Klivans, and Konstantinos Stavropoulos. 2023. Agnostically Learning Single-Index Models using Omnipredictors. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023."},{"volume-title":"14th Innovations in Theoretical Computer Science Conference (ITCS 2023) (Leibniz International Proceedings in Informatics (LIPIcs)). 60:1\u201360:20. isbn:978-3-95977-263-1 issn:1868-8969","author":"Gopalan Parikshit","key":"e_1_3_2_1_17_1","unstructured":"Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. 2023. Loss Minimization Through the Lens Of Outcome Indistinguishability. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) (Leibniz International Proceedings in Informatics (LIPIcs)). 60:1\u201360:20. isbn:978-3-95977-263-1 issn:1868-8969"},{"key":"e_1_3_2_1_18_1","volume-title":"Omnipredictors. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 (LIPIcs","volume":"21","author":"Gopalan Parikshit","year":"2022","unstructured":"Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. 2022. Omnipredictors. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 79:1\u201379:21."},{"key":"e_1_3_2_1_19_1","volume-title":"Advances in Neural Information Processing Systems","author":"Gopalan Parikshit","year":"2023","unstructured":"Parikshit Gopalan, Michael Kim, and Omer Reingold. 2023. Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.). 36, Curran Associates, Inc., 39936\u201339956. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/7d693203215325902ff9dbdd067a50ac-Paper-Conference.pdf"},{"key":"e_1_3_2_1_20_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"2070","author":"Gopalan Parikshit","year":"2024","unstructured":"Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, and Mihir Singhal. 2024. Omnipredictors for regression and the approximate rank of convex functions. In The Thirty Seventh Annual Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 247). PMLR, 2027\u20132070."},{"key":"e_1_3_2_1_21_1","volume-title":"Projections onto order simplexes. Applied mathematics and Optimization, 12, 1","author":"Grotzinger Stephen J","year":"1984","unstructured":"Stephen J Grotzinger and Christoph Witzgall. 1984. Projections onto order simplexes. Applied mathematics and Optimization, 12, 1 (1984), 247\u2013270."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.33"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research","volume":"1948","author":"Hebert-Johnson Ursula","year":"2018","unstructured":"Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. 2018. Multicalibration: Calibration for the (Computationally-Identifiable) Masses. In Proceedings of the 35th International Conference on Machine Learning, Jennifer Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research, Vol. 80). PMLR, 1939\u20131948. https:\/\/proceedings.mlr.press\/v80\/hebert-johnson18a.html"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1009210682"},{"key":"e_1_3_2_1_25_1","volume-title":"Testing Calibration in Nearly-Linear Time. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems","author":"Hu Lunjia","year":"2024","unstructured":"Lunjia Hu, Arun Jambulapati, Kevin Tian, and Chutong Yang. 2024. Testing Calibration in Nearly-Linear Time. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024."},{"key":"e_1_3_2_1_26_1","volume-title":"Omer Reingold, and Chutong Yang.","author":"Hu Lunjia","year":"2023","unstructured":"Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, and Chutong Yang. 2023. Omnipredictors for Constrained Optimization. In Proceedings of the 40th International Conference on Machine Learning, Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.) (Proceedings of Machine Learning Research, Vol. 202). PMLR, 13497\u201313527. https:\/\/proceedings.mlr.press\/v202\/hu23b.html"},{"key":"e_1_3_2_1_27_1","unstructured":"Lunjia Hu Kevin Tian and Chutong Yang. 2024. Omnipredicting Single-Index Models with Multi-Index Models. arXiv preprint arXiv:2411.13083."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4076(93)90114-K"},{"key":"e_1_3_2_1_29_1","volume-title":"Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems","author":"Kakade Sham M.","year":"2011","unstructured":"Sham M. Kakade, Adam Kalai, Varun Kanade, and Ohad Shamir. 2011. Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. 927\u2013935."},{"key":"e_1_3_2_1_30_1","volume-title":"The Isotron Algorithm: High-Dimensional Isotonic Regression. In COLT 2009 - The 22nd Conference on Learning Theory.","author":"Kalai Adam Tauman","year":"2009","unstructured":"Adam Tauman Kalai and Ravi Sastry. 2009. The Isotron Algorithm: High-Dimensional Isotonic Regression. In COLT 2009 - The 22nd Conference on Learning Theory."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306618.3314287"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.79"},{"key":"e_1_3_2_1_33_1","volume-title":"The Computational Complexity of Training ReLU(s). CoRR, abs\/1810.04207","author":"Manurangsi Pasin","year":"2018","unstructured":"Pasin Manurangsi and Daniel Reichman. 2018. The Computational Complexity of Training ReLU(s). CoRR, abs\/1810.04207 (2018)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/2344614"},{"key":"e_1_3_2_1_35_1","volume-title":"High-Dimensional Unbiased Prediction for Sequential Decision Making. In OPT 2023: Optimization for Machine Learning. https:\/\/openreview.net\/forum?id=P4j4l45NUq","author":"Noarov Georgy","year":"2023","unstructured":"Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. 2023. High-Dimensional Unbiased Prediction for Sequential Decision Making. In OPT 2023: Optimization for Machine Learning. https:\/\/openreview.net\/forum?id=P4j4l45NUq"},{"key":"e_1_3_2_1_36_1","volume-title":"Kim","author":"Okoroafor Princewill","year":"2024","unstructured":"Princewill Okoroafor, Robert Kleinberg, and Michael P. Kim. 2024. Near-Optimal Algorithms for Omniprediction. Personal communication"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912110"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976602760408035"},{"key":"e_1_3_2_1_39_1","volume-title":"Forty-first International Conference on Machine Learning, ICML 2024","author":"Zarifis Nikos","year":"2024","unstructured":"Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. 2024. Robustly Learning Single-Index Models via Alignment Sharpness. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:38Z","timestamp":1750693478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":39,"alternative-id":["10.1145\/3717823.3718223","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718223","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}