Optimal random perturbations for stochastic approximation using a simultaneous perturbation gradient approximation

Payman Sadegh; J. C. Spall

doi:10.1109/9.720513

Optimal random perturbations for stochastic approximation using a simultaneous perturbation gradient approximation

Payman Sadegh, J. C. Spall

Research output: Contribution to journal › Journal article › Research › peer-review

667 Downloads (Pure)

Abstract

The simultaneous perturbation stochastic approximation (SPSA) algorithm has attracted considerable attention for challenging optimization problems where it is difficult or impossible to obtain a direct gradient of the objective (say, loss) function. The approach is based on a highly efficient simultaneous perturbation approximation to the gradient based on loss function measurements. SPSA is based on picking a simultaneous perturbation (random) vector in a Monte Carlo fashion as part of generating the approximation to the gradient. This paper derives the optimal distribution for the Monte Carlo process. The objective is to minimize the mean square error of the estimate. The authors also consider maximization of the likelihood that the estimate be confined within a bounded symmetric region of the true parameter. The optimal distribution for the components of the simultaneous perturbation vector is found to be a symmetric Bernoulli in both cases. The authors end the paper with a numerical study related to the area of experiment design

Original language	English
Journal	I E E E Transactions on Automatic Control
Volume	43
Issue number	10
Pages (from-to)	1480-1484
ISSN	0018-9286
DOIs	https://doi.org/10.1109/9.720513
Publication status	Published - 1998

Bibliographical note

Copyright: 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

Access to Document

10.1109/9.720513

SadeghFinal published version, 137 KB

OpenUrl availability

Full text

Cite this

@article{0bd84183361a446cb710cdc327770b59,

title = "Optimal random perturbations for stochastic approximation using a simultaneous perturbation gradient approximation",

abstract = "The simultaneous perturbation stochastic approximation (SPSA) algorithm has attracted considerable attention for challenging optimization problems where it is difficult or impossible to obtain a direct gradient of the objective (say, loss) function. The approach is based on a highly efficient simultaneous perturbation approximation to the gradient based on loss function measurements. SPSA is based on picking a simultaneous perturbation (random) vector in a Monte Carlo fashion as part of generating the approximation to the gradient. This paper derives the optimal distribution for the Monte Carlo process. The objective is to minimize the mean square error of the estimate. The authors also consider maximization of the likelihood that the estimate be confined within a bounded symmetric region of the true parameter. The optimal distribution for the components of the simultaneous perturbation vector is found to be a symmetric Bernoulli in both cases. The authors end the paper with a numerical study related to the area of experiment design",

author = "Payman Sadegh and Spall, {J. C.}",

note = "Copyright: 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE",

year = "1998",

doi = "10.1109/9.720513",

language = "English",

volume = "43",

pages = "1480--1484",

journal = "I E E E Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers",

number = "10",

}

TY - JOUR

T1 - Optimal random perturbations for stochastic approximation using a simultaneous perturbation gradient approximation

AU - Sadegh, Payman

AU - Spall, J. C.

N1 - Copyright: 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

PY - 1998

Y1 - 1998

N2 - The simultaneous perturbation stochastic approximation (SPSA) algorithm has attracted considerable attention for challenging optimization problems where it is difficult or impossible to obtain a direct gradient of the objective (say, loss) function. The approach is based on a highly efficient simultaneous perturbation approximation to the gradient based on loss function measurements. SPSA is based on picking a simultaneous perturbation (random) vector in a Monte Carlo fashion as part of generating the approximation to the gradient. This paper derives the optimal distribution for the Monte Carlo process. The objective is to minimize the mean square error of the estimate. The authors also consider maximization of the likelihood that the estimate be confined within a bounded symmetric region of the true parameter. The optimal distribution for the components of the simultaneous perturbation vector is found to be a symmetric Bernoulli in both cases. The authors end the paper with a numerical study related to the area of experiment design

AB - The simultaneous perturbation stochastic approximation (SPSA) algorithm has attracted considerable attention for challenging optimization problems where it is difficult or impossible to obtain a direct gradient of the objective (say, loss) function. The approach is based on a highly efficient simultaneous perturbation approximation to the gradient based on loss function measurements. SPSA is based on picking a simultaneous perturbation (random) vector in a Monte Carlo fashion as part of generating the approximation to the gradient. This paper derives the optimal distribution for the Monte Carlo process. The objective is to minimize the mean square error of the estimate. The authors also consider maximization of the likelihood that the estimate be confined within a bounded symmetric region of the true parameter. The optimal distribution for the components of the simultaneous perturbation vector is found to be a symmetric Bernoulli in both cases. The authors end the paper with a numerical study related to the area of experiment design

U2 - 10.1109/9.720513

DO - 10.1109/9.720513

M3 - Journal article

SN - 0018-9286

VL - 43

SP - 1480

EP - 1484

JO - I E E E Transactions on Automatic Control

JF - I E E E Transactions on Automatic Control

IS - 10

ER -

Optimal random perturbations for stochastic approximation using a simultaneous perturbation gradient approximation

Abstract

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this