This paper investigates how to accelerate the convergence of distributed optimization algorithms on nonconvex problems with zeroth-order information available only. We propose a zeroth-order (ZO) distributed primal-dual stochastic coordinates algorithm equipped with "powerball" method to accelerate. We prove that the proposed algorithm has a convergence rate of $\mathcal{ O}(\sqrt{ p}/\sqrt{ nT})$ for general nonconvex cost functions. We consider solving the generation of adversarial examples from black-box DNNs problem to compare with the existing state-of-the-art centralized and distributed ZO algorithms. The numerical results demonstrate the faster convergence rate of the proposed algorithm and match the theoretical analysis.

Categories: math.OC

Accelerated Zeroth-order Algorithm for Stochastic Distributed Nonconvex Optimization