Simultaneous perturbation stochastic approximation

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 recent 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 u^* with loss function J(u):

u^* = \arg  \min_{u \in U} J(u).

Both Finite Differences Stochastic Approximation (FDSA) and SPSA use the same iterative process:

u_{n+1} = u_n - a_n\hat{g}_n(u_n),

where u_n=((u_n)_1,(u_n)_2,\ldots,(u_n)_p)^T represents the n^{th} iterate, \hat{g}_n(u_n) is the estimate of the gradient of the objective function g(u)= \frac{\partial}{\partial u}J(u) evaluated at {u_n}, and \{a_n\} is a positive number sequence converging to 0. If u_n is a p-dimensional vector, the i^{th} component of the symmetric finite difference gradient estimator is:

FD: (\hat{g_n}(u_n))_i = \frac{J(u_n+c_ne_i)-J(u_n-c_ne_i)}{2c_n},

1 ≤i ≤p, where e_i is the unit vector with a 1 in the i^{th} place, and c_nis a small positive number that decreases with n. With this method, 2p evaluations of J for each g_n are needed. Clearly, when p is large, this estimator loses efficiency.

Let now \Delta_n be a random perturbation vector. The i^{th} component of the stochastic perturbation gradient estimator is:

SP: (\hat{g_n}(u_n))_i = \frac{J(u_n+c_n\Delta_n)-J(u_n-c_n\Delta_n)}{2c_n(\Delta_n)_i}.

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 g_n 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 unbiased estimator of the gradient, as shown in the following lemma.

Convergence lemma

Denote by

b_n = E[\hat{g}_n|u_n] -\nabla J(u_n)

the bias in the estimator \hat{g}_n. Assume that \{(\Delta_n)_i\} are all mutually independent with zero-mean, bounded second moments, and E(|(\Delta_n)_i|^{-1}) uniformly bounded. Then b_n→0 w.p. 1.

Sketch of the proof

The main idea is to use conditioning on \Delta_n to express E[(\hat{g}_n)_i] and then to use a second order Taylor expansion of J(u_n+c_n\Delta_n)_i and J(u_n-c_n\Delta_n)_i. After algebraic manipulations using the zero mean and the independence of \{(\Delta_n)_i\}, we get

E[(\hat{g}_n)_i]=(g_n)_i + O(c_n^2)

The result follows from the hypothesis that c_n→0.

Next we resume some of the hypotheses under which u_t converges in probability to the set of global minima of J(u). The efficiency of the method depends on the shape of J(u), the values of the parameters a_k and c_k and the distribution of the perturbation terms \Delta_{ki}. First, the algorithm parameters must satisfy the following conditions:

A good choice for \Delta_{ki} is the Rademacher distribution, i.e. Bernoulli +-1 with probability 0.5. Other choices are possible too, but note that the uniform and normal distributions cannot be used because they do not satisfy the finite inverse moment conditions.

The loss function J(u) must be thrice continuously differentiable and the individual elements of the third derivative must be bounded: |J^{(3)}(u)| < a_3 < \infty . Also, |J(u)|→∝ as u→∝.

In addition, \nabla J must be Lipschitz continuous, bounded and the ODE  \dot{u}=g(u) must have a unique solution for each initial condition. Under these conditions and a few others, u_k converges in probability to the set of global minima of J(u) (see Maryak and Chin, 2008).

References

    This article is issued from Wikipedia - version of the Wednesday, March 02, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.