{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T12:35:55Z","timestamp":1793277355772,"version":"4.5.0"},"reference-count":93,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2107079"],"award-info":[{"award-number":["CCF-2107079"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2144298"],"award-info":[{"award-number":["CCF-2144298"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF1652862"],"award-info":[{"award-number":["CCF1652862"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2107547"],"award-info":[{"award-number":["CCF-2107547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1553288"],"award-info":[{"award-number":["CCF-1553288"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the power of query access for the fundamental task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels of the examples,\u00a0and the goal is to compute a hypothesis that is competitive with the best-fit function in a known class;\u00a0i.e., it achieves error [Formula: see text], where [Formula: see text] is the error of the best function in the class. We focus on a general family of multi-Index models (MIMs), which are [Formula: see text]-variate functions that depend only on a few relevant directions, i.e., have the form [Formula: see text] for an unknown link function [Formula: see text] and a [Formula: see text] matrix [Formula: see text]. MIMs cover a wide range of commonly studied function classes, including real-valued function classes,\u00a0such as constant-depth neural networks with ReLU activations, and Boolean concept classes,\u00a0such as intersections of halfspaces. Our main result shows that query access gives significant runtime improvements over random examples for agnostically learning both real-valued and Boolean-valued MIMs. Under standard regularity assumptions for the link function (namely, bounded variation or surface area), we give an agnostic query learner for MIMs with running time [Formula: see text]. In contrast, algorithms that rely only on random labeled examples inherently require [Formula: see text] samples and runtime, even for the basic problem of agnostically learning a single ReLU or a halfspace. As special cases of our general approach, we obtain the following results: [Formula: see text] For the class of depth-[Formula: see text], width-[Formula: see text] ReLU networks on [Formula: see text], our agnostic query learner runs in time [Formula: see text]. This bound qualitatively matches the runtime of an algorithm by Chen, Klivans, and Meka [ Learning deep ReLU networks is fixed-parameter tractable, 2022] for the realizable PAC setting with random examples. [Formula: see text] For the class of arbitrary intersections of [Formula: see text] halfspaces on [Formula: see text], our agnostic query learner runs in time [Formula: see text]. Prior to our work, no improvement over the agnostic PAC model complexity (without queries) was known, even for the case of a single halfspace. In both these settings, we provide evidence that the [Formula: see text] runtime dependence is required for proper query learners, even for agnostically learning a single ReLU or halfspace. Our algorithmic result establishes a strong computational separation between the agnostic PAC and the agnostic PAC\u00a0+\u00a0Query models under the Gaussian distribution for a range of natural function classes. Prior to our work, no such separation was known for any natural concept class, even for the case of a single halfspace, for which it was an open problem posed by Feldman [ On the power of membership queries in agnostic learning, 2008]. Our results are enabled by a general dimension-reduction technique that leverages query access to estimate gradients of (a smoothed version of) the underlying label function.<\/jats:p>","DOI":"10.1137\/24m1718135","type":"journal-article","created":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T08:00:52Z","timestamp":1783929652000},"page":"FOCS24-435-FOCS24-486","source":"Crossref","is-referenced-by-count":0,"title":["Agnostically Learning Multi-Index Models with Queries"],"prefix":"10.1137","volume":"55","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI 53706 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Kane","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of California San Diego, San Diego, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vasilis","family":"Kontonis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Austin, Austin, TX 78712 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[{"name":"Department of Informatics and Telecommunications, University of Athens, Athens, GR-16122, Greece."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikos","family":"Zarifis","sequence":"additional","affiliation":[{"name":"Computer Science & Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,13]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"R. Arriaga and S. Vempala, An algorithmic theory of learning: Robust concepts and random projection, in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, New York, 1999, pp. 616\u2013623.","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"ref3","unstructured":"A. Bakshi, R. Jayaram, and D. P. Woodruff, Learning two layer rectified neural networks in polynomial time, in Proceedings of the 32nd Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 99, PMLR, 2019, pp. 195\u2013268."},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"B. Barak, F. G. S. L. Brand\u00e3o, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou, Hypercontractivity, sum-of-squares proofs, and their applications, in STOC \u201912: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 307\u2013326, https:\/\/doi.org\/10.1145\/2213977.","DOI":"10.1145\/2213977.2214006"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0710"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3561047"},{"key":"ref7","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/062","volume":"62","author":"Bogachev V.","year":"1998","journal-title":"Math, Surveys Monogr."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2399924"},{"key":"ref9","unstructured":"S. Chen, Z. Dou, S. Goel, A. R. Klivans, and R. Meka, Learning narrow one-hidden-layer ReLU networks, in Proceedings of the 36th Conference on Learning Theory, Proceedings of Machine Learning Research 195, PMLR, 2023, pp. 5580\u20135614, 2023, https:\/\/proceedings.mlr.press\/v195\/chen23a.html."},{"key":"ref10","unstructured":"S. Chen, A. R. Klivans, and R. Meka, Efficiently learning one hidden layer ReLU networks from queries, in Advances in Neural Information Processing Systems 34 (NeurIPS 2021), 2021, pp. 24087\u201324098."},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"S. Chen, A. R. Klivans, and R. Meka, Learning deep ReLU networks is fixed-parameter tractable, in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, New York, 2022, pp. 696\u2013707.","DOI":"10.1109\/FOCS52979.2021.00073"},{"key":"ref12","unstructured":"S. Chen and R. Meka, Learning polynomials in few relevant dimensions, in Proceedings of the 32nd Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 125, PMLR, 2020, pp. 1161\u20131227, http:\/\/proceedings.mlr.press\/v125\/chen20a.html."},{"key":"ref13","unstructured":"S. Chen and S. Narayanan, A faster and simpler algorithm for learning shallow networks,\u00a0Proceedings of Thirty Seventh Conference on Learning Theory,\u00a0PMLR 247,\u00a02024, pp. 981\u2013994, https:\/\/proceedings.mlr.press\/v247\/chen24b.html."},{"key":"ref14","unstructured":"V. Chernozhukov, D. Chetverikov, and K. Kato, Detailed Proof of Nazarov\u2019s Inequality, preprint, https:\/\/arxiv.org\/abs\/1711.10696, 2017."},{"key":"ref15","first-page":"1647","volume":"9","author":"Dalalyan A. S.","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"ref16","unstructured":"A. Damian, J. Lee, and M. Soltanolkotabi, Neural networks can learn representations with gradient descent, in Proceedings of the 35th Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 125, PMLR, 2022, pp. 5413\u20135452."},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"A. Daniely, Complexity theoretic limitations on learning halfspaces, in STOC \u201916: Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, New York, 2016, pp. 105\u2013117.","DOI":"10.1145\/2897518.2897520"},{"key":"ref18","unstructured":"A. Daniely and E. Granot, An exact poly-time membership-queries algorithm for extracting a three-layer ReLU network, in 11th International Conference on Learning Representations (ICLR 2023), 2023."},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"A. De, E. Mossel, and J. Neeman, Robust testing of low dimensional functions, in STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2021, pp. 584\u2013597.","DOI":"10.1145\/3406325.3451115"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, P. Harsha, A. Klivans, R. Meka, P. Raghavendra, R. A. Servedio, and L. Y. Tan, Bounding the average sensitivity and noise sensitivity of polynomial threshold functions, in STOC \u201910: Proceedings of the 42nd ACM Symposium on Theory of Computing, ACM, New York, 2010, pp. 533\u2013542.","DOI":"10.1145\/1806689.1806763"},{"key":"ref21","unstructured":"I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren, Hardness of learning a single neuron with adversarial label noise, in Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research 151, PMLR, 2022, pp. 8199\u20138213."},{"key":"ref22","unstructured":"I. Diakonikolas and D. M. Kane, Efficiently learning one-hidden-layer ReLU networks via Schur polynomials, in Proceedings of Thirty Seventh Conference on Learning Theory,\u00a0PMLR 247,\u00a02024, pp. 1364\u20131378, https:\/\/proceedings.mlr.press\/v247\/diakonikolas24c.html."},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas and D. M. Kane, Small covers for near-zero sets of polynomials and learning latent variable models, in 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, New York, 2020, pp. 184\u2013195.","DOI":"10.1109\/FOCS46700.2020.00026"},{"key":"ref24","unstructured":"I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis, Agnostic proper learning of halfspaces under Gaussian marginals, in Proceedings of the 34th Conference on Learning Theory, Proceedings of Machine Learning Research 134, PMLR, 2021, pp. 1522\u20131551."},{"key":"ref25","unstructured":"I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis, Algorithms and SQ lower bounds for PAC learning one-hidden-layer ReLU networks, in Proceedings of the 33rd Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 125, PMLR, 2020, pp. 1514\u20131539."},{"key":"ref26","unstructured":"I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren, Cryptographic hardness of learning halfspaces with Massart noise, in NIPS\u201922: Proceedings of the 36th International Conference on Neural Information Processing Systems, https:\/\/dl.acm.org\/doi\/10.5555\/3600270.3600532."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, D. M. Kane, and J. Nelson, Bounded independence fools degree-2 threshold functions, in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, IEEE, New York, 2010, pp. 11\u201320.","DOI":"10.1109\/FOCS.2010.8"},{"key":"ref28","unstructured":"I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis, The optimality of polynomial regression for agnostic learning under Gaussian marginals in the SQ model, in Proceedings of the 34th Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 134, PMLR, 2021, pp. 1552\u20131584."},{"key":"ref29","unstructured":"I. Diakonikolas, D. M. Kane, and L. Ren, Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginals, in Proceedings of the 40th International Conference on Machine Learning,\u00a0PMLR 202,\u00a02023, pp. 7922\u20137938, https:\/\/proceedings.mlr.press\/v202\/diakonikolas23b.html."},{"key":"ref30","first-page":"13586","volume-title":"Advances in Neural Information Processing Systems 33 (NeurIPS 2020)","author":"Diakonikolas I.","year":"2020"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/110855223"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.28"},{"key":"ref33","unstructured":"R. Dudeja and D. Hsu, Learning single-index models in gaussian space, in Proceedings of the 31st Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 75, PMLR, 2018, pp. 1887\u20131930, http:\/\/proceedings.mlr.press\/v75\/dudeja18a.html."},{"key":"ref34","unstructured":"V. Feldman, On the power of membership queries in agnostic learning, in 21st Annual Conference on Learning Theory (COLT 2008), ACM, New York, 2008, pp. 147\u2013156, http:\/\/colt2008.cs.helsinki.fi\/papers\/129-Feldman.pdf."},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1981.10477729"},{"key":"ref36","unstructured":"R. Ge, R. Kuditipudi, Z. Li, and X. Wang, Learning two-layer neural networks with symmetric inputs, in Seventh International Conference on Learning Representations (ICLR 2019), 2019."},{"key":"ref37","unstructured":"R. Ge, J. D. Lee, and T. Ma, Learning one-hidden-layer neural networks with landscape design, in Sixth International Conference on Learning Representations (ICLR 2018), 2018."},{"key":"ref38","first-page":"2147","volume-title":"Advances in Neural Information Processing Systems 33 (NeurIPS 2020)","author":"Goel S.","year":"2020"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin, A hard-core predicate for all one-way functions, in STOC \u201989: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 25\u201332.","DOI":"10.1145\/73007.73010"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos, Agnostically learning single-index models using omnipredictors, in 37th Conference on Neural Information Processing Systems (NeurIPS 2023), 2023, pp. 14685\u201314704.","DOI":"10.52202\/075280-0646"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"P. Gopalan, A. Kalai, and A. Klivans, Agnostically learning decision trees, in STOC \u201908: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, New York, 2008, pp. 527\u2013536.","DOI":"10.1145\/1374376.1374451"},{"key":"ref42","unstructured":"P. Gopalan, A. Kalai, and A. R. Klivans, A query algorithm for agnostically learning DNF? in 21st Annual Conference on Learning Theory (COLT 2008), ACM, New York, 2008, pp. 515\u2013516, http:\/\/colt2008.cs.helsinki.fi\/papers\/Gopalan-open-question.pdf."},{"key":"ref43","unstructured":"S. Gopi, P. Netrapalli, P. Jain, and A. Nori, One-bit compressed sensing: Provable support and vector recovery, in Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research 28, PMLR, 2013, pp. 154\u2013162."},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349155"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17146-8"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1009210682"},{"key":"ref48","unstructured":"D. J. Hsu, C. Sanford, R. A. Servedio, and E. Vlatakis-Gkaragkounis, Near-optimal statistical query lower bounds for agnostically learning intersections of halfspaces with Gaussian marginals, in Proceedings of the 35th Conference on Learning Theory,\u00a0Proceedings of Machine Learning Research 178, PMLR, 2022, pp. 283\u2013312."},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349519"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4076(93)90114-K"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"ref52","unstructured":"M. Jagielski, N. Carlini, D. Berthelot, A. Kurakin, and N. Papernot, High accuracy and high fidelity extraction of neural networks, in 29th USENIX Security Symposium, USENIX Security 2020, USENIX Association, San Francisco, CA, 2020, pp. 1345\u20131362."},{"key":"ref53","unstructured":"M. Janzamin, H. Sedghi, and A. Anandkumar, Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks Using Tensor Methods, preprint, arXiv:1506.08473, 2015."},{"key":"ref54","unstructured":"R. Jayaram, D. Woodruff, and Q. Zhang, Span recovery for deep neural networks with applications to input obfuscation, in Eighth International Conference on Learning Representations (ICLR 2020), 2020."},{"key":"ref55","author":"Kakade S. M.","year":"2011","journal-title":"Advances in Neural Information Processing Systems 24 (NIPS 2011)"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"ref57","volume-title":"22nd Conference on Learning Theory (COLT 2009)","author":"Kalai A. T.","year":"2009"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0012-6"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022615600103"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"ref61","doi-asserted-by":"crossref","unstructured":"A. Klivans, R. O\u2019Donnell, and R. Servedio, Learning geometric concepts via Gaussian surface area, in FOCS \u201908: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, New York, 2008, pp. 541\u2013550.","DOI":"10.1109\/FOCS.2008.64"},{"key":"ref62","doi-asserted-by":"crossref","unstructured":"A. R. Klivans, P. M. Long, and A. K. Tang, Baum\u2019s algorithm learns intersections of halfspaces with respect to log-concave distributions, in APPROX \u201909\/RANDOM \u201909: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, ACM, New York, 2009, pp. 588\u2013600.","DOI":"10.1007\/978-3-642-03685-9_44"},{"key":"ref63","doi-asserted-by":"crossref","unstructured":"V. Kontonis, C. Tzamos, and M. Zampetakis, Efficient truncated statistics with unknown truncation, in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, IEEE, New York, 2019, pp. 1578\u20131595.","DOI":"10.1109\/FOCS.2019.00093"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"ref65","first-page":"485","volume":"118","author":"Ledoux M.","year":"1994","journal-title":"Bull. Sci. Math."},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1991.10475035"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1145\/3287560.3287562"},{"key":"ref68","first-page":"2481","volume":"7","author":"Mukherjee S.","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"ref69","first-page":"519","volume":"7","author":"Mukherjee S.","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"ref70","doi-asserted-by":"crossref","unstructured":"J. Neeman, Testing surface area with arbitrary accuracy, in STOC \u201914: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 393\u2013397, https:\/\/doi.org\/10.1145\/2591796.","DOI":"10.1145\/2591796.2591807"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9296-2"},{"key":"ref72","unstructured":"P. Netrapalli, P. Jain, and S. Sanghavi, Phase retrieval using alternating minimization, in NIPS\u201913: Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, 2013, pp. 2796\u20132804, https:\/\/dl.acm.org\/doi\/10.5555\/2999792.2999924."},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"ref74","doi-asserted-by":"crossref","unstructured":"N. Papernot, P. D. McDaniel, I. J. Goodfellow, S. Jha, Z. B. Celik, and A. Swami, Practical black-box attacks against machine learning, in Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS 2017, 2017, pp. 506\u2013519, https:\/\/doi.org\/10.1145\/3052973.","DOI":"10.1145\/3052973.3053009"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076302"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21442"},{"key":"ref77","doi-asserted-by":"crossref","unstructured":"P. Raghavendra and D. Steurer, Graph expansion and the unique games conjecture, in Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), ACM, New York, 2010, pp. 755\u2013764, https:\/\/doi.org\/10.1145\/1806689.","DOI":"10.1145\/1806689.1806792"},{"key":"ref78","unstructured":"D. Rolnick and K. P. Kording, Reverse-engineering deep ReLU networks, in Proceedings of the 37th International Conference on Machine Learning,\u00a0Proceedings of Machine Learning Research 119, PMLR, 2020, pp. 8178\u20138187."},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1037\/h0042519"},{"key":"ref80","doi-asserted-by":"crossref","unstructured":"Y. Shi, Y. Sagduyu, and A. Grushin, How to steal a machine learning classifier with deep learning, in 2017 IEEE International Symposium on Technologies for Homeland Security (HST), IEEE, New York, 2017, pp. 1\u20135.","DOI":"10.1109\/THS.2017.7943475"},{"key":"ref81","unstructured":"S. Tiegel, Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems, proceedings of Thirty Sixth Conference on Learning Theory,\u00a0PMLR 195:3029\u20133064,\u00a02023 https:\/\/proceedings.mlr.press\/v195\/tiegel23a.html."},{"key":"ref82","unstructured":"F. Tram\u00e8r, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart, Stealing machine learning models via prediction APIs, in 25th USENIX Security Symposium, USENIX Security 16, USENIX Association, San Francisco, CA, 2016, pp. 601\u2013618."},{"key":"ref83","volume-title":"Introduction to Nonparametric Estimation","author":"Tsybakov A. B.","year":"2008"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"ref85","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, A theory of the learnable, in STOC \u201984: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, ACM, New York, 1984, pp. 436\u2013445.","DOI":"10.1145\/800057.808710"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857916"},{"key":"ref87","doi-asserted-by":"crossref","unstructured":"S. Vempala, A random sampling based algorithm for learning the intersection of halfspaces, in FOCS \u201997: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, New York, 1997, pp. 508\u2013513.","DOI":"10.1109\/SFCS.1997.646139"},{"key":"ref88","doi-asserted-by":"crossref","unstructured":"S. Vempala, Learning convex concepts from Gaussian distributions with PCA, in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, IEEE, New York, 2010, pp. 124\u2013130.","DOI":"10.1109\/FOCS.2010.19"},{"key":"ref89","unstructured":"S. Vempala and Y. Xiao, Structure from local optima: Learning subspace juntas via higher order PCA, in STOC \u201912: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, ACM, New York, 2012."},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref91","first-page":"2175","volume":"11","author":"Wu Q.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1198\/016214508000000805"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.03411"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1718135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T12:07:54Z","timestamp":1793275674000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1718135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,13]]},"references-count":93,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,10,31]]}},"alternative-id":["10.1137\/24M1718135"],"URL":"https:\/\/doi.org\/10.1137\/24m1718135","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,13]]}}}