Zero Order Algorithm for Decentralized Optimization Problems

Abstract In this paper we consider a distributed optimization problem in the black-box formulation. This means that the target function f is decomposed into the sum of $$n$$ functions $${{f}_{i}}$$ , where $$n$$ is the number of workers, it is assumed that each worker has access only to the zero-order noisy oracle, i.e., only to the values of $${{f}_{i}}(x)$$ with added noise. In this paper, we propose a new method based on the state-of-the-art distributed optimization algorithm MARINA . In particular, the following modifications are made to solve the problem in the black-box formulation: (i) we use approximations of the gradient instead of the true value, (ii) the difference of two approximated gradients at some coordinates is used instead of the compression operator. In this paper, a theoretical convergence analysis is provided for non-convex functions and functions satisfying the PL condition. The convergence rate of the proposed algorithm is correlated with the results for the algorithm that uses the first-order oracle. The theoretical results are validated in computational experiments to find optimal hyperparameters for the Resnet-18 neural network, that is trained on the CIFAR-10 dataset and the SVM model on the LibSVM library dataset and on the Mnist-784 dataset.