Asynchronous classification-based optimization

Asynchronous parallelization is an effective way to accelerate optimization. While asynchronous parallelization can destroy the sequential structure of optimization algorithms, it has been found counter-intuitively that some optimization algorithms are proven to preserve their performance under asynchronous parallelization, including the stochastic gradient descent for first-order optimization of differentiable functions and Pareto optimization for zeroth-order optimization in binary space. Following this direction, in this paper, we show that the classification-based optimization, which is a recently developed framework for zeroth-order optimization in continuous space, can also enjoy the asynchronous parallelization. We implement ASRacos, an asynchronous version of a classification-based optimization algorithm SRacos, to accelerate the optimization through asynchronous parallelization. We theoretically provide the query complexity of ASRacos and further show that on certain conditions, ASRacos can achieve a better performance than SRacos even if using the same number of evaluations. Experiments on synthetic functions and controlling tasks in OpenAI Gym demonstrate that ASRacos can achieve almost linear speedup while preserving good solution quality.