SPSA

Simultaneous Perturbation Stochastic Approximation is an efficient, popular, stochastic gradient descend method [SpallSpall1992]. It can be defined by:

$$\hat{\theta}_{k + 1} = \hat{\theta}_k - a_k \hat{g}_k(\hat{\theta}_k)$$

$$\hat{g}_{ki}(\hat{\theta}_k) = \frac{y(\hat{\theta}_k + c_k \Delta_k) - y(\hat{\theta}_k - c_k \Delta_k)}{2 c_k}$$

With $\hat{\theta}_k$ the solution estimation at iteration $k$, $a_k$ a learning rate, $\hat{g}_k(\hat{\theta}_k)$ the estimation of the gradient at $\hat{\theta}_k$, $y$ the objective function, $c_k$ a perturbation rate and $\Delta_k$ the randomized perturbation vector.

The current implementation performs this two-sided perturbation to estimate the gradient with the perturbation vector $\Delta_k$ drawn from a Bernoulli $\pm$ distribution to satisfy convergence conditions.

Table 3.6 lists the settings available for this optimizer.

Table 3.6: SPSA Settings

Name	Description
learning-rate	The learning rate $a_k$ used to update the new solution according to the current gradient estimation. You can use a mathematical expression for this setting and use the variable $k$ to indicate the current iteration number
perturbation-rate	The rate $c_k$ with which to perturbate the solution to estimate the gradient. You can use a mathematical expression for this setting and use the variable $k$ to indicate the current iteration number
epsilon	The normalized maximum parameter step size. You can use a mathematical expression for this setting and use the variable $k$ to indicate the current iteration number
boundary-condition	Indicates how parameter boundaries should be handled. There are three possible settings: None (does not contrain the parameter space), StickResult (only constrains the actual solution to be within the parameter boundaries) and StickAll (constrains both the actual position and the perturbed solutions to be within the parameter boundaries).