Simultaneous perturbation stochastic approximation (original) (raw)
Simultaneous perturbation stochastic approximation (SPSA) is an algorithmic method for optimizing systems with multiple unknown parameters. It is a type of stochastic approximation algorithm. As an optimization method, it is appropriately suited to large-scale population models, adaptive modeling, simulation optimization, and atmospheric modeling. Many examples are presented at the SPSA website http://www.jhuapl.edu/SPSA. A comprehensive book on the subject is Bhatnagar et al. (2013). An early paper on the subject is Spall (1987) and the foundational paper providing the key theory and justification is Spall (1992).
| Property | Value |
|---|---|
| dbo:abstract | Simultaneous perturbation stochastic approximation (SPSA) is an algorithmic method for optimizing systems with multiple unknown parameters. It is a type of stochastic approximation algorithm. As an optimization method, it is appropriately suited to large-scale population models, adaptive modeling, simulation optimization, and atmospheric modeling. Many examples are presented at the SPSA website http://www.jhuapl.edu/SPSA. A comprehensive book on the subject is Bhatnagar et al. (2013). An early paper on the subject is Spall (1987) and the foundational paper providing the key theory and justification is Spall (1992). SPSA is a descent method capable of finding global minima, sharing this property with other methods as simulated annealing. Its main feature is the gradient approximation that requires only two measurements of the objective function, regardless of the dimension of the optimization problem. Recall that we want to find the optimal control with lossfunction : Both Finite Differences Stochastic Approximation (FDSA)and SPSA use the same iterative process: where represents the iterate, is the estimate of the gradient of the objective function evaluated at , and is a positive number sequence converging to 0. If is a p-dimensional vector, the component of the symmetric finite difference gradient estimator is: FD: 1 ≤i ≤p, where is the unit vector with a 1 in the place, and is a small positive number that decreases with n. With this method, 2p evaluations of J for each are needed. Clearly, when p is large, this estimator loses efficiency. Let now be a random perturbation vector. The component of the stochastic perturbation gradient estimator is: SP: Remark that FD perturbs only one direction at a time, while the SP estimator disturbs all directions at the same time (the numerator is identical in all p components). The number of loss function measurements needed in the SPSA method for each is always 2, independent of the dimension p. Thus, SPSA uses p times fewer function evaluations than FDSA, which makes it a lot more efficient. Simple experiments with p=2 showed that SPSA converges in the same number of iterations as FDSA. The latter follows approximately the steepest descent direction, behaving like the gradient method. On the other hand, SPSA, with the random search direction, does not follow exactly the gradient path. In average though, it tracks it nearly because the gradient approximation is an almost unbiasedestimator of the gradient, as shown in the following lemma. (en) |
| dbo:wikiPageExternalLink | https://dx.doi.org/10.1002/eej.20239 https://link.springer.com/book/10.1007/978-1-4471-4285-0 http://www.jhuapl.edu/SPSA. http://www.jhuapl.edu/SPSA/PDF-SPSA/Spall_An_Overview.PDF |
| dbo:wikiPageID | 24464148 (xsd:integer) |
| dbo:wikiPageLength | 8931 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099031949 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbc:Randomized_algorithms dbr:Symmetric dbr:Approximation dbr:Simulated_annealing dbr:Idea dbc:Optimization_algorithms_and_methods dbr:Stochastic_gradient_descent dbr:Probability dbr:Rademacher_distribution dbr:Atmospheric_model dbc:Stochastic_optimization dbr:Hypothesis dbc:Numerical_climate_and_weather_models dbr:Differentiable_function dbr:Dimension dbr:Optimization dbr:Stochastic_approximation dbr:Convergence_(mathematics) dbr:Parameters dbr:Steepest dbr:Unbiased |
| dbp:wikiPageUsesTemplate | dbt:Isbn |
| dcterms:subject | dbc:Randomized_algorithms dbc:Optimization_algorithms_and_methods dbc:Stochastic_optimization dbc:Numerical_climate_and_weather_models |
| rdf:type | yago:WikicatOptimizationAlgorithmsAndMethods yago:WikicatStochasticAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Simultaneous perturbation stochastic approximation (SPSA) is an algorithmic method for optimizing systems with multiple unknown parameters. It is a type of stochastic approximation algorithm. As an optimization method, it is appropriately suited to large-scale population models, adaptive modeling, simulation optimization, and atmospheric modeling. Many examples are presented at the SPSA website http://www.jhuapl.edu/SPSA. A comprehensive book on the subject is Bhatnagar et al. (2013). An early paper on the subject is Spall (1987) and the foundational paper providing the key theory and justification is Spall (1992). (en) |
| rdfs:label | Simultaneous perturbation stochastic approximation (en) |
| owl:sameAs | freebase:Simultaneous perturbation stochastic approximation yago-res:Simultaneous perturbation stochastic approximation wikidata:Simultaneous perturbation stochastic approximation https://global.dbpedia.org/id/fbRW |
| prov:wasDerivedFrom | wikipedia-en:Simultaneous_perturbation_stochastic_approximation?oldid=1099031949&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Simultaneous_perturbation_stochastic_approximation |
| is dbo:wikiPageDisambiguates of | dbr:SPSA |
| is dbo:wikiPageRedirects of | dbr:Finite_Differences_Stochastic_Approximation |
| is dbo:wikiPageWikiLink of | dbr:List_of_numerical_analysis_topics dbr:Mathematical_optimization dbr:Rademacher_distribution dbr:SPSA dbr:Stochastic_approximation dbr:Stochastic_optimization dbr:Finite_Differences_Stochastic_Approximation |
| is foaf:primaryTopic of | wikipedia-en:Simultaneous_perturbation_stochastic_approximation |