Gradient Ascent in Multi-Objective Minimization: Applications in Machine Learning
Dr Vaibhav Rajan, Assistant Professor, School of Computing
Abstract:
Multi-objective optimization (MOO) problems arise in many domains where intelligent systems need to balance conflicting objectives. In such scenarios, Decision makers (DM) require a Pareto optimal (PO) solution that strikes a suitable trade-off among the objectives. They rely on MOO solvers to explore the Pareto front (PF), the set of all possible PO solutions. Existing methods primarily focus on solving convex MOO problems. However, real-world applications often involve non-convex training objectives in high-dimensional parameter spaces. Therefore, lack of non-convex MOO solver poses a challenge in modelling practical intelligent systems.
We address a fundamental shortcoming in the existing optimization methods. They are sensitive to the starting point, which may cause premature stagnation at a sub-optimal solution before reaching to the solution that complies with the trade-off requirement. To address this, we propose a scalable algorithm, namely Exact Pareto Optimal (EPO) Search, which uses controlled gradient ascent in addition to the usual gradient descent, to minimize multiple non-convex objectives simultaneously. EPO Search can not only converge to a trade-off specific PO solution from random initialization, but also navigate the non-convex PF by tracing from one PO solution to another at a linear rate of convergence. We show its usefulness in many decision making scenarios and machine learning (ML) applications.
We apply EPO Search in two types of ML applications: Multi-Task Learning (MTL), where a deep neural network model is trained to perform multiple tasks, and multi-criteria Learning to Rank (LTR), where a gradient-boosted-decision-tree model is trained to rank a list of items based on multiple criteria, such as relevance and fairness. We evaluate our method on three real-world datasets from different domains (such as personalized medicine, e-commerce and hydrometeorology) for the MTL application and four search-ranking datasets for the LTR application. In all cases, our algorithm provides competitive performance in comparison to existing MOO algorithms, demonstrating its effectiveness in practical applications.
We extend the PF tracing ability of EPO Search for Multi-Criteria Decision Making (MCDM) to find a PO solution corresponding to a DM's unknown preference or utility function. We propose two algorithms that contribute to two types of MCDM scenarios: 1) A posteriori MCDM, where an approximate PF is presented to the DM; and 2) Interactive MCDM, where the DM interacts with the system to find his/her most preferred solution progressively. Empirical evaluation of the extended EPO Search algorithms on six benchmarks MOO problems demonstrate significant improvement over the state-of-the-art in both techniques: for a posteriori MCDM, it achieves higher PF approximation accuracy faster. For interactive MCDM, it achieves lower regret w.r.t. the (oracle) preferred solution.