Finite Difference Gradient Approximation: To Randomize or Not?

References

• Berahas AS, Byrd RH, Nocedal J (2018) Derivative-free optimization of noisy functions via quasi-Newton methods. Preprint, submitted March 27, https://arxiv.org/abs/1803.10173.Google Scholar
• Berahas AS, Cao L, Scheinberg K (2021) A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations Comput. Math. 22:507–560.Crossref, Google Scholar
• Conn AR, Scheinberg K, Vicente LN (2008) Introduction to Derivative-free Optimization, MPS-SIAM Series on Optimization (SIAM, Philadelphia).Google Scholar
• Duchi JC, Jordan MI, Wainwright MJ, Wibisono A (2015) Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Trans. Inform. Theory 61(5):2788–2806.Crossref, Google Scholar
• Fazel M, Ge R, Kakade SM, Mesbahi M (2018) Global convergence of policy gradient methods for the linear quadratic regulator. Preprint, submitted January 15, https://arxiv.org/abs/1801.05039.Google Scholar
• Flaxman AD, Kalai AT, McMahan HB (2005) Online convex optimization in the bandit setting: Gradient descent without a gradient. Proc. Sixteenth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 385–394.Google Scholar
• Ghadimi S, Lan G (2013) Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4):2341–2368.Crossref, Google Scholar
• Larson J, Menickelly M, Wild S (2019) Derivative-free optimization methods. Acta Numerica 28:287–404.Crossref, Google Scholar
• Maggiar A, Wächter A, Dolinskaya IS, Staum J (2018) A derivative-free trust-region algorithm for the optimization of functions smoothed via Gaussian convolution using adaptive multiple importance sampling. SIAM J. Optim. 28(2):1478–1507.Crossref, Google Scholar
• Moré JJ, Wild SM (2012) Estimating derivatives of noisy simulations. ACM Trans. Math. Software 38(3):1–21.Crossref, Google Scholar
• Nesterov Y, Spokoiny V (2017) Random gradient-free minimization of convex functions. Found. Comput. Math. 17(2):527–566.Crossref, Google Scholar
• Salimans T, Ho J, Chen X, Sidor S, Sutskever I (2017) Evolution strategies as a scalable alternative to reinforcement learning. Preprint, submitted March 10, https://arxiv.org/abs/1703.03864.Google Scholar
• Shamir O (2017) An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. J. Machine Learn. Res. 18(1):1703–1713.Google Scholar
• Snoek J, Larochelle H, Adams RP (2012) Practical Bayesian optimization of machine learning algorithms. Pereira F, Burges CJC, Bottou L, Weinberger KQ, eds. Proc. 25th Internat. Conf. Neural Inform. Processing Systems, vol. 2 (Curran Associates, Inc., Red Hook, NY), 2951–2959.Google Scholar
• Spall JC (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Automatic Control 37(3):332–341.Crossref, Google Scholar
• Spall JC (2000) Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Trans. Automatic Control 45(10):1839–1853.Crossref, Google Scholar