DSPG: Decentralized Simultaneous Perturbations Gradient Descent Scheme
This work addresses optimization challenges in decentralized multi-agent systems, such as robotics or sensor networks, but is incremental as it builds on existing SPSA methods.
The paper tackles the problem of distributed optimization in multi-agent systems with non-differentiable or observable objective functions over error-prone networks, presenting the DSPG algorithm that improves upon SPSA by allowing old information use and simpler hyper-parameters, with analysis showing biases from delays can be mitigated and numerical results supporting the theory.
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.