DSPG: Decentralized Simultaneous Perturbations Gradient Descent Scheme
  Distributed descent-based methods are an essential toolset to solving
optimization problems in multi-agent system scenarios. Here the agents seek to
optimize a global objective function through mutual cooperation. Oftentimes,
cooperation is achieved over a wireless communication network that is prone to
delays and errors. There are many scenarios wherein the objective function is
either non-differentiable or merely observable. In this paper, we present a
cross-entropy based distributed stochastic approximation algorithm (SA) that
finds a minimum of the objective, using only samples. We call this algorithm
Decentralized Simultaneous Perturbation Stochastic Gradient, with Constant
Sensitivity Parameters (DSPG). This algorithm is a two fold improvement over
the classic Simultaneous Perturbation Stochastic Approximations (SPSA)
algorithm. Specifically, DSPG allows for (i) the use of old information from
other agents and (ii) easy implementation through the use simple
hyper-parameter choices. We analyze the biases and variances that arise due to
these two allowances. We show that the biases due to communication delays can
be countered by a careful choice of algorithm hyper-parameters. The variance of
the gradient estimator and its effect on the rate of convergence is studied. We
present numerical results supporting our theory. Finally, we discuss an
application to the stochastic consensus problem.
