Solving problems of multi-criteria optimization involves finding many combinations of optimization parameters, in which the values of the criteria cannot be improved in several criteria at once without worsening the values of the remaining ones (Pareto set). In the framework of the research, several assumptions were introduced: criteria are multiextremal and difficult to calculate, presented in the form of a “black box”, and the number of optimized parameters is small. The paper presents a method for solving this class of problems based on the information-statistical approach and a machine learning procedure used to increase search efficiency. A parallel implementation of the method is described, which is supplemented with the ability to perform calculations in asynchronous parallel mode. The efficiency and scalability of the proposed algorithm is analyzed on the base of solving a test class of multiextremal problems.