Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization
Abhishek Roy, Geelon So, Yian Ma
In multi-objective optimization, a single decision vector must balance the  trade-offs between many objectives. Solutions achieving an optimal trade-off  are said to be Pareto optimal---these are decision vectors for which improving  any one objective must come at a cost to another. Many decisions can be Pareto  optimal, so when the decision maker can choose only one, this raises questions  of which solution to pick and how. We formulate the problem as *Pareto-constrained optimization*, where the goal is to optimize a  preference function constrained to a set of Pareto optimal solutions.     This constrained optimization problem poses significant challenges: not only is the constraint set  defined implicitly, but it is also generally non-convex and non-smooth, even when the objectives are strongly convex. We propose a reformulation of the problem where the constraint set is redefined in terms of an appropriately defined manifold. This reformulation allows us to introduce a clearer and more accurate notion of optimality and stationarity, improving upon existing definitions in the literature. We provide an algorithm with a last-iterate convergence rate of $O(  K^{-1/2})$ to this notion of stationarity when the preference function is Lipschitz smooth and when the objective functions are strongly convex and Lipschitz smooth. Moreover, motivated by practical applications like Reinforcement Learning with Human Feedback (RLHF), we extend this algorithm to tackle the case where the preference function can only be queried via dueling feedback.