{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T22:41:38Z","timestamp":1776206498139,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T00:00:00Z","timestamp":1620345600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T00:00:00Z","timestamp":1620345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s10208-021-09513-z","type":"journal-article","created":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T18:03:58Z","timestamp":1620410638000},"page":"507-560","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":92,"title":["A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization"],"prefix":"10.1007","volume":"22","author":[{"given":"Albert S.","family":"Berahas","sequence":"first","affiliation":[]},{"given":"Liyuan","family":"Cao","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"Choromanski","sequence":"additional","affiliation":[]},{"given":"Katya","family":"Scheinberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,7]]},"reference":[{"key":"9513_CR1","doi-asserted-by":"crossref","unstructured":"S\u00f8ren Asmussen and Peter\u00a0W. Glynn. Stochastic simulation - algorithms and analysis, volume\u00a057 of Stochastic modeling and applied probability. Springer, 2007.","DOI":"10.1007\/978-0-387-69033-9"},{"key":"9513_CR2","doi-asserted-by":"crossref","unstructured":"Afonso Bandeira, Katya Scheinberg, and Luis\u00a0N Vicente. Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization. Mathematical Programming, Series B, 134:223\u2013257, 2012.","DOI":"10.1007\/s10107-012-0578-z"},{"key":"9513_CR3","unstructured":"Anastasia Bayandina, Alexander Gasnikov, Fariman Guliev, and Anastasia Lagunovskaya. Gradient-free two-points optimal method for nonsmooth stochastic convex optimization problem with additional small noise. arXiv preprintarXiv:1701.03821, 2017."},{"key":"9513_CR4","doi-asserted-by":"crossref","unstructured":"Albert\u00a0S Berahas, Richard\u00a0H Byrd, and Jorge Nocedal. Derivative-free optimization of noisy functions via quasi-newton methods. SIAM Journal on Optimization, 29(2):965\u2013993, 2019.","DOI":"10.1137\/18M1177718"},{"key":"9513_CR5","unstructured":"Albert\u00a0S Berahas, Liyuan Cao, and Katya Scheinberg. Global convergence rate analysis of a generic line search algorithm with noise. arXiv preprintarXiv:1910.04055, 2019."},{"key":"9513_CR6","unstructured":"Lev Bogolubsky, Pavel Dvurechenskii, Alexander Gasnikov, Gleb Gusev, Yurii Nesterov, Andrei\u00a0M Raigorodskii, Aleksey Tikhonov, and Maksim Zhukovskii. Learning supervised pagerank with gradient-based and gradient-free optimization methods. Advances in neural information processing systems, 29:4914\u20134922, 2016."},{"key":"9513_CR7","unstructured":"Raghu Bollapragada and Stefan\u00a0M Wild. Adaptive sampling quasi-newton methods for derivative-free stochastic optimization. arXiv preprintarXiv:1910.13516, 2019."},{"key":"9513_CR8","unstructured":"Richard\u00a0P Brent. Algorithms for minimization without derivatives. Courier Corporation, 2013."},{"key":"9513_CR9","unstructured":"Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAI Gym. arXiv preprintarXiv:1606.01540, 2016."},{"key":"9513_CR10","doi-asserted-by":"crossref","unstructured":"Richard\u00a0H Byrd, Gillian\u00a0M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning. Mathematical programming, 134(1):127\u2013155, 2012.","DOI":"10.1007\/s10107-012-0572-5"},{"key":"9513_CR11","doi-asserted-by":"crossref","unstructured":"Richard\u00a0G Carter. On the global convergence of trust region algorithms using inexact gradient information. SIAM Journal on Numerical Analysis, 28(1):251\u2013265, 1991.","DOI":"10.1137\/0728014"},{"key":"9513_CR12","unstructured":"Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Mathematical Programming, pages 1\u201339, 2018."},{"key":"9513_CR13","doi-asserted-by":"crossref","unstructured":"Krzysztof Choromanski, Atil Iscen, Vikas Sindhwani, Jie Tan, and Erwin Coumans. Optimizing simulations with noise-tolerant structured exploration. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 2970\u20132977. IEEE, 2018.","DOI":"10.1109\/ICRA.2018.8460492"},{"key":"9513_CR14","unstructured":"Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard\u00a0E Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. arXiv preprintarXiv:1804.02395, 2018."},{"key":"9513_CR15","unstructured":"Andrew\u00a0R Conn, Katya Scheinberg, and Philippe\u00a0L Toint. On the convergence of derivative-free methods for unconstrained optimization. In A.\u00a0Iserles and M.\u00a0Buhmann, editors, Approximation Theory and Optimization: Tributes to M. J. D. Powell, pages 83\u2013108, Cambridge, England, 1997. Cambridge University Press."},{"key":"9513_CR16","doi-asserted-by":"crossref","unstructured":"Andrew\u00a0R Conn, Katya Scheinberg, and Philippe\u00a0L Toint. A derivative free optimization algorithm in practice. Proceedings of the 7th AIAA\/USAF\/NASA\/ISSMO Symposium on Multidisciplinary Analysis and Optimization, St. Louis, Missouri, September 2-4, 1998.","DOI":"10.2514\/6.1998-4718"},{"key":"9513_CR17","doi-asserted-by":"crossref","unstructured":"Andrew\u00a0R Conn, Katya Scheinberg, and Luis\u00a0N Vicente. Geometry of interpolation sets in derivative free optimization. Mathematical programming, 111(1-2):141\u2013172, 2008.","DOI":"10.1007\/s10107-006-0073-5"},{"key":"9513_CR18","doi-asserted-by":"crossref","unstructured":"Andrew\u00a0R Conn, Katya Scheinberg, and Luis\u00a0N Vicente. Introduction to Derivative-free Optimization. MPS-SIAM Optimization series. SIAM, Philadelphia, USA, 2008.","DOI":"10.1137\/1.9780898718768"},{"key":"9513_CR19","doi-asserted-by":"crossref","unstructured":"Elizabeth\u00a0D Dolan and Jorge\u00a0J Mor\u00e9. Benchmarking Optimization Software with Performance Profiles. Mathematical Programming, 91(2):201\u2013213, 2002.","DOI":"10.1007\/s101070100263"},{"key":"9513_CR20","doi-asserted-by":"crossref","unstructured":"John\u00a0C Duchi, Michael\u00a0I Jordan, Martin\u00a0J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788\u20132806, 2015.","DOI":"10.1109\/TIT.2015.2409256"},{"key":"9513_CR21","doi-asserted-by":"crossref","unstructured":"Pavel Dvurechensky, Eduard Gorbunov, and Alexander Gasnikov. An accelerated directional derivative method for smooth stochastic convex optimization. European Journal of Operational Research, 2020.","DOI":"10.1016\/j.ejor.2020.08.027"},{"key":"9513_CR22","unstructured":"Maryam Fazel, Rong Ge, Sham\u00a0M Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. arXiv preprintarXiv:1801.05039, 2018."},{"key":"9513_CR23","unstructured":"Abraham\u00a0D Flaxman, Adam\u00a0Tauman Kalai, and H\u00a0Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385\u2013394. Society for Industrial and Applied Mathematics, 2005."},{"issue":"4","key":"9513_CR24","doi-asserted-by":"publisher","first-page":"2341","DOI":"10.1137\/120880811","volume":"23","author":"Saeed Ghadimi","year":"2013","unstructured":"Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341\u20132368, 2013.","journal-title":"SIAM Journal on Optimization"},{"key":"9513_CR25","unstructured":"Kevin\u00a0G Jamieson, Robert Nowak, and Ben Recht. Query complexity of derivative-free optimization. Advances in Neural Information Processing Systems, 25:2672\u20132680, 2012."},{"key":"9513_CR26","doi-asserted-by":"crossref","unstructured":"Jack\u00a0C Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, 23(3):462\u2013466, 1952.","DOI":"10.1214\/aoms\/1177729392"},{"key":"9513_CR27","doi-asserted-by":"crossref","unstructured":"Jeffrey Larson, Matt Menickelly, and Stefan\u00a0M Wild. Derivative-free optimization methods. Acta Numerica, 28:287\u2013404, 2019.","DOI":"10.1017\/S0962492919000060"},{"key":"9513_CR28","doi-asserted-by":"crossref","unstructured":"Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 3727\u20133737, 2018.","DOI":"10.1109\/GlobalSIP.2018.8646618"},{"key":"9513_CR29","doi-asserted-by":"crossref","unstructured":"Alvaro Maggiar, Andreas W\u00e4chter, Irina\u00a0S Dolinskaya, and Jeremy Staum. A derivative-free trust-region algorithm for the optimization of functions smoothed via gaussian convolution using adaptive multiple importance sampling. SIAM Journal on Optimization, 28(2):1478\u20131507, 2018.","DOI":"10.1137\/15M1031679"},{"key":"9513_CR30","doi-asserted-by":"crossref","unstructured":"Jorge\u00a0J Mor\u00e9 and Stefan\u00a0M Wild. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1):172\u2013191, 2009.","DOI":"10.1137\/080724083"},{"key":"9513_CR31","doi-asserted-by":"crossref","unstructured":"Jorge\u00a0J Mor\u00e9 and Stefan\u00a0M Wild. Estimating computational noise. SIAM Journal on Scientific Computing, 33(3):1292\u20131314, 2011.","DOI":"10.1137\/100786125"},{"issue":"2","key":"9513_CR32","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s10208-015-9296-2","volume":"17","author":"Yurii Nesterov","year":"2017","unstructured":"Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527\u2013566, 2017.","journal-title":"Foundations of Computational Mathematics"},{"key":"9513_CR33","unstructured":"Jorge Nocedal and Stephen\u00a0J Wright. Numerical Optimization, Second Edition. Springer, 2006."},{"issue":"1","key":"9513_CR34","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/18M1216250","volume":"30","author":"Courtney Paquette","year":"2020","unstructured":"Courtney Paquette and Katya Scheinberg. A stochastic line search method with expected complexity analysis. SIAM Journal on Optimization, 30(1):349\u2013376, 2020.","journal-title":"SIAM Journal on Optimization"},{"key":"9513_CR35","doi-asserted-by":"crossref","unstructured":"Raghu Pasupathy, Peter Glynn, Soumyadip Ghosh, and Fatemeh\u00a0S Hashemi. On sampling rates in simulation-based recursions. SIAM Journal on Optimization, 28(1):45\u201373, 2018.","DOI":"10.1137\/140951679"},{"key":"9513_CR36","doi-asserted-by":"crossref","unstructured":"Valentin\u00a0V Petrov. On lower bounds for tail probabilities. Journal of statistical planning and inference, 137(8):2703\u20132705, 2007.","DOI":"10.1016\/j.jspi.2006.02.015"},{"key":"9513_CR37","unstructured":"Boris\u00a0T Polyak. Introduction to Optimization (1987). Optimization Software, Inc, New York."},{"key":"9513_CR38","first-page":"60","volume":"9","author":"Michael J D Powell","year":"1974","unstructured":"Michael J\u00a0D Powell. Unconstrained minimization algorithms without computation of derivatives. Bollettino delle Unione Matematica Italiana, 9:60\u201369, 1974.","journal-title":"Bollettino delle Unione Matematica Italiana"},{"key":"9513_CR39","doi-asserted-by":"crossref","unstructured":"Michael J\u00a0D Powell. The NEWUOA software for unconstrained optimization without derivatives. In Large-Scale Nonlinear Optimization, volume\u00a083, pages 255\u2013297. Springer, US, 2006.","DOI":"10.1007\/0-387-30065-1_16"},{"key":"9513_CR40","unstructured":"Mark Rowland, Krzysztof Choromanski, Fran\u00e7ois Chalus, Aldo Pacchiano, Tamas Sarl\u00f3s, Turner\u00a0Richard E, and Adrian Weller. Geometrically coupled monte carlo sampling. In Advances in Neural Information Processing Systems, pages 195\u2013205, 2018."},{"key":"9513_CR41","unstructured":"Tim Salimans, Jonathan Ho, Xi\u00a0Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. Technical Report arXiv:1703.03864, 2016."},{"key":"9513_CR42","unstructured":"Klaus Schittkowski. More test examples for nonlinear programming codes, volume 282. Springer Science & Business Media, 2012."},{"key":"9513_CR43","unstructured":"John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889\u20131897, 2015."},{"issue":"1","key":"9513_CR44","first-page":"1703","volume":"18","author":"Ohad Shamir","year":"2017","unstructured":"Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1703\u20131713, 2017.","journal-title":"The Journal of Machine Learning Research"},{"key":"9513_CR45","doi-asserted-by":"crossref","unstructured":"Sara Shashaani, Fatemeh\u00a0S Hashemi, and Raghu Pasupathy. Astro-df: A class of adaptive sampling trust-region algorithms for derivative-free stochastic optimization. SIAM Journal on Optimization, 28(4):3145\u20133176, 2018.","DOI":"10.1137\/15M1042425"},{"key":"9513_CR46","doi-asserted-by":"crossref","unstructured":"James\u00a0C Spall. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE transactions on automatic control, 45(10):1839\u20131853, 2000.","DOI":"10.1109\/TAC.2000.880982"},{"key":"9513_CR47","unstructured":"James\u00a0C Spall. Introduction to stochastic search and optimization: estimation, simulation, and control, volume\u00a065. John Wiley & Sons, 2005."},{"key":"9513_CR48","unstructured":"Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael\u00a0I Jordan. Stochastic cubic regularization for fast nonconvex optimization. In Advances in neural information processing systems, pages 2899\u20132908, 2018."},{"key":"9513_CR49","doi-asserted-by":"crossref","unstructured":"Joel\u00a0A Tropp. An introduction to matrix concentration inequalities. arXiv preprintarXiv:1501.01571, 2015.","DOI":"10.1561\/9781601988393"},{"issue":"1","key":"9513_CR50","first-page":"949","volume":"15","author":"Daan Wierstra","year":"2014","unstructured":"Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi\u00a0Sun, Jan Peters, and J\u00fcrgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949\u2013980, 2014.","journal-title":"The Journal of Machine Learning Research"},{"key":"9513_CR51","doi-asserted-by":"crossref","unstructured":"Stefan\u00a0M Wild, Rommel\u00a0G Regis, and Christine\u00a0A Shoemaker. ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM Journal on Scientific Computing, 30(6):3197\u20133219, 2008.","DOI":"10.1137\/070691814"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09513-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09513-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09513-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T17:10:15Z","timestamp":1649869815000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09513-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,7]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9513"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09513-z","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,7]]},"assertion":[{"value":"26 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}