{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T03:49:18Z","timestamp":1775706558889,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T00:00:00Z","timestamp":1745884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T00:00:00Z","timestamp":1745884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-PI3A0004"],"award-info":[{"award-number":["ANR-19-PI3A0004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-EURE-0010"],"award-info":[{"award-number":["ANR-17-EURE-0010"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-23-CE23-0012-01"],"award-info":[{"award-number":["ANR-23-CE23-0012-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006394","name":"Air Force Materiel Command","doi-asserted-by":"publisher","award":["FA8655-22-1-7012"],"award-info":[{"award-number":["FA8655-22-1-7012"]}],"id":[{"id":"10.13039\/100006394","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1007\/s10107-025-02229-w","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T00:53:47Z","timestamp":1745888027000},"page":"539-574","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Geometric and computational hardness of bilevel programming"],"prefix":"10.1007","volume":"215","author":[{"given":"J\u00e9r\u00f4me","family":"Bolte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9952-2194","authenticated-orcid":false,"given":"Qu\u1ed1c-T\u00f9ng","family":"L\u00ea","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edouard","family":"Pauwels","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Vaiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,29]]},"reference":[{"key":"2229_CR1","unstructured":"Ablin, P., Peyr\u00e9, G., Moreau, T.: Super-efficiency of automatic differentiation for functions defined as a minimum. In: Proceedings of the 37th International Conference on Machine Learning, ICML\u201920, virtual, JMLR.org (2020)"},{"key":"2229_CR2","first-page":"151","volume":"21","author":"A Aboussoror","year":"1995","unstructured":"Aboussoror, A., Loridan, P.: Strong-weak Stackelberg problems in finite dimensional spaces. Serdica Math. J. 21, 151\u2013170 (1995)","journal-title":"Serdica Math. J."},{"key":"2229_CR3","unstructured":"Arbel, M., Mairal, J.: Amortized implicit differentiation for stochastic bilevel optimization. In: International Conference on Learning Representations, Virtual (2022)"},{"key":"2229_CR4","unstructured":"Arbel, M., Mairal, J.: Non-convex bilevel games with critical point selection maps. In: NeurIPS 2022\u201336th Conference on Neural Information Processing Systems. Advances in Neural Information Processing Systems (NeurIPS) 2022, pp. 1\u201334. United States, New Orleans (2022)"},{"key":"2229_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"3","key":"2229_CR6","doi-asserted-by":"publisher","first-page":"2137","DOI":"10.1137\/22M1540818","volume":"33","author":"F Bach","year":"2023","unstructured":"Bach, F., Rudi, A.: Exponential convergence of sum-of-squares hierarchies for trigonometric polynomials. SIAM J. Optim. 33(3), 2137\u20132159 (2023)","journal-title":"SIAM J. Optim."},{"key":"2229_CR7","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/BF00941574","volume":"68","author":"J Bard","year":"1991","unstructured":"Bard, J.: Some properties of the bilevel programming problem. J. Optim. Theory Appl. 68, 371\u2013378 (1991)","journal-title":"J. Optim. Theory Appl."},{"key":"2229_CR8","volume-title":"Introduction to Real Analysis","author":"RG Bartle","year":"2011","unstructured":"Bartle, R.G., Sherbert, D.R.: Introduction to Real Analysis. Wiley, New Delhi (2011)"},{"key":"2229_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics)","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag, Berlin, Heidelberg (2006)"},{"issue":"2","key":"2229_CR10","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/j.ejor.2023.01.008","volume":"311","author":"Y Beck","year":"2023","unstructured":"Beck, Y., Ljubi\u0107, I., Schmidt, M.: A survey on bilevel optimization under uncertainty. Eur. J. Oper. Res. 311(2), 401\u2013426 (2023)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"2229_CR11","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1016\/j.orl.2021.07.010","volume":"49","author":"Y Beck","year":"2021","unstructured":"Beck, Y., Schmidt, Martin: A robust approach for modeling limited observability in bilevel optimization. Oper. Res. Lett. 49(5), 752\u2013758 (2021)","journal-title":"Oper. Res. Lett."},{"key":"2229_CR12","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1287\/opre.38.3.556","volume":"38","author":"Omar Ben-Ayed","year":"1990","unstructured":"Ben-Ayed, Omar, Blair, E.: Computational difficulties of bilevel linear programming. Oper. Res. 38, 556\u2013560 (1990)","journal-title":"Oper. Res."},{"key":"2229_CR13","volume-title":"Real Algebraic and Semi-algebraic Sets","author":"R Benedetti","year":"1990","unstructured":"Benedetti, R., Risler, J.J.: Real Algebraic and Semi-algebraic Sets. Actualit\u00e9s math\u00e9matiques, Hermann, Paris (1990)"},{"key":"2229_CR14","unstructured":"Berge, C.: Topological spaces. In: Proceedings of the Edinburgh Mathematical Society, vol. 13, (1963)"},{"key":"2229_CR15","volume-title":"Stochastic Optimal Control: The Discrete-Time Case","author":"D Bertsekas","year":"1996","unstructured":"Bertsekas, D., Shreve, S.E.: Stochastic Optimal Control: The Discrete-Time Case, vol. 5. Athena Scientific, Belmont, Massachusetts (1996)"},{"key":"2229_CR16","unstructured":"Blondel, M., Berthet, Q., Cuturi, M., Frostig, R., Hoyer, S., Llinares-L\u2019opez, F., Pedregosa, F., Vert, J.P.: Efficient and modular implicit differentiation. ArXiv, arXiv:2105.15183, (2021)"},{"key":"2229_CR17","unstructured":"Bolte, J., Le, T., Pauwels, E., Silveti-Falls, A.: Nonsmooth Implicit Differentiation for Machine Learning and Optimization. In: Ranzato M., Beygelzimer A., Dauphin Y., Liang P.S., Wortman Vaughan J. (eds.) Advances in Neural Information Processing Systems, vol. 34, pp. 13537\u201313549. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/70afbf2259b4449d8ae1429e054df1b1-Paper.pdf (2021)"},{"issue":"2","key":"2229_CR18","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130906593","volume":"24","author":"A Caprara","year":"2014","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2), 823\u2013838 (2014)","journal-title":"SIAM J. Optim."},{"key":"2229_CR19","unstructured":"Cerulli, M.: Bilevel Optimization and Applications. Theses, Institut Polytechnique de Paris (2021)"},{"issue":"3","key":"2229_CR20","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1080\/02331939508844048","volume":"32","author":"Y Chen","year":"1995","unstructured":"Chen, Y., Florian, M.: The nonlinear bilevel programming problem: formulations, regularity and optimality conditions. Optimization 32(3), 193\u2013209 (1995)","journal-title":"Optimization"},{"key":"2229_CR21","unstructured":"Dagr\u00e9ou, M., Ablin, P., Vaiter, S., Moreau, T.: A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In: Advances in Neural Information Processing Systems (NeurIPS) (2022)"},{"key":"2229_CR22","unstructured":"Dagr\u00e9ou, M., Moreau, T., Vaiter, S., Ablin, P.: a lower bound and a near-optimal algorithm for bilevel empirical risk minimization. In: International Conference on Artificial Intelligence and Statistics (AISTATS) (2024)"},{"issue":"2","key":"2229_CR23","doi-asserted-by":"publisher","first-page":"1327","DOI":"10.1137\/19M1298147","volume":"30","author":"A Daniilidis","year":"2020","unstructured":"Daniilidis, A., Drusvyatskiy, Dmitriy: Pathological subgradient dynamics. SIAM J. Optim. 30(2), 1327\u20131338 (2020)","journal-title":"SIAM J. Optim."},{"key":"2229_CR24","series-title":"Nonconvex Optimization and Its Applications","volume-title":"Foundations of Bilevel Programming","author":"S Dempe","year":"2002","unstructured":"Dempe, S.: Foundations of Bilevel Programming. Nonconvex Optimization and Its Applications, Springer, US (2002)"},{"issue":"4","key":"2229_CR25","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1137\/110845197","volume":"22","author":"S Dempe","year":"2012","unstructured":"Dempe, S., Mordukhovich, B.S., Zemkoho, A.B.: Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J. Optim. 22(4), 1309\u20131343 (2012)","journal-title":"SIAM J. Optim."},{"key":"2229_CR26","unstructured":"Eggermont, C.E.J., Woeginger, G.J.: Motion planning with pulley, rope, and baskets. In: Thomas, W., Christoph, D. (ed.). STACS\u201912 (29th Symposium on Theoretical Aspects of Computer Science), vol. 14, pp. 374\u2013383, Paris, France, LIPIcs (2012)"},{"key":"2229_CR27","unstructured":"Franceschi, L., Frasconi, P., Salzo, S., Grazzi, R., Pontil, M.: Bilevel programming for hyperparameter optimization and meta-learning. In: International Conference on Machine Learning (2018)"},{"key":"2229_CR28","unstructured":"Gould, S., Fernando, B., Cherian, A., Anderson, P., Cruz, R.S., Guo, E.: On differentiating parameterized argmin and argmax problems with application to bi-level optimization. In: CoRR, arXiv:1607.05447, (2016)"},{"key":"2229_CR29","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1080\/00036811.2010.495339","volume":"90","author":"R Henrion","year":"2011","unstructured":"Henrion, R., Surowiec, T.: On calmness conditions in convex bilevel programming. Appl. Anal. 90, 951\u2013970 (2011)","journal-title":"Appl. Anal."},{"key":"2229_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01586088","volume":"32","author":"R Jeroslow","year":"1985","unstructured":"Jeroslow, R.: The polynomial hierarchy and a simple model for competitive analysis. Math. Program. 32, 146\u2013164 (1985)","journal-title":"Math. Program."},{"issue":"1","key":"2229_CR31","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1137\/15M1017922","volume":"26","author":"V Jeyakumar","year":"2016","unstructured":"Jeyakumar, V., Lasserre, J.B., Li, G., Pham, T.S.: Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems. SIAM J. Optim. 26(1), 753\u2013780 (2016)","journal-title":"SIAM J. Optim."},{"key":"2229_CR32","unstructured":"Ji, K., Yang, J., Liang, Y.: Bilevel optimization: convergence analysis and enhanced design. In: International Conference on Machine Learning, Vienna, Austria (2020)"},{"key":"2229_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20735-3","volume-title":"An Introduction to Differential Manifolds","author":"J Lafontaine","year":"2015","unstructured":"Lafontaine, J., et al.: An Introduction to Differential Manifolds. Springer, Cham (2015)"},{"issue":"3","key":"2229_CR34","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"2229_CR35","volume-title":"Introduction to Smooth Manifolds","author":"JM Lee","year":"2000","unstructured":"Lee, J.M.: Introduction to Smooth Manifolds. Springer, New York (2000)"},{"key":"2229_CR36","doi-asserted-by":"publisher","first-page":"04","DOI":"10.1007\/s10107-013-0633-4","volume":"144","author":"GH Lin","year":"2014","unstructured":"Lin, G.H., Mengwei, X., Ye, Jane: On solving simple bilevel programs with a nonconvex lower level program. Math. Program. 144, 04 (2014)","journal-title":"Math. Program."},{"issue":"12","key":"2229_CR37","doi-asserted-by":"publisher","first-page":"10045","DOI":"10.1109\/TPAMI.2021.3132674","volume":"44","author":"R Liu","year":"2022","unstructured":"Liu, R., Gao, J., Zhang, J., Meng, D., Lin, Z.: Investigating bi-level optimization for learning and vision from a unified perspective: a survey and beyond. IEEE Trans. Pattern Anal. Mach. Intell. 44(12), 10045\u201310067 (2022)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2229_CR38","unstructured":"Liu, R., Liu, X., Yuan, X., Zeng, S., Zhang, J.: A value-function-based interior-point method for non-convex bi-level optimization. In: Marina, M., Tong, Z., (eds), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, vol. 139 of Proceedings of Machine Learning Research, pp. 6882\u20136892, virtual, PMLR (2021)"},{"key":"2229_CR39","unstructured":"Liu, R., Liu, Y., Zeng, S., Zhang, J.: Towards gradient-based bilevel optimization with non-convex followers and beyond. In: Ranzato M., Beygelzimer, A., Dauphin, Y., Liang, P., Wortman Vaughan, J., eds) Advances in Neural Information Processing Systems, vol. 34, pp. 8662\u20138675. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/48bea99c85bcbaaba618ba10a6f69e44-Paper.pdf (2021)"},{"key":"2229_CR40","unstructured":"Liu, R., Mu, P., Yuan, X., Zeng, S., Zhang, J.: A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In: International Conference on Machine Learning, Vienna, Austria (2020)"},{"key":"2229_CR41","first-page":"08","volume":"146","author":"A Lodi","year":"2013","unstructured":"Lodi, A., Ralphs, T., Woeginger, G.: Bilevel programming and the separation problem. Math. Program. 146, 08 (2013)","journal-title":"Math. Program."},{"issue":"2","key":"2229_CR42","doi-asserted-by":"publisher","first-page":"717","DOI":"10.2307\/44154072","volume":"26","author":"PD Loewen","year":"2000","unstructured":"Loewen, P.D., Wang, Xianfu: Typical properties of Lipschitz functions. Real Anal. Exch. 26(2), 717\u2013726 (2000)","journal-title":"Real Anal. Exch."},{"key":"2229_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52119-6_7","volume-title":"Bilevel Optimization and Variational Analysis","author":"BS Mordukhovich","year":"2020","unstructured":"Mordukhovich, B.S.: Bilevel Optimization and Variational Analysis. Springer International Publishing, Cham (2020)"},{"issue":"3","key":"2229_CR44","doi-asserted-by":"publisher","first-page":"1728","DOI":"10.1137\/15M1052172","volume":"27","author":"J Nie","year":"2017","unstructured":"Nie, J., Wang, L., Ye, J.J.: Bilevel polynomial programs and semidefinite relaxation methods. SIAM J. Optim. 27(3), 1728\u20131757 (2017)","journal-title":"SIAM J. Optim."},{"key":"2229_CR45","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"Pablo A Parrilo","year":"2003","unstructured":"Parrilo, Pablo A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293\u2013320 (2003)","journal-title":"Math. Program."},{"key":"2229_CR46","unstructured":"Rajeswaran, A., Finn, C., Kakade, S.M., Levine, S.: Meta-learning with implicit gradients. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA (2019)"},{"issue":"4","key":"2229_CR47","doi-asserted-by":"publisher","first-page":"3184","DOI":"10.1287\/moor.2021.1241","volume":"47","author":"R R\u00edos-Zertuche","year":"2022","unstructured":"R\u00edos-Zertuche, R.: Examples of pathological dynamics of the subgradient method for Lipschitz path-differentiable functions. Math. Oper. Res. 47(4), 3184\u20133206 (2022)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2229_CR48","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TEVC.2017.2712906","volume":"22","author":"A Sinha","year":"2018","unstructured":"Sinha, A., Malo, P., Deb, Kalyanmoy: A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Trans. Evolut. Comput. 22(2), 276\u2013295 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"1","key":"2229_CR49","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"LJ Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"2229_CR50","unstructured":"Thomson, B.S., Bruckner, J.B., Bruckner, A.M.: Elementary Real Analysis. www.classicalrealanalysis.com, (2008)"},{"issue":"2","key":"2229_CR51","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1215\/S0012-7094-96-08416-1","volume":"84","author":"L van den Dries","year":"1996","unstructured":"van den Dries, L., Miller, C.: Geometric categories and o-minimal structures. Duke Math. J. 84(2), 497\u2013540 (1996)","journal-title":"Duke Math. J."},{"key":"2229_CR52","unstructured":"Vershynin, R.: High-dimensional probability: an introduction with applications in data science. Number\u00a047 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge"},{"issue":"1","key":"2229_CR53","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/02331939508844060","volume":"33","author":"JJ Ye","year":"1995","unstructured":"Ye, J.J., Zhu, D.L.: Optimality conditions for bilevel programming problems. Optimization 33(1), 9\u201327 (1995)","journal-title":"Optimization"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02229-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02229-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02229-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T12:21:09Z","timestamp":1768047669000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02229-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,29]]},"references-count":53,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["2229"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02229-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,29]]},"assertion":[{"value":"16 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}