SPSA in Go

tl;dr - I created an SPSA library in Go. You can find it on github and documentation on godoc.

While it doesn’t get the press of other Evolutionary Computing algorithms, Simultaneous Perturbation Stochastic Analysis (SPSA) is a global stochastic optimizer with a strong theoretical foundation. It has a defined asymptotic convergence rate, even in high noise situations. It works as an extension of stochastic root finding by estimating the gradient (derivative) of the target function using only two measurements (regardless of parameter vector dimension). Here’s the core iteration of the algorithm:

Where G is a function that takes the loss function L (to be minimized) and the current iteration of the parameter vector θ and produces a gradient estimate using simultaneous perturbation. If you’d like to read more, check out the website or Spall’s original paper [pdf].

I wrote a golang implementation of it originally for my final project in Spall’s class at JHU. I repackaged it with a nicer API and a full test suite. Its on github, documentation on godoc, and testing on travis.

Here’s some example code that uses it from the docs.

spsa := &SPSA{
  L: AbsoluteSum, // Loss Function
  C: NoConstraints,
  Theta: Vector{1,1,1,1,1},
  Ak: StandardAk(1, 100, .602),
  Ck: StandardCk(.1, .101),
  Delta: Bernoulli{1},
}
theta := spsa.Run(1000)