{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T22:41:31Z","timestamp":1776206491735,"version":"3.50.1"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T00:00:00Z","timestamp":1663113600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T00:00:00Z","timestamp":1663113600000},"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\/N510129\/1"],"award-info":[{"award-number":["EP\/N510129\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012338","name":"Alan Turing Institute","doi-asserted-by":"publisher","award":["Turing Project"],"award-info":[{"award-number":["Turing Project"]}],"id":[{"id":"10.13039\/100012338","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007851","name":"National Physical Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007851","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show almost sure convergence of X-REGO to an approximate global solution of the original problem, under weak assumptions on the problem (having a strictly feasible global solution) and on the solver (guaranteed to find an approximate global solution of the reduced problem with sufficiently high probability). In the particular case of unconstrained objectives with low effective dimension, we propose an X-REGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to X-REGO globally converging after a finite number of embeddings, proportional to the effective dimension. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem.\n<\/jats:p>","DOI":"10.1007\/s10107-022-01871-y","type":"journal-article","created":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T12:03:21Z","timestamp":1663157001000},"page":"781-829","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Global optimization using random embeddings"],"prefix":"10.1007","volume":"200","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0963-5550","authenticated-orcid":false,"given":"Coralia","family":"Cartis","sequence":"first","affiliation":[]},{"given":"Estelle","family":"Massart","sequence":"additional","affiliation":[]},{"given":"Adilet","family":"Otemissov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,14]]},"reference":[{"key":"1871_CR1","unstructured":"Amelunxen, D.: Geometric analysis of the condition of the convex feasibility problem. PhD thesis, University of Paderborn (2011)"},{"issue":"2","key":"1871_CR2","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s00454-017-9904-9","volume":"58","author":"D Amelunxen","year":"2017","unstructured":"Amelunxen, D., Lotz, M.: Intrinsic volumes of polyhedral cones: a combinatorial perspective. Discrete Comput. Geom. 58(2), 371\u2013409 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1871_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1093\/imaiai\/iau005","volume":"3","author":"D Amelunxen","year":"2014","unstructured":"Amelunxen, D., Lotz, M., McCoy, M.B., Tropp, J.A.: Living on the edge: phase transitions in convex programs with random data. Inf. Inference J. IMA 3(3), 224\u2013294 (2014)","journal-title":"Inf. Inference J. IMA"},{"key":"1871_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000015","volume":"4","author":"F Bach","year":"2011","unstructured":"Bach, F., Jenatton, R., Mairal, J., Obozinski, G.: Optimization with sparsity-inducing penalties. Found. Trends Mach. Learn. 4, 1\u2013106 (2011)","journal-title":"Found. Trends Mach. Learn."},{"issue":"3","key":"1871_CR5","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1137\/130915984","volume":"24","author":"AS Bandeira","year":"2014","unstructured":"Bandeira, A.S., Scheinberg, K., Vicente, L.N.: Convergence of trust-region methods based on probabilistic models. SIAM J. Optim. 24(3), 1238\u20131264 (2014)","journal-title":"SIAM J. Optim."},{"key":"1871_CR6","doi-asserted-by":"crossref","unstructured":"Beck, A.: Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. Society for Industrial and Applied Mathematics, MOS-SIAM Series on Optimization (2014)","DOI":"10.1137\/1.9781611973655"},{"key":"1871_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Tal. A, Nemirovski, A.: Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics (2001)","DOI":"10.1137\/1.9780898718829"},{"issue":"4","key":"1871_CR8","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1080\/10556788.2020.1725751","volume":"35","author":"AS Berahas","year":"2020","unstructured":"Berahas, A.S., Bollapragada, R., Nocedal, J.: An investigation of Newton-sketch and subsampled Newton methods. Optim. Methods Softw. 35(4), 661\u2013680 (2020)","journal-title":"Optim. Methods Softw."},{"issue":"4","key":"1871_CR9","doi-asserted-by":"publisher","first-page":"2726","DOI":"10.1137\/19M1244378","volume":"30","author":"EH Bergou","year":"2020","unstructured":"Bergou, E.H., Gorbunov, E., Richt\u00e1rik, P.: Stochastic three points method for unconstrained smooth minimization. SIAM J. Optim. 30(4), 2726\u20132749 (2020)","journal-title":"SIAM J. Optim."},{"key":"1871_CR10","doi-asserted-by":"crossref","unstructured":"Binois, M., Ginsbourger, D., Roustant, O.: A warped kernel improving robustness in Bayesian optimization via random embeddings. arXiv e-prints, page. arXiv:1411.3685 (2014)","DOI":"10.1007\/978-3-319-19084-6_28"},{"key":"1871_CR11","unstructured":"Binois, M., Ginsbourger, D., Roustant, O.: On the choice of the low-dimensional domain for global optimization via random embeddings. arXiv e-prints, page. arXiv:1704.05318 (2017)"},{"key":"1871_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York, NY, USA (2004)"},{"key":"1871_CR13","first-page":"35","volume-title":"Knitro: An Integrated Package for Nonlinear Optimization","author":"RH Byrd","year":"2006","unstructured":"Byrd, R.H., Nocedal, J., Waltz, R.A.: Knitro: An Integrated Package for Nonlinear Optimization, pp. 35\u201359. Springer, US, Boston, MA (2006)"},{"key":"1871_CR14","unstructured":"Cai, H., Mckenzie, D., Yin, W., Zhang, Z.: Zeroth-order regularized optimization (ZORO): approximately sparse gradients and adaptive sampling. arXiv e-prints, page. arXiv:2003.13001 (2020)"},{"issue":"1","key":"1871_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1093\/imaiai\/iaab011","volume":"11","author":"C Cartis","year":"2022","unstructured":"Cartis, C., Otemissov, A.: A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality. Inf. Inference J. IMA 11(1), 167\u2013201 (2022)","journal-title":"Inf. Inference J. IMA"},{"key":"1871_CR16","doi-asserted-by":"publisher","unstructured":"Cartis, C., Roberts, L.: Scalable subspace methods for derivative-free nonlinear least-squares optimization. arXiv e-prints, page. Math. Program. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01836-1","DOI":"10.1007\/s10107-022-01836-1"},{"issue":"2","key":"1871_CR17","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10107-017-1137-4","volume":"169","author":"C Cartis","year":"2018","unstructured":"Cartis, C., Scheinberg, K.: Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Math. Program. 169(2), 337\u2013375 (2018)","journal-title":"Math. Program."},{"key":"1871_CR18","unstructured":"Cartis, C., Fiala, J., Shao, Z.: Hashing embeddings of optimal dimension, with applications to linear least squares. arXiv e-prints, page. arxiv:2105.11815 (2021a)"},{"key":"1871_CR19","doi-asserted-by":"crossref","unstructured":"Cartis, C., Massart, E., Otemissov, A.: Global optimization using random embeddings. arXiv e-prints, page. arxiv:2107.12102 (2021b)","DOI":"10.1007\/s10107-022-01871-y"},{"key":"1871_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01812-9","author":"C Cartis","year":"2022","unstructured":"Cartis, C., Massart, E., Otemissov, A.: Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings. Math. Program. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01812-9","journal-title":"Math. Program."},{"key":"1871_CR21","unstructured":"Chen, J., Zhu, G., Gu, R., Yuan, C., Huang, Y.: Semi-supervised embedding learning for high-dimensional Bayesian optimization. arXiv e-prints, page. arXiv:2005.14601 (2020)"},{"key":"1871_CR22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973860","volume-title":"Active Subspaces","author":"P Constantine","year":"2015","unstructured":"Constantine, P.: Active Subspaces. SIAM, Philadelphia, PA (2015)"},{"key":"1871_CR23","doi-asserted-by":"crossref","unstructured":"Demo, N., Tezzele, M., Rozza, G.: A supervised learning approach involving active subspaces for an efficient genetic algorithm in high-dimensional optimization problems. arXiv e-prints, page. arXiv:2006.07282 (2020)","DOI":"10.1137\/20M1345219"},{"key":"1871_CR24","volume-title":"Towards Global Optimization","author":"LCW Dixon","year":"1975","unstructured":"Dixon, L.C.W., Szeg\u00f6, G.P.: Towards Global Optimization. Elsevier, New York (1975)"},{"key":"1871_CR25","unstructured":"Djolonga, J., Krause, A., Cevher, V.: High-dimensional gaussian process bandits. In: Proceedings of the 26th International Conference on Neural Information Processing Systems, NIPS\u201913, pp. 1025\u20131033 (2013)"},{"issue":"2","key":"1871_CR26","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002)","journal-title":"Math. Program."},{"key":"1871_CR27","unstructured":"Eriksson, D., Dong, K., Lee, E.H., Bindel, D., Wilson, A.G.: Scaling Gaussian process regression with derivatives. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS\u201918, pp. 6868\u20136878 (2018)"},{"key":"1871_CR28","unstructured":"Ernesto,P.A., Diliman, U.P.: MVF\u2014multivariate test functions library in C for unconstrained global optimization (2005)"},{"issue":"2","key":"1871_CR29","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s10208-012-9115-y","volume":"12","author":"M Fornasier","year":"2012","unstructured":"Fornasier, M., Schnass, K., Vybiral, J.: Learning functions of few arbitrary linear parameters in high dimensions. Found. Comput. Math. 12(2), 229\u2013262 (2012)","journal-title":"Found. Comput. Math."},{"key":"1871_CR30","unstructured":"Garnett, R., Osborne, M.A., Hennig, P:. Active learning of linear embeddings for gaussian processes. In: Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI\u201914, pp. 230\u2013239 (2014)"},{"key":"1871_CR31","unstructured":"Gavana, A.: Global optimization benchmarks and AMPGO. Available at http:\/\/infinity77.net\/global_optimization\/"},{"key":"1871_CR32","volume-title":"Handbook of Metaheuristics (International Series in Operations Research & Management Science)","author":"M Gendreau","year":"2010","unstructured":"Gendreau, M., Potvin, J.-Y.: Handbook of Metaheuristics (International Series in Operations Research & Management Science), 2nd edn. Springer, US (2010)","edition":"2"},{"issue":"1","key":"1871_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/16-AAP1195","volume":"27","author":"L Goldstein","year":"2017","unstructured":"Goldstein, L., Nourdin, I., Peccati, G.: Gaussian phase transitions and conic intrinsic volumes: steining the Steiner formula. Ann. Appl. Probab. 27(1), 1\u201347 (2017)","journal-title":"Ann. Appl. Probab."},{"key":"1871_CR34","unstructured":"Golovin, D., Karro, J., Kochanski, G., Lee, C., Song, X., Zhang, Q.: Gradientless descent: high-dimensional zeroth-order optimization. In: Proceedings of the Sixth International Conference on Learning Representations, ICLR\u201920 (2020)"},{"key":"1871_CR35","unstructured":"Gower, R., Koralev, D., Lieder, F., Richt\u00e1rik, P.: Rsn: randomized subspace Newton. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems, NIPS\u201919 (2019)"},{"issue":"3","key":"1871_CR36","doi-asserted-by":"publisher","first-page":"1515","DOI":"10.1137\/140961602","volume":"25","author":"S Gratton","year":"2015","unstructured":"Gratton, S., Royer, C.W., Vicente, L.N., Zhang, Z.: Direct search based on probabilistic descent. SIAM J. Optim. 25(3), 1515\u20131541 (2015)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1871_CR37","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10589-019-00062-4","volume":"72","author":"Serge Gratton","year":"2019","unstructured":"Gratton, Serge, Royer, Cl\u00e9ment. W., Vicente, Lu\u00eds. N., Zhang, Zaikun: Direct search based on probabilistic feasible descent for bound and linearly constrained problems. Comput. Optim. Appl. 72(3), 525\u2013559 (2019)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"1871_CR38","doi-asserted-by":"publisher","first-page":"1303","DOI":"10.1287\/moor.2020.1092","volume":"46","author":"D Grishchenko","year":"2021","unstructured":"Grishchenko, D., Iutzeler, F., Malick, J.: Proximal gradient methods with adaptive subspace sampling. Math. Oper. Res. 46(4), 1303\u20131323 (2021)","journal-title":"Math. Oper. Res."},{"key":"1871_CR39","volume-title":"Matrix Variate Distributions","author":"AK Gupta","year":"2000","unstructured":"Gupta, A.K., Nagar, D.K.: Matrix Variate Distributions. Chapman and Hall\/CRC, New York (2000)"},{"key":"1871_CR40","unstructured":"Hanzely, F., Doikov, N., Richt\u00e1rik, P., Nesterov, Y.: Stochastic subspace cubic Newton method. In: Proceedings of the 37th International Conference on Machine Learning, ICML\u201920 (2020)"},{"issue":"2","key":"1871_CR41","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0202009","volume":"2","author":"JH Holland","year":"1973","unstructured":"Holland, J.H.: Genetic algorithms and the optimal allocation of trials. SIAM J. Comput. 2(2), 88\u2013105 (1973)","journal-title":"SIAM J. Comput."},{"key":"1871_CR42","unstructured":"Izmailov, P., Maddox, W.J., Kirichenko, P., Garipov, T., Vetrov, D., Wilson, A.G.: Subspace inference for Bayesian deep learning. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI\u201919) (2019)"},{"key":"1871_CR43","unstructured":"Kirschner, J., Mutny, M., Hiller, N., Ischebeck, R., Krause, A.: Adaptive and safe Bayesian optimization in high dimensions via one-dimensional subspaces. In: Proceedings of the 36th International Conference on Machine Learning, ICML\u201919 (2019)"},{"key":"1871_CR44","unstructured":"Kozak, D., Becker, S., Doostan, A., Tenorio, L.: Stochastic subspace descent. arXiv e-prints, page. arXiv:1904.01145 (2019)"},{"key":"1871_CR45","unstructured":"Lacotte, J., Pilanci, M.: Effective dimension adaptive sketching methods for faster regularized least-squares optimization. In: Proceedings of the 34th Conference on Neural Information Processing Systems, NIPS\u201920 (2020)"},{"key":"1871_CR46","unstructured":"Lacotte, J., Pilanci, M., Pavone, M.: High-dimensional optimization in adaptive random subspaces. In: Proceedings of the 33rd Conference on Neural Information Processing Systems, NIPS\u201919 (2019)"},{"key":"1871_CR47","unstructured":"Li, C., Farkhoor, H., Liu, R., Yosinski, J.: Measuring the intrinsic dimension of objective landscapes. In: Proceedings of the Sixth International Conference on Learning Representations, ICLR\u201918 (2018)"},{"key":"1871_CR48","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.laa.2021.06.010","volume":"626","author":"L Liberti","year":"2021","unstructured":"Liberti, L., Poirion, P.-L., Vu, K.: Random projections for conic programs. Linear Algebra Appl. 626, 204\u2013220 (2021)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"1871_CR49","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1007\/s00454-014-9595-4","volume":"51","author":"MB McCoy","year":"2014","unstructured":"McCoy, M.B., Tropp, J.A.: From Steiner formulas for cones to concentration of intrinsic volumes. Discrete Comput. Geom. 51(4), 926\u2013963 (2014)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"1871_CR50","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"key":"1871_CR51","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":"1871_CR52","unstructured":"NIST. NIST Digital Library of Mathematical Functions, 2020. Available at https:\/\/dlmf.nist.gov"},{"key":"1871_CR53","unstructured":"Otemissov, A.: Dimensionality reduction techniques for global optimization. PhD thesis, University of Oxford (2021)"},{"issue":"1","key":"1871_CR54","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1137\/15M1021106","volume":"27","author":"M Pilanci","year":"2017","unstructured":"Pilanci, M., Wainwright, M.J.: Newton sketch: a near linear-time optimization algorithm with linear-quadratic convergence. SIAM J. Optim. 27(1), 205\u2013245 (2017)","journal-title":"SIAM J. Optim."},{"key":"1871_CR55","unstructured":"Qian, H., Hu, Y.Q., Yu, Y.: Derivative-free optimization of high-dimensional non-convex functions by sequential random embeddings. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI\u201916 (2016)"},{"key":"1871_CR56","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10107-015-0901-6","volume":"156","author":"P Richt\u00e1rik","year":"2015","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Parallel coordinate descent methods for big data optimization. Math. Program. 156, 433\u2013484 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"1871_CR57","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-018-1346-5","volume":"174","author":"F Roosta-Khorasani","year":"2019","unstructured":"Roosta-Khorasani, F., Mahoney, M.W.: Sub-sampled Newton methods. Math. Program. 174(1), 293\u2013326 (2019)","journal-title":"Math. Program."},{"key":"1871_CR58","doi-asserted-by":"crossref","unstructured":"Schneider, R., Weil, W.: Stochastic and Integral Geometry. Springer series in statistics: Probability and its applications. Springer (2008)","DOI":"10.1007\/978-3-540-78859-1"},{"issue":"1","key":"1871_CR59","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/moor.6.1.19","volume":"6","author":"FJ Solis","year":"1981","unstructured":"Solis, F.J., Wets, R.J.-B.: Minimization by random search techniques. Math. Oper. Res. 6(1), 19\u201330 (1981)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1871_CR60","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/110853613","volume":"23","author":"SU Stich","year":"2013","unstructured":"Stich, S.U., M\u00fcller, C.L., G\u00e4rtner, B.: Optimization of convex functions with random pursuit. SIAM J. Optim. 23(2), 1284\u20131309 (2013)","journal-title":"SIAM J. Optim."},{"key":"1871_CR61","unstructured":"Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: test functions and datasets, 2013. Available at https:\/\/www.sfu.ca\/~ssurjano\/"},{"key":"1871_CR62","doi-asserted-by":"publisher","first-page":"133","DOI":"10.2140\/pjm.1951.1.133","volume":"1","author":"FG Tricomi","year":"1951","unstructured":"Tricomi, F.G., Erd\u00e9lyi, A.: The asymptotic expansion of a ratio of gamma functions. Pacific J. Math. 1, 133\u2013142 (1951)","journal-title":"Pacific J. Math."},{"issue":"3","key":"1871_CR63","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/j.acha.2014.01.002","volume":"37","author":"H Tyagi","year":"2014","unstructured":"Tyagi, H., Cevher, V.: Learning non-parametric basis independent models from point queries via low-rank methods. Appl. Comput. Harmon. Anal. 37(3), 389\u2013412 (2014)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1871_CR64","first-page":"1","volume":"23","author":"G Ughi","year":"2021","unstructured":"Ughi, G., Abrol, V., Tanner, J.: An empirical study of derivative-free-optimization algorithms for targeted black-box attacks in deep neural networks. Optim. Eng. 23, 1\u201328 (2021)","journal-title":"Optim. Eng."},{"key":"1871_CR65","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press (2018)","DOI":"10.1017\/9781108231596"},{"issue":"4","key":"1871_CR66","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1287\/moor.2017.0894","volume":"43","author":"K Vu","year":"2018","unstructured":"Vu, K., Poirion, P.-L., Liberti, L.: Random projections for linear programming. Math. Oper. Res. 43(4), 1051\u20131071 (2018)","journal-title":"Math. Oper. Res."},{"key":"1871_CR67","unstructured":"Wang, Y., Du, S.S., Balakrishnan, S., Singh, A.: Stochastic zeroth-order optimization in high dimensions. In: International Conference on Artificial Intelligence and Statistics, AISTATS\u201918 (2018)"},{"issue":"1","key":"1871_CR68","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1613\/jair.4806","volume":"55","author":"Z Wang","year":"2016","unstructured":"Wang, Z., Hutter, F., Zoghi, M., Matheson, D., De Freitas, N.: Bayesian optimization in a billion dimensions via random embeddings. J. Artif. Intell. Res. 55(1), 361\u2013387 (2016)","journal-title":"J. Artif. Intell. Res."},{"key":"1871_CR69","unstructured":"D.\u00a0P. Woodruff. Sketching as a tool for numerical linear algebra. Found. Trends\u00ae Theor. Comput. Sci. 10(1\u20132), 1\u2013157 (2014)"},{"key":"1871_CR70","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","volume":"151","author":"SJ Wright","year":"2015","unstructured":"Wright, S.J.: Coordinate descent algorithms. Math. Program. 151, 3\u201334 (2015)","journal-title":"Math. Program."},{"key":"1871_CR71","doi-asserted-by":"crossref","unstructured":"Zhang, M., Li, H., Su, S.: High dimensional Bayesian optimization via supervised dimension reduction. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI\u201919 (2019)","DOI":"10.24963\/ijcai.2019\/596"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01871-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01871-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01871-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,21]],"date-time":"2023-06-21T12:10:25Z","timestamp":1687349425000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01871-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,14]]},"references-count":71,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1871"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01871-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,14]]},"assertion":[{"value":"7 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}