{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T12:36:54Z","timestamp":1764333414314,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T00:00:00Z","timestamp":1710979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T00:00:00Z","timestamp":1710979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work, we introduce new direct-search schemes for the solution of bilevel optimization (BO) problems. Our methods rely on a fixed accuracy blackbox oracle for the lower-level problem, and deal both with smooth and potentially nonsmooth true objectives. We thus analyze for the first time in the literature direct-search schemes in these settings, giving convergence guarantees to approximate stationary points, as well as complexity bounds in the smooth case. We also propose the first adaptation of mesh adaptive direct-search schemes for BO. Some preliminary numerical results on a standard set of bilevel optimization problems show the effectiveness of our new approaches.\n<\/jats:p>","DOI":"10.1007\/s10589-024-00567-7","type":"journal-article","created":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T09:02:14Z","timestamp":1711011734000},"page":"469-490","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Inexact direct-search methods for bilevel optimization problems"],"prefix":"10.1007","volume":"88","author":[{"given":"Youssef","family":"Diouane","sequence":"first","affiliation":[]},{"given":"Vyacheslav","family":"Kungurtsev","sequence":"additional","affiliation":[]},{"given":"Francesco","family":"Rinaldi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4189-0631","authenticated-orcid":false,"given":"Damiano","family":"Zeffiro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,21]]},"reference":[{"key":"567_CR1","unstructured":"Anagnostidis, S.-K., Lucchi, A., Diouane, Y.: Direct-search for a class of stochastic min-max problems. In: Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, vol. 130, pp. 3772\u20133780. PMLR (2021)"},{"key":"567_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-1124-0_2","volume-title":"A Survey on Direct Search Methods for Blackbox Optimization and Their Applications","author":"C Audet","year":"2014","unstructured":"Audet, C.: A Survey on Direct Search Methods for Blackbox Optimization and Their Applications. Springer, Berlin (2014)"},{"issue":"1","key":"567_CR3","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/040603371","volume":"17","author":"C Audet","year":"2006","unstructured":"Audet, C., Dennis, J.E., Jr.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188\u2013217 (2006)","journal-title":"SIAM J. Optim."},{"key":"567_CR4","unstructured":"Audet, C., Dzahini, K.J., Kokkolaras, M., Le Digabel, S.: Stomads: Stochastic blackbox optimization using probabilistic estimates. arXiv preprint arXiv:1911.01012 (2019)"},{"key":"567_CR5","doi-asserted-by":"crossref","unstructured":"Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization (2017)","DOI":"10.1007\/978-3-319-68913-5"},{"key":"567_CR6","unstructured":"Beck, Y., Schmidt, M.: A Gentle and Incomplete Introduction to Bilevel Optimization (2021)"},{"issue":"2","key":"567_CR7","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s10208-021-09513-z","volume":"22","author":"AS Berahas","year":"2022","unstructured":"Berahas, A.S., Cao, L., Choromanski, K., Scheinberg, K.: A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Found. Comput. Math. 22(2), 507\u2013560 (2022)","journal-title":"Found. Comput. Math."},{"key":"567_CR8","unstructured":"Chen, L., Xu, J., Zhang, J.: On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301.00712 (2023)"},{"key":"567_CR9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s10479-007-0176-2","volume":"153","author":"B Colson","year":"2007","unstructured":"Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153, 235\u2013256 (2007)","journal-title":"Ann. Oper. Res."},{"key":"567_CR10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718768","volume-title":"Introduction to Derivative-Free Optimization","author":"AR Conn","year":"2009","unstructured":"Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. SIAM, Philadelphia (2009)"},{"issue":"3","key":"567_CR11","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1080\/10556788.2010.547579","volume":"27","author":"AR Conn","year":"2012","unstructured":"Conn, A.R., Vicente, L.N.: Bilevel derivative-free optimization and its application to robust optimization. Optim. Methods Softw. 27(3), 561\u2013577 (2012)","journal-title":"Optim. Methods Softw."},{"key":"567_CR12","volume-title":"Foundations of Bilevel Programming","author":"S Dempe","year":"2002","unstructured":"Dempe, S.: Foundations of Bilevel Programming. Springer, Berlin (2002)"},{"key":"567_CR13","doi-asserted-by":"crossref","unstructured":"Dempe, S.: Bilevel optimization: theory, algorithms, applications and a bibliography. In: Bilevel Optimization: Advances and Next Challenges, pp. 581\u2013672 (2020)","DOI":"10.1007\/978-3-030-52119-6_20"},{"key":"567_CR14","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10589-021-00329-9","volume":"81","author":"KJ Dzahini","year":"2022","unstructured":"Dzahini, K.J.: Expected complexity analysis of stochastic direct-search. Comput. Optim. Appl. 81, 179\u2013200 (2022)","journal-title":"Comput. Optim. Appl."},{"issue":"5","key":"567_CR15","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/s10851-021-01020-8","volume":"63","author":"MJ Ehrhardt","year":"2021","unstructured":"Ehrhardt, M.J., Roberts, L.: Inexact derivative-free optimization for bilevel learning. J. Math. Imaging Vis. 63(5), 580\u2013600 (2021)","journal-title":"J. Math. Imaging Vis."},{"issue":"3","key":"567_CR16","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1137\/130940037","volume":"24","author":"G Fasano","year":"2014","unstructured":"Fasano, G., Liuzzi, G., Lucidi, S., Rinaldi, F.: A linesearch-based derivative-free approach for nonsmooth constrained optimization. SIAM J. Optim. 24(3), 959\u2013992 (2014)","journal-title":"SIAM J. Optim."},{"key":"567_CR17","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, pp. 1568\u20131577. PMLR (2018)"},{"key":"567_CR18","unstructured":"Grazzi, R., Franceschi, L., Pontil, M., Salzo, Sa.: On the iteration complexity of hypergradient computation. In: International Conference on Machine Learning, pp. 3748\u20133758. PMLR (2020)"},{"key":"567_CR19","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/BF01386213","volume":"2","author":"JH Halton","year":"1960","unstructured":"Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84\u201390 (1960)","journal-title":"Numer. Math."},{"issue":"22","key":"567_CR20","first-page":"1","volume":"24","author":"K Ji","year":"2023","unstructured":"Ji, K., Liang, Y.: Lower bounds and accelerated algorithms for bilevel optimization. J. Mach. Learn. Res. 24(22), 1\u201356 (2023)","journal-title":"J. Mach. Learn. Res."},{"key":"567_CR21","unstructured":"Ji, K., Yang, J., Liang, Y.: Bilevel optimization: convergence analysis and enhanced design. In: International Conference on Machine Learning, pp. 4882\u20134892. PMLR (2021)"},{"key":"567_CR22","unstructured":"Jordan, M.I., Kornowski, G., Lin, T., Shamir, O., Zampetakis, M.: Deterministic nonsmooth nonconvex optimization. arXiv preprint arXiv:2302.08300 (2023)"},{"key":"567_CR23","doi-asserted-by":"crossref","unstructured":"Karimi, H., Nutini, J., Schmidt, M.: Linear convergence of gradient and proximal-gradient methods under the Polyak\u2013\u0142ojasiewicz condition. In: Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19\u201323, 2016, Proceedings, Part I 16, pp. 795\u2013811. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-46128-1_50"},{"key":"567_CR24","first-page":"30271","volume":"34","author":"P Khanduri","year":"2021","unstructured":"Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., Yang, Z.: A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Adv. Neural Inf. Process. Syst. 34, 30271\u201330283 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"567_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejco.2021.100007","volume":"9","author":"T Kleinert","year":"2021","unstructured":"Kleinert, T., Labb\u00e9, M., Ljubi\u0107, I., Schmidt, M.: A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9, 100007 (2021)","journal-title":"EURO J. Comput. Optim."},{"issue":"3","key":"567_CR26","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1137\/S003614450242889","volume":"45","author":"TG Kolda","year":"2003","unstructured":"Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385\u2013482 (2003)","journal-title":"SIAM Rev."},{"key":"567_CR27","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1017\/S0962492919000060","volume":"28","author":"J Larson","year":"2019","unstructured":"Larson, J., Menickelly, M., Wild, S.M.: Derivative-free optimization methods. Acta Numerica 28, 287\u2013404 (2019)","journal-title":"Acta Numerica"},{"key":"567_CR28","first-page":"26160","volume":"35","author":"T Lin","year":"2022","unstructured":"Lin, T., Zheng, Z., Jordan, M.I.: Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Adv. Neural Inf. Process. Syst. 35, 26160\u201326175 (2022)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"567_CR29","first-page":"17248","volume":"35","author":"B Liu","year":"2022","unstructured":"Liu, B., Ye, M., Wright, S., Stone, P., Liu, Q.: Bome! bilevel optimization made easy: a simple first-order approach. Adv. Neural Inf. Process. Syst. 35, 17248\u201317262 (2022)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"567_CR30","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: International Conference on Machine Learning, pp. 6882\u20136892. PMLR (2021)"},{"key":"567_CR31","first-page":"8662","volume":"34","author":"R Liu","year":"2021","unstructured":"Liu, R., Liu, Y., Zeng, S., Zhang, J.: Towards gradient-based bilevel optimization with non-convex followers and beyond. Adv. Neural Inf. Process. Syst. 34, 8662\u20138675 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"567_CR32","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, pp. 6305\u20136315. PMLR (2020)"},{"key":"567_CR33","doi-asserted-by":"publisher","first-page":"3012","DOI":"10.1137\/19M125772X","volume":"29","author":"G Liuzzi","year":"2019","unstructured":"Liuzzi, G., Lucidi, S., Rinaldi, F., Vicente, L.N.: Trust-region methods for the derivative-free optimization of nonsmooth black-box functions. SIAM J. Optim. 29, 3012\u20133035 (2019)","journal-title":"SIAM J. Optim."},{"key":"567_CR34","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1023\/A:1013735414984","volume":"21","author":"S Lucidi","year":"2002","unstructured":"Lucidi, S., Sciandrone, M.: A derivative-free algorithm for bound constrained optimization. Comput. Optim. Appl. 21, 119\u2013142 (2002)","journal-title":"Comput. Optim. Appl."},{"key":"567_CR35","unstructured":"Maheshwari, C., Shankar Sasty, S.., Ratliff, L., Mazumdar, E.: Convergent first-order methods for bi-level optimization and stackelberg games. arXiv preprint arXiv:2302.01421 (2023)"},{"key":"567_CR36","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s10107-018-1326-9","volume":"179","author":"M Menickelly","year":"2020","unstructured":"Menickelly, M., Wild, S.M.: Derivative-free robust optimization by outer approximations. Math. Program. 179, 157\u2013193 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"567_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10589-009-9295-9","volume":"49","author":"AG Mersha","year":"2011","unstructured":"Mersha, A.G., Dempe, S.: Direct search algorithm for bilevel programming problems. Comput. Optim. Appl. 49(1), 1\u201315 (2011)","journal-title":"Comput. Optim. Appl."},{"key":"567_CR38","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/080724083","volume":"20","author":"JJ Mor\u00e9","year":"2009","unstructured":"Mor\u00e9, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20, 172\u2013191 (2009)","journal-title":"SIAM J. Optim."},{"key":"567_CR39","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s10208-015-9296-2","volume":"17","author":"Y Nesterov","year":"2017","unstructured":"Nesterov, Y., Spokoiny, V.: Random gradient-free minimization of convex functions. Found. Comput. Math. 17, 527\u2013566 (2017)","journal-title":"Found. Comput. Math."},{"key":"567_CR40","unstructured":"Rando, M., Molinari, C., Rosasco, L., Villa, S.: An optimal structured zeroth-order algorithm for non-smooth optimization. arXiv preprint arXiv:2305.16024 (2023)"},{"key":"567_CR41","unstructured":"Rinaldi, F., Vicente, L.N., Zeffiro, D.: A weak tail-bound probabilistic condition for function estimation in stochastic derivative-free optimization. arXiv preprint arXiv:2202.11074 (2022)"},{"key":"567_CR42","unstructured":"Venturini, S., Cristofari, A., Rinaldi, F., Tudisco, F.: Learning the right layers: a data-driven layer-aggregation strategy for semi-supervised learning on multilayer graphs. arXiv preprint arXiv:2306.00152 (2023)"},{"issue":"1\u20132","key":"567_CR43","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s13675-012-0003-7","volume":"1","author":"LN Vicente","year":"2013","unstructured":"Vicente, L.N.: Worst case complexity of direct search. EURO J. Comput. Optim. 1(1\u20132), 143\u2013153 (2013)","journal-title":"EURO J. Comput. Optim."},{"key":"567_CR44","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/j.cor.2012.12.005","volume":"41","author":"D Zhang","year":"2014","unstructured":"Zhang, D., Lin, G.-H.: Bilevel direct search method for leader-follower problems and application in health insurance. Comput. Oper. Res. 41, 359\u2013373 (2014)","journal-title":"Comput. Oper. Res."},{"key":"567_CR45","first-page":"18309","volume":"35","author":"Y Zhang","year":"2022","unstructured":"Zhang, Y., Yao, Y., Parikshit Ram, P., Zhao, T.C., Hong, M., Wang, Y., Liu, S.: Advancing model pruning via bi-level optimization. Adv. Neural Inf. Process. Syst. 35, 18309\u201318326 (2022)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"567_CR46","doi-asserted-by":"crossref","unstructured":"Zhou, S., Zemkoho, A.B., Tin, A.: Bolib: bilevel optimization library of test problems. arXiv preprint arXiv:1812.00230v3 (2020)","DOI":"10.1007\/978-3-030-52119-6_19"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00567-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00567-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00567-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T16:09:48Z","timestamp":1715616588000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00567-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,21]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["567"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00567-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2024,3,21]]},"assertion":[{"value":"13 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}