A one-measurement form of simultaneous perturbation stochastic approximation

By James C. Spall. 1997

The simultaneous perturbation stochastic approximation (SPSA) algorithm has proven very effective for difficult multivariate optimization problems where it is not possible to obtain direct gradient information. As discussed to date, SPSA is based on a highly efficient gradient approximation requiring only two measurements of the loss function independent of the number of parameters being estimated. This note presents a form of SPSA that requires only one function measurement (for any dimension). Theory is presented that identifies the class of problems for which this one-measurement form will be asymptotically superior to the standard two-measurement form.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Episodic Exploration for Deep Deterministic Policies: An Application to StarCraft Micromanagement Tasks (2016, methodology): “This algorithm can be viewed as a heuristic.”
Parameterized quantum circuits as machine learning models (2019, background): “[41] James C Spall, “A one-measurement form of simultaneous perturbation stochastic approximation,” Automatica 33, 109–112 (1997).”
Extremum seeking from 1922 to 2010 (2010, background): “Stochastic dither signals are discussed in [92, 97, 139-141] and references therein.”
The stochastic approximation method for the estimation of a multivariate probability density (2008, background): “…(see, among many others, Blum (1954), Fabian (1967), Kushner and Clark (1978), Hall and Heyde (1980), Ruppert (1982), Chen (1988), Spall (1988), Polyak and Tsybakov (1990), Dippon and Renz (1997), Spall (1997), Chen, Duncan and PasikDuncan (1999), Dippon (2003), and Mokkadem and Pelletier (2007a)).”
A companion for the kiefer-wolfowitz-blum stochastic approximation algorithm (2006, background): “4 Proof of Theorems 1 and 2 In view of the definition of L (θ) n , ∆ (θ) n , L (μ) n and ∆ (μ) n (see (26), (27), (34), and (35) respectively), Theorems 1 and 2 are straightforward consequences of the combination of Lemmas 5 and 7 together with the following lemma.”
Quantum optimization using variational algorithms on near-term quantum devices (2017, background): “ second derivatives helps achieve faster convergence [93]. In contrast, additional savings in time overhead in SPSA optimizations that rely on just one evaluation of the cost function per update step [94] could further improve the performance in large-scale quantum problems where sampling is particu”
Fine-Tuning Language Models with Just Forward Passes (2023, methodology): “Many one-point gradient estimators have been proposed in past works [34, 87, 95], and using such estimators in place of SPSA would halve the training time.”
Supervised learning with quantum-enhanced feature spaces (2018, background): “We have found that Spall’s SPSA [23, 24] stochastic gradient decent algorithm performs well in the noisy experimental setting.”