Exact Pareto Optimal Search for Multi-Task Learning and Multi-Criteria Decision-Making

Given multiple non-convex objective functions and objective-specific weights, Chebyshev scalarization (CS) is a well-known approach to obtain an Exact Pareto Optimal (EPO), i.e., a solution on the Pareto front (PF) that intersects the ray defined by the inverse of the weights. First-order optimizers that use the CS formulation to find EPO solutions encounter practical problems of oscillations and stagnation that affect convergence. Moreover, when initialized with a PO solution, they do not guarantee a controlled trajectory that lies completely on the PF. These shortcomings lead to modeling limitations and computational inefficiency in multi-task learning (MTL) and multi-criteria decision-making (MCDM) methods that utilize CS for their underlying non-convex multi-objective optimization (MOO). To address these shortcomings, we design a new MOO method, EPO Search. We prove that EPO Search converges to an EPO solution and empirically illustrate its computational efficiency and robustness to initialization. When initialized on the PF, EPO Search can trace the PF and converge to the required EPO solution at a linear rate of convergence. Using EPO Search we develop new algorithms: PESA-EPO for approximating the PF in a posteriori MCDM, and GP-EPO for preference elicitation in interactive MCDM; experiments on benchmark datasets confirm their advantages over competing alternatives. EPO Search scales linearly with the number of decision variables which enables its use for training deep networks. Empirical results on real data from personalized medicine, e-commerce and hydrometeorology demonstrate the efficacy of EPO Search for deep MTL.