Observations on the Feasibility of Exact Pareto Optimization

Reference. Cédric Saule and Robert Giegerich. 2014. Observations on the Feasibility of Exact Pareto Optimization. Proceedings of 1st workshop on Computational Methods for Structural RNAs (CMSR'14). isbn:978-2-9550187-0-5. pp. 43-56. doi:10.15455/CMSR.2014.0004
Abstract. Pareto optimization combines independent objectives by computing the Pareto front of its search space, defined as the set of all candidates whose scores are not dominated by others in at least one objective. This gives, in a precise sense, better information that an artificial amalgamation of different scores into a single objective, but is more costly to compute.
We define a general Pareto product operator *Par on scoring schemes. Independent of a particular algorithm, we prove that for two scoring schemes A and B used in dynamic programming, the scoring scheme A *Par B correctly performs Pareto optimization over the same search space. We show that a Pareto-eager implementation of dynamic programming can achieve the same asymptotics as a single-objective optimization which computes the same number of results. For a concrete application in RNA structure prediction, we show that the empirical size of the Pareto front remains within reasonable bounds. Without artificial amalgamation of objectives, and with no heuristics involved, Pareto optimization is faster than computing the same number of answers separately for each objective.
Presented at CMSR'14 (Strasbourg, France) on September 7th 2014 at 17:00 by Cédric Saule.

License information

Creative Commons LicenseThe proceedings of CMSR'14 are distributed under the terms of a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. Ownership of the copyright for the articles is retained by their authors. They allow anyone to download, reuse, reprint, distribute, and/or copy articles for any non-commercial purposes, provided that the original authors and source are appropriately cited.