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

Payman Sadegh; J. C. Spall

doi:10.1109/ACC.1997.609490

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

Payman Sadegh, J. C. Spall

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

480 Downloads (Pure)

Abstract

The simultaneous perturbation stochastic approximation (SPSA) algorithm has recently attracted considerable attention for 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. We 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. We end the paper with a numerical study related to the area of experiment design

Original language	English
Title of host publication	American Control Conference, 1997. Proceedings of the 1997
Volume	6
Publisher	IEEE
Publication date	1997
Pages	3582-3586
ISBN (Print)	0-7803-3832-4
DOIs	https://doi.org/10.1109/ACC.1997.609490
Publication status	Published - 1997
Event	1997 American Control Conference - Albuquerque, NM, United States Duration: 4 Jun 1997 → 6 Jun 1997 http://www.ece.unm.edu/controls/ACC97/welcome.html

Conference

Conference	1997 American Control Conference
Country/Territory	United States
City	Albuquerque, NM
Period	04/06/1997 → 06/06/1997
Internet address	http://www.ece.unm.edu/controls/ACC97/welcome.html

Bibliographical note

Copyright: 1997 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/ACC.1997.609490

SadeghFinal published version, 570 KB

OpenUrl availability

Full text

Cite this

@inproceedings{f004436b053b4efbb3c6d9ed38ebad17,

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

abstract = "The simultaneous perturbation stochastic approximation (SPSA) algorithm has recently attracted considerable attention for 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. We 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. We end the paper with a numerical study related to the area of experiment design",

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

note = "Copyright: 1997 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; 1997 American Control Conference, ACC 97 ; Conference date: 04-06-1997 Through 06-06-1997",

year = "1997",

doi = "10.1109/ACC.1997.609490",

language = "English",

isbn = "0-7803-3832-4",

volume = "6",

pages = "3582--3586",

booktitle = "American Control Conference, 1997. Proceedings of the 1997",

publisher = "IEEE",

address = "United States",

url = "http://www.ece.unm.edu/controls/ACC97/welcome.html",

}

TY - GEN

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

AU - Sadegh, Payman

AU - Spall, J. C.

N1 - Copyright: 1997 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 - 1997

Y1 - 1997

N2 - The simultaneous perturbation stochastic approximation (SPSA) algorithm has recently attracted considerable attention for 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. We 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. We end the paper with a numerical study related to the area of experiment design

AB - The simultaneous perturbation stochastic approximation (SPSA) algorithm has recently attracted considerable attention for 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. We 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. We end the paper with a numerical study related to the area of experiment design

U2 - 10.1109/ACC.1997.609490

DO - 10.1109/ACC.1997.609490

M3 - Article in proceedings

SN - 0-7803-3832-4

VL - 6

SP - 3582

EP - 3586

BT - American Control Conference, 1997. Proceedings of the 1997

PB - IEEE

T2 - 1997 American Control Conference

Y2 - 4 June 1997 through 6 June 1997

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this