Preliminary results on non-bernoulli distribution of perturbations for simultaneous perturbation stochastic approximation

Simultaneous perturbation stochastic approximation (SPSA) has proven to be an efficient algorithm for recursive optimization. SPSA uses a centered difference approximation to the gradient based on only two function evaluations regardless of the dimension of the problem. Typically, the Bernoulli ±1 distribution is used for perturbation vectors and theory has been established to prove the asymptotic optimality of this distribution. However, efficiency of the Bernoulli distribution may not be guaranteed for small-samples. In this paper, we investigate the performance of segmented uniform distribution for perturbation vectors. For small- samples, we show that the Bernoulli distribution may not be the best for a certain choice of parameters.