Abstract:
In this paper we consider a distributed optimisation problem in the black-box formulation. This means that the target function $f$ is decomposed into the sum of $n$ functions $f$, where $n$ is the number of workers, where each worker is assumed to have access only to the zero-order noisy oracle, i.e., only to the values of $f (x)$ with added noise. In this paper, we propose a new ZO-MARINA method based on the state-of-the-art MARINA distributed optimization algorithm. In particular, the following modifications are made to solve the problem in the black-box formulation: i) its approximation is used instead of the honest gradient, 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 Polak–Lojasiewicz condition. The speed of the proposed algorithm is correlated with the results for an algorithm that uses a first-order oracle. The theoretical results are validated in computational experiments to find optimal hyperparameters for the Resnet-18 neural network when trained on the CIFAR-10 dataset and the SVM model on the LibSVM library dataset and on the Mnist-784 dataset.
