SPSA Step

Problem

Take one SPSA (simultaneous perturbation stochastic approximation) step.

After random.seed(seed), draw delta_i = +1 when random.random() < 0.5 and -1 otherwise. With step = a / (k + 1) ** 0.602, return x_i - step * (loss_plus - loss_minus) / (2 * c * delta_i).

Hint

A single pair of loss evaluations yields a gradient estimate for all coordinates.

Test cases

case 1

in: [[1,2],3,2.5,0.1,0.05,0,0]

expected: [1.5,2.5]

case 2

in: [[0,0,0],1.5,1,0.2,0.1,5,42]

expected: [0.17002898082240728,-0.17002898082240728,-0.17002898082240728]

case 3

in: [[1],2,4,0.5,0.25,10,7]

expected: [1.472184361309482]

Starter codePython

def spsa_update(x, loss_plus, loss_minus, a, c, k, seed):
    # Your code here
    pass

3 test cases · run your code against them in the editor