Gradient Estimation Schemes for Noisy Functions

Research output: Working paperDiscussion paperOther research output

282 Downloads (Pure)

Abstract

In this paper we analyze different schemes for obtaining gradient estimates when the underlying function is noisy.Good gradient estimation is e.g. important for nonlinear programming solvers.As an error criterion we take the norm of the difference between the real and estimated gradients.This error can be split up into a deterministic and a stochastic error.For three finite difference schemes and two Design of Experiments (DoE) schemes we analyze both the deterministic and the stochastic errors.We also derive optimal step sizes for each scheme, such that the total error is minimized.Some of the schemes have the nice property that this step size also minimizes 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
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages22
Volume2003-12
Publication statusPublished - 2003

Publication series

NameCentER Discussion Paper
Volume2003-12

Fingerprint

Gradient Estimation
Gradient Estimate
Design of Experiments
Nonlinear Programming
Finite Difference Scheme
Gradient
Minimise
Norm

Keywords

  • nonlinear programming
  • finite elements
  • gradient estimation

Cite this

Brekelmans, R. C. M., Driessen, L., Hamers, H. J. M., & den Hertog, D. (2003). Gradient Estimation Schemes for Noisy Functions. (CentER Discussion Paper; Vol. 2003-12). Tilburg: Operations research.
Brekelmans, R.C.M. ; Driessen, L. ; Hamers, H.J.M. ; den Hertog, D. / Gradient Estimation Schemes for Noisy Functions. Tilburg : Operations research, 2003. (CentER Discussion Paper).
@techreport{4aa4fd6380d9498989a80c1683fc5c4f,
title = "Gradient Estimation Schemes for Noisy Functions",
abstract = "In this paper we analyze different schemes for obtaining gradient estimates when the underlying function is noisy.Good gradient estimation is e.g. important for nonlinear programming solvers.As an error criterion we take the norm of the difference between the real and estimated gradients.This error can be split up into a deterministic and a stochastic error.For three finite difference schemes and two Design of Experiments (DoE) schemes we analyze both the deterministic and the stochastic errors.We also derive optimal step sizes for each scheme, such that the total error is minimized.Some of the schemes have the nice property that this step size also minimizes 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",
keywords = "nonlinear programming, finite elements, gradient estimation",
author = "R.C.M. Brekelmans and L. Driessen and H.J.M. Hamers and {den Hertog}, D.",
note = "Pagination: 22",
year = "2003",
language = "English",
volume = "2003-12",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Brekelmans, RCM, Driessen, L, Hamers, HJM & den Hertog, D 2003 'Gradient Estimation Schemes for Noisy Functions' CentER Discussion Paper, vol. 2003-12, Operations research, Tilburg.

Gradient Estimation Schemes for Noisy Functions. / Brekelmans, R.C.M.; Driessen, L.; Hamers, H.J.M.; den Hertog, D.

Tilburg : Operations research, 2003. (CentER Discussion Paper; Vol. 2003-12).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Gradient Estimation Schemes for Noisy Functions

AU - Brekelmans, R.C.M.

AU - Driessen, L.

AU - Hamers, H.J.M.

AU - den Hertog, D.

N1 - Pagination: 22

PY - 2003

Y1 - 2003

N2 - In this paper we analyze different schemes for obtaining gradient estimates when the underlying function is noisy.Good gradient estimation is e.g. important for nonlinear programming solvers.As an error criterion we take the norm of the difference between the real and estimated gradients.This error can be split up into a deterministic and a stochastic error.For three finite difference schemes and two Design of Experiments (DoE) schemes we analyze both the deterministic and the stochastic errors.We also derive optimal step sizes for each scheme, such that the total error is minimized.Some of the schemes have the nice property that this step size also minimizes 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

AB - In this paper we analyze different schemes for obtaining gradient estimates when the underlying function is noisy.Good gradient estimation is e.g. important for nonlinear programming solvers.As an error criterion we take the norm of the difference between the real and estimated gradients.This error can be split up into a deterministic and a stochastic error.For three finite difference schemes and two Design of Experiments (DoE) schemes we analyze both the deterministic and the stochastic errors.We also derive optimal step sizes for each scheme, such that the total error is minimized.Some of the schemes have the nice property that this step size also minimizes 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

KW - nonlinear programming

KW - finite elements

KW - gradient estimation

M3 - Discussion paper

VL - 2003-12

T3 - CentER Discussion Paper

BT - Gradient Estimation Schemes for Noisy Functions

PB - Operations research

CY - Tilburg

ER -

Brekelmans RCM, Driessen L, Hamers HJM, den Hertog D. Gradient Estimation Schemes for Noisy Functions. Tilburg: Operations research. 2003. (CentER Discussion Paper).