Abstract
In this paper, we analyze different schemes for obtaining gradient estimates when the underlying functions are noisy. Good gradient estimation is important e.g. for nonlinear programming solvers. As error criterion, we take the norm of the difference between the real and estimated gradients. The total error can be split into a deterministic error and a stochastic error. For three finite-difference schemes and two design of experiments (DoE) schemes, we analyze both the deterministic errors and stochastic errors. We derive also optimal stepsizes for each scheme, such that the total error is minimized. Some of the schemes have the nice property that this stepsize minimizes also the variance of the error. Based on these results, we show that, to obtain good gradient estimates for noisy functions, it is worthwhile to use DoE schemes. We recommend to implement such schemes in NLP solvers.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Griewank (1989) On Automatic Differentiation M. Iri K. Tanabe (Eds) Mathematical Programming. KTK Scientific Publishers Tokyo, Japan 83–107
L.C.W. Dixon (1994) ArticleTitleOn Automatic Differentiation and Continuous Optimization NATO Advanced Study Institutes Series. 434 501–512
J. Kiefer J. Wolfowitz (1952) ArticleTitleStochastic Estimation of a Regression Function Annals of Mathematical Statistics. 23 462–466
J.R. Blum (1954) ArticleTitleMultidimensional Stochastic Approximation Methods Annals of Mathematical Statistics. 25 737–744
Y. Ermoliev (1980) Stochastic Quasigradient Methods Y. Ermoliev R.J.B. Wets (Eds) Numerical Techniques for Stochastic Optimization. Springer-Verlag Berlin, Germany
J.M. Donohue E.C. Houck R.H. Myers (1993) ArticleTitleSimulation Designs for Controlling Second-Order Bias in First-Order Response Surfaces Operations Research. 41 880–902
J.M. Donohue E.C. Houck R.H. Myers (1995) ArticleTitleSimulation Designs for the Estimation of Quadratic Response Surface Gradients in the Presence of Model Misspecification Management Science. 41 244–262
M.H. Safizadeh (2002) ArticleTitleMinimizing the Bias and Variance of the Gradient Estimate in RSM Simulation Studies European Journal of Operational Research. 136 121–135 Occurrence Handle10.1016/S0377-2217(01)00063-7 Occurrence HandleMR1863668
M.A. Zazanis R. Suri (1993) ArticleTitleConvergence Rates of Finite-Difference Sensitivity Estimates for Stochastic Systems Operations Research. 41 694–703 Occurrence HandleMR1238419
D.C. Montgomery (1984) Design and Analysis of Experiments EditionNumber2 Wiley New York, NY
G.E.P. Box W.G. Hunter J.S. Hunter (1987) Statistics for Experimenters Wiley New York, NY
P.E. Gill W. Murray M.H. Wright (1981) Practical Optimization Academic Press London, UK
Author information
Authors and Affiliations
Additional information
L. C. W. Dixon
We thank our colleague Jack Kleijnen for useful remarks on an earlier version of this paper and Gül Gürkan for providing us with relevant literature. Moreover, we thank the anonymous referee for valuable remarks.
Rights and permissions
About this article
Cite this article
Brekelmans, R.C.M., Driessen, L.T., Hamers, H.J.M. et al. Gradient Estimation Schemes for Noisy Functions. J Optim Theory Appl 126, 529–551 (2005). https://doi.org/10.1007/s10957-005-5496-2
Issue Date:
DOI: https://doi.org/10.1007/s10957-005-5496-2