[2604.01098] Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization

Computer Science > Machine Learning arXiv:2604.01098 (cs) [Submitted on 1 Apr 2026] Title:Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization Authors:Jinzhao Li, Nan Jiang, Yexiang Xue View a PDF of the paper titled Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization, by Jinzhao Li and 2 other authors View PDF HTML (experimental) Abstract:Stochastic Multi-Objective Optimization (SMOO) is critical for decision-making trading off multiple potentially conflicting objectives in uncertain environments. SMOO aims at identifying the Pareto frontier, which contains all mutually non-dominating decisions. The problem is highly intractable due to the embedded probabilistic inference, such as computing the marginal, posterior probabilities, or expectations. Existing methods, such as scalarization, sample average approximation, and evolutionary algorithms, either offer arbitrarily loose approximations or may incur prohibitive computational costs. We propose XOR-SMOO, a novel algorithm that with probability $1-\delta$, obtains $\gamma$-approximate Pareto frontiers ($\gamma>1$) for SMOO by querying an SAT oracle poly-log times in $\gamma$ and $\delta$. A $\gamma$-approximate Pareto frontier is only below the true frontier by a fixed, multiplicative factor $\gamma$. Thus, XOR-SMOO solves highly intractable SMOO problems (\#P-hard) with only queries to SAT oracles while obtaining tight, ...