Solving a multicriteria optimization problem requires finding a whole set of independent variables corresponding to non-dominated criteria values (Pareto set). The complexity of these problems increases significantly in the case when the criteria are multiextremal. The paper presents several variations of the global optimization algorithm intended for approximate solving “black-box” multiobjective problems with multiextremal criteria. The proposed methods are based on a combination of the information-statistical approach and machine learning procedures aimed at increasing the efficiency of constructing the Pareto set approximation. As a novelty, the paper describes a new approach to using machine learning models within the algorithm of multicriteria optimization. Based on a representative computational experiment, the effectiveness of different versions of the proposed algorithm is estimated.