{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T13:45:31Z","timestamp":1769521531098,"version":"3.49.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,2,6]],"date-time":"2021-02-06T00:00:00Z","timestamp":1612569600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,6]],"date-time":"2021-02-06T00:00:00Z","timestamp":1612569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S026045\/1"],"award-info":[{"award-number":["EP\/S026045\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T026693\/1"],"award-info":[{"award-number":["EP\/T026693\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005962","name":"Faraday Institute for Science and Religion","doi-asserted-by":"publisher","award":["EP\/T007745\/1"],"award-info":[{"award-number":["EP\/T007745\/1"]}],"id":[{"id":"10.13039\/501100005962","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["ECF-2019-478"],"award-info":[{"award-number":["ECF-2019-478"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Math Imaging Vis"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Variational regularization techniques are dominant in the field of mathematical imaging. A drawback of these techniques is that they are dependent on a number of parameters which have to be set by the user. A by-now common strategy to resolve this issue is to learn these parameters from data. While mathematically appealing, this strategy leads to a nested optimization problem (known as bilevel optimization) which is computationally very difficult to handle. It is common when solving the upper-level problem to assume access to exact solutions of the lower-level problem, which is practically infeasible. In this work we propose to solve these problems using inexact derivative-free optimization algorithms which never require exact lower-level problem solutions, but instead assume access to approximate solutions with controllable accuracy, which is achievable in practice. We prove global convergence and a worst-case complexity bound for our approach. We test our proposed framework on ROF denoising and learning MRI sampling patterns. Dynamically adjusting the lower-level accuracy yields learned parameters with similar reconstruction quality as high-accuracy evaluations but with dramatic reductions in computational work (up to 100 times faster in some cases).\n<\/jats:p>","DOI":"10.1007\/s10851-021-01020-8","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T01:02:21Z","timestamp":1612832541000},"page":"580-600","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Inexact Derivative-Free Optimization for Bilevel Learning"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8523-353X","authenticated-orcid":false,"given":"Matthias J.","family":"Ehrhardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6438-9703","authenticated-orcid":false,"given":"Lindon","family":"Roberts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,6]]},"reference":[{"key":"1020_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492919000059","volume":"28","author":"S Arridge","year":"2019","unstructured":"Arridge, S., Maass, P., \u00d6ktem, O., Sch\u00f6nlieb, C.B.: Solving inverse problems using data-driven models. Acta Numerica 28, 1\u2013174 (2019)","journal-title":"Acta Numerica"},{"key":"1020_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68913-5","volume-title":"Derivative-free and blackbox optimization","author":"C Audet","year":"2017","unstructured":"Audet, C., Hare, W.: Derivative-free and blackbox optimization. Springer Series in Operations Research and Financial Engineering. Springer, Cham (2017)"},{"issue":"3","key":"1020_CR3","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1137\/040620886","volume":"17","author":"C Audet","year":"2006","unstructured":"Audet, C., Orban, D.: Finding optimal algorithmic parameters using derivative-free optimization. SIAM J Optim 17(3), 642\u2013664 (2006)","journal-title":"SIAM J Optim"},{"key":"1020_CR4","unstructured":"Bartels, S., Weber, N.: Parameter learning and fractional differential operators: application in image regularization and decomposition. arXiv preprint arXiv:2001.03394 (2020)"},{"key":"1020_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974997","volume-title":"First-order methods in optimization, MOS-SIAM series on optimization","author":"A Beck","year":"2017","unstructured":"Beck, A.: First-order methods in optimization, MOS-SIAM series on optimization, vol. 25. MOS\/SIAM, Philadelphia (2017)"},{"issue":"1","key":"1020_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm. SIAM J Imagin Sci 2(1), 183\u2013202 (2009)","journal-title":"SIAM J Imagin Sci"},{"issue":"4","key":"1020_CR7","doi-asserted-by":"publisher","first-page":"2881","DOI":"10.1137\/18M1226282","volume":"29","author":"S Bellavia","year":"2020","unstructured":"Bellavia, S., Gurioli, G., Morini, B., Toint, P.L.: Adaptive regularization algorithms with inexact evaluations for nonconvex optimization. SIAM J Optim 29(4), 2881\u20132915 (2020). https:\/\/doi.org\/10.1137\/18M1226282","journal-title":"SIAM J Optim"},{"key":"1020_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492918000016","volume":"27","author":"M Benning","year":"2018","unstructured":"Benning, M., Burger, M.: Modern regularization methods for inverse problems. Acta Numerica 27, 1\u2013111 (2018)","journal-title":"Acta Numerica"},{"issue":"3","key":"1020_CR9","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1137\/090769521","volume":"3","author":"K Bredies","year":"2010","unstructured":"Bredies, K., Kunisch, K., Pock, T.: Total generalized variation. SIAM J Imagin Sci 3(3), 492\u2013526 (2010)","journal-title":"SIAM J Imagin Sci"},{"key":"1020_CR10","doi-asserted-by":"crossref","unstructured":"Bredies, K., Lorenz, D.: Mathematical Image Processing, Applied and Numerical Harmonic Analysis. Birkh\u00e4user, Basel (2018). https:\/\/doi.org\/10.1007\/978-3-030-01458-2","DOI":"10.1007\/978-3-030-01458-2"},{"issue":"1","key":"1020_CR11","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/19M1255355","volume":"31","author":"H Calandra","year":"2021","unstructured":"Calandra, H., Gratton, S., Riccietti, E., Vasseur, X.: On High-order multilevel optimization strategies. SIAM J Optim 31(1), 307\u2013330 (2021). https:\/\/doi.org\/10.1137\/19M1255355","journal-title":"SIAM J Optim"},{"key":"1020_CR12","doi-asserted-by":"crossref","unstructured":"Cartis C, Fiala J, Marteau B, Roberts L (2019) Improving the flexibility and robustness of model-based derivative-free optimization solvers. ACM Trans Math Softw 45(3): 32:1\u201332:41","DOI":"10.1145\/3338517"},{"issue":"4","key":"1020_CR13","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s12532-019-00161-7","volume":"11","author":"C Cartis","year":"2019","unstructured":"Cartis, C., Roberts, L.: A derivative-free Gauss-Newton method. Math Program Comput 11(4), 631\u2013674 (2019)","journal-title":"Math Program Comput"},{"key":"1020_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1017\/S096249291600009X","volume":"25","author":"A Chambolle","year":"2016","unstructured":"Chambolle, A., Pock, T.: An introduction to continuous optimization for imaging. Acta Numerica 25, 161\u2013319 (2016)","journal-title":"Acta Numerica"},{"key":"1020_CR15","doi-asserted-by":"crossref","unstructured":"Chen, R., Scheinberg, K., Chen, B.Y.: Aligning ligand binding cavities by optimizing superposed volume. In: 2012 IEEE International Conference on Bioinformatics and Biomedicine. Philadelphia, PA (2012)","DOI":"10.1109\/BIBM.2012.6392629"},{"key":"1020_CR16","unstructured":"Chen, Y., Ranftl, R., Brox, T., Pock, T.: A bi-level view of inpainting-based image compression. In: 19th Computer Vision Winter Workshop (2014)"},{"key":"1020_CR17","volume-title":"Trust-region methods, MPS-SIAM series on optimization","author":"AR Conn","year":"2000","unstructured":"Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods, MPS-SIAM series on optimization, vol. 1. MPS\/SIAM, Philadelphia (2000)"},{"key":"1020_CR18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718768","volume-title":"Introduction to derivative-free optimization, MPS-SIAM series on optimization","author":"AR Conn","year":"2009","unstructured":"Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to derivative-free optimization, MPS-SIAM series on optimization, vol. 8. MPS\/SIAM, Philadelphia (2009)"},{"issue":"3","key":"1020_CR19","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 Method Softw 27(3), 561\u2013577 (2012)","journal-title":"Optim Method Softw"},{"issue":"1","key":"1020_CR20","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/j.jmaa.2015.09.023","volume":"434","author":"JC De Los Reyes","year":"2016","unstructured":"De Los Reyes, J.C., Sch\u00f6nlieb, C.B., Valkonen, T.: The structure of optimal parameters for image restoration problems. J Math Anal Appl 434(1), 464\u2013500 (2016)","journal-title":"J Math Anal Appl"},{"key":"1020_CR21","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.3934\/ipi.2013.7.1183","volume":"7","author":"JC De Los Reyes","year":"2013","unstructured":"De Los Reyes, J.C., Sch\u00f6nlieb, C.B.: Image denoising: learning the noise model via nonsmooth PDE-constrained optimization. Inverse Probl Imagin 7, 1183\u20131214 (2013)","journal-title":"Inverse Probl Imagin"},{"key":"1020_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511616723","volume-title":"Multidimensional real analysis I: differentiation","author":"JJ Duistermaat","year":"2004","unstructured":"Duistermaat, J.J., Kolk, J.A.C.: Multidimensional real analysis I: differentiation. Cambridge University Press, New York (2004)"},{"key":"1020_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-1740-8","volume-title":"Regularization of inverse problems, mathematics and its applications","author":"HW Engl","year":"1996","unstructured":"Engl, H.W., Hanke, M., Neubauer, A.: Regularization of inverse problems, mathematics and its applications. Springer, NY (1996)"},{"issue":"4","key":"1020_CR24","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/151005683","volume":"26","author":"R Garmanjani","year":"2016","unstructured":"Garmanjani, R., J\u00fadice, D., Vicente, L.N.: Trust-region methods without using derivatives: worst case complexity and the nonsmooth case. SIAM J Optim 26(4), 1987\u20132011 (2016)","journal-title":"SIAM J Optim"},{"issue":"6","key":"1020_CR25","doi-asserted-by":"publisher","first-page":"1394","DOI":"10.1109\/TMI.2018.2832540","volume":"37","author":"B G\u00f6zc\u00fc","year":"2018","unstructured":"G\u00f6zc\u00fc, B., Mahabadi, R.K., Li, Y.H., Ilicak, E., \u00c7ukur, T., Scarlett, J., Cevher, V.: Learning-based compressive MRI. IEEE Trans Med Imagin 37(6), 1394\u20131406 (2018)","journal-title":"IEEE Trans Med Imagin"},{"key":"1020_CR26","doi-asserted-by":"crossref","unstructured":"Gratton, S., Simon, E., Toint, P.L.: An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity. Math Program (2020). https:\/\/doi.org\/10.1007\/s10107-020-01466-5","DOI":"10.1007\/s10107-020-01466-5"},{"issue":"4","key":"1020_CR27","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/1034115","volume":"34","author":"PC Hansen","year":"1992","unstructured":"Hansen, P.C.: Analysis of discrete Ill-posed problems by means of the L-curve. SIAM Rev 34(4), 561\u2013580 (1992)","journal-title":"SIAM Rev"},{"key":"1020_CR28","unstructured":"Hinterm\u00fcller, M., Papafitsoros, K., Rautenberg, C.N., Sun, H.: Dualization and Automatic Distributed Parameter Selection of Total Generalized Variation via Bilevel Optimization. arXiv preprint arXiv:2002.05614 (2020)"},{"key":"1020_CR29","doi-asserted-by":"crossref","unstructured":"Ito, K., Jin, B.: Inverse problems - tikhonov theory and algorithms. World Scientific Publishing, Singapore (2014)","DOI":"10.1142\/9120"},{"issue":"2","key":"1020_CR30","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1137\/120882706","volume":"6","author":"K Kunisch","year":"2013","unstructured":"Kunisch, K., Pock, T.: A bilevel optimization approach for parameter learning in variational models. SIAM J Imagin Sci 6(2), 938\u2013983 (2013)","journal-title":"SIAM J Imagin Sci"},{"key":"1020_CR31","unstructured":"Lakhmiri, D., Le\u00a0Digabel, S., Tribes, C.: HyperNOMAD: Hyperparameter optimization of deep neural networks using mesh adaptive direct search. arXiv preprint arXiv:1907.01698 (2019)"},{"key":"1020_CR32","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1017\/S0962492919000060","volume":"28","author":"JW Larson","year":"2019","unstructured":"Larson, J.W., Menickelly, M., Wild, S.M.: Derivative-free optimization methods. Acta Numerica 28, 287\u2013404 (2019)","journal-title":"Acta Numerica"},{"issue":"6","key":"1020_CR33","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1002\/mrm.21391","volume":"58","author":"M Lustig","year":"2007","unstructured":"Lustig, M., Donoho, D.L., Pauly, J.M.: Sparse MRI: the application of compressed sensing for rapid MR imaging. Magn Reson Med 58(6), 1182\u20131195 (2007)","journal-title":"Magn Reson Med"},{"issue":"5","key":"1020_CR34","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.2514\/1.J051125","volume":"50","author":"A March","year":"2012","unstructured":"March, A., Willcox, K.: Provably convergent multifidelity optimization algorithm not requiring high-fidelity derivatives. AIAA J 50(5), 1079\u20131089 (2012)","journal-title":"AIAA J"},{"issue":"3","key":"1020_CR35","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for solving the convex programming problem with convergence rate $$o(1\/k^2)$$. Doklady Akademii Nauk SSSR 269(3), 543\u2013547 (1983)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"1020_CR36","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Dordrecht (2004)","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"1020_CR37","volume-title":"Numerical optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical optimization, 2nd edn. Springer Science and Business Media, New York (2006)","edition":"2"},{"key":"1020_CR38","doi-asserted-by":"crossref","unstructured":"Ochs, P., Ranftl, R., Brox, T., Pock, T.: Bilevel optimization with nonsmooth lower level problems. SSVM 9087, 654\u2013665 (2015)","DOI":"10.1007\/978-3-319-18461-6_52"},{"key":"1020_CR39","unstructured":"Riis, E.S., Ehrhardt, M.J., Quispel, G.R.W., Sch\u00f6nlieb, C.B.: A geometric integration approach to nonsmooth, nonconvex optimisation. arXiv preprint arXiv:1807.07554 (2018)"},{"issue":"1","key":"1020_CR40","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1287\/moor.5.1.43","volume":"5","author":"SM Robinson","year":"1980","unstructured":"Robinson, S.M.: Strongly regular generalized equations. Math Op Res 5(1), 43\u201362 (1980)","journal-title":"Math Op Res"},{"key":"1020_CR41","volume-title":"Variational analysis","author":"RT Rockafellar","year":"2008","unstructured":"Rockafellar, R.T., Wets, R.J.B.: Variational analysis. Springer science and business media, Berlin (2008)"},{"issue":"1\u20132","key":"1020_CR42","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-019-01362-7","volume":"180","author":"CW Royer","year":"2020","unstructured":"Royer, C.W., O\u2019Neill, M., Wright, S.J.: A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Math Program 180(1\u20132), 451\u2013488 (2020)","journal-title":"Math Program"},{"issue":"1","key":"1020_CR43","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","volume":"60","author":"LI Rudin","year":"1992","unstructured":"Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys D: Nonlinear Phenom 60(1), 259\u2013268 (1992)","journal-title":"Phys D: Nonlinear Phenom"},{"key":"1020_CR44","volume-title":"Variational methods in imaging","author":"O Scherzer","year":"2008","unstructured":"Scherzer, O., Grasmair, M., Grossauer, H., Haltmeier, M., Lenzen, F.: Variational methods in imaging. Springer Science and Business Media LLC, Berlin (2008)"},{"issue":"12","key":"1020_CR45","doi-asserted-by":"publisher","first-page":"4310","DOI":"10.1109\/TMI.2020.3017353","volume":"39","author":"F Sherry","year":"2020","unstructured":"Sherry, F., Benning, M., los Reyes, J.C.D., Graves, M.J., Maierhofer, G., Williams, G., Schonlieb, C.B., Ehrhardt, M.J.: Learning the sampling pattern for MRI. IEEE Trans Med Imagin 39(12), 4310\u20134321 (2020)","journal-title":"IEEE Trans Med Imagin"},{"key":"1020_CR46","unstructured":"Usman, M., Batchelor, P.G.: Optimized Sampling Patterns for Practical Compressed MRI. In: International Conference on Sampling Theory and Applications (2009)"},{"issue":"6","key":"1020_CR47","doi-asserted-by":"publisher","first-page":"3555","DOI":"10.1137\/09075531X","volume":"20","author":"H Zhang","year":"2010","unstructured":"Zhang, H., Conn, A.R., Scheinberg, K.: A derivative-free algorithm for least-squares minimization. SIAM J Optim 20(6), 3555\u20133576 (2010)","journal-title":"SIAM J Optim"}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-021-01020-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10851-021-01020-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-021-01020-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T14:21:52Z","timestamp":1622211712000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10851-021-01020-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,6]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["1020"],"URL":"https:\/\/doi.org\/10.1007\/s10851-021-01020-8","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"value":"0924-9907","type":"print"},{"value":"1573-7683","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,6]]},"assertion":[{"value":"1 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}