A Hybrid 2-stage Neural Optimization for Pareto Front Extraction
- URL: http://arxiv.org/abs/2101.11684v2
- Date: Sat, 13 Feb 2021 17:03:10 GMT
- Title: A Hybrid 2-stage Neural Optimization for Pareto Front Extraction
- Authors: Gurpreet Singh, Soumyajit Gupta, Matthew Lease, Clint Dawson
- Abstract summary: A major obstacle to optimal trade-off solutions is that they don't always converge to each other.
We propose a two-stage approach that is accurate and cost-effective.
- Score: 3.918940900258555
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Classification, recommendation, and ranking problems often involve competing
goals with additional constraints (e.g., to satisfy fairness or diversity
criteria). Such optimization problems are quite challenging, often involving
non-convex functions along with considerations of user preferences in balancing
trade-offs. Pareto solutions represent optimal frontiers for jointly optimizing
multiple competing objectives. A major obstacle for frequently used
linear-scalarization strategies is that the resulting optimization problem
might not always converge to a global optimum. Furthermore, such methods only
return one solution point per run. A Pareto solution set is a subset of all
such global optima over multiple runs for different trade-off choices.
Therefore, a Pareto front can only be guaranteed with multiple runs of the
linear-scalarization problem, where all runs converge to their respective
global optima. Consequently, extracting a Pareto front for practical problems
is computationally intractable with substantial computational overheads,
limited scalability, and reduced accuracy. We propose a robust, low cost,
two-stage, hybrid neural Pareto optimization approach that is accurate and
scales (compute space and time) with data dimensions, as well as number of
functions and constraints. The first stage (neural network) efficiently
extracts a weak Pareto front, using Fritz-John conditions as the discriminator,
with no assumptions of convexity on the objectives or constraints. The second
stage (efficient Pareto filter) extracts the strong Pareto optimal subset given
the weak front from stage 1. Fritz-John conditions provide us with theoretical
bounds on approximation error between the true and network extracted weak
Pareto front. Numerical experiments demonstrates the accuracy and efficiency on
a canonical set of benchmark problems and a fairness optimization task from
prior works.
Related papers
- Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings [7.6275971668447005]
We tackle the problem of computing a sequence of rankings with the guarantee of the Pareto-optimal balance between consumers and producers of items.
We introduce a novel approach to the above problem by using the Expohedron - a permutahedron whose points represent all exposures of items.
We further propose an efficient method by relaxing our optimization problem on the Expohedron's circumscribed $n$-sphere, which significantly improve the running time.
arXiv Detail & Related papers (2024-02-22T05:48:54Z) - Optimization on Pareto sets: On a theory of multi-objective optimization [7.907376287850398]
In multi-objective optimization, a single decision vector must balance the trade-offs between many objectives.
We consider a more practically significant optimization problem, where the goal is to optimize a constrained set.
arXiv Detail & Related papers (2023-08-04T05:55:52Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Polynomial Optimization: Enhancing RLT relaxations with Conic
Constraints [0.0]
Conic optimization has emerged as a powerful tool for designing tractable and guaranteed algorithms for non-scale problems.
We investigate the strengthening of the RLT relaxations of optimization problems through the addition of nine different types of constraints.
We show how to design these variants and their performance with respect to each other and with respect to the standard RLT relaxations.
arXiv Detail & Related papers (2022-08-11T02:13:04Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints.
A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual.
This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
arXiv Detail & Related papers (2021-10-20T02:57:21Z) - Pareto Navigation Gradient Descent: a First-Order Algorithm for
Optimization in Pareto Set [17.617944390196286]
Modern machine learning applications, such as multi-task learning, require finding optimal model parameters to trade-off multiple objective functions.
We propose a first-order algorithm that approximately solves OPT-in-Pareto using only gradient information.
arXiv Detail & Related papers (2021-10-17T04:07:04Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
It is essential to theoretically guarantee that algorithms provide small objective residual with high probability.
Existing methods for non-smooth convex optimization have complexity with bounds dependence on the confidence level that is either negative-power or logarithmic.
We propose novel stepsize rules for two gradient methods with clipping.
arXiv Detail & Related papers (2021-06-10T17:54:21Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
arXiv Detail & Related papers (2020-12-11T08:28:51Z) - Extracting Optimal Solution Manifolds using Constrained Neural
Optimization [6.800113407368289]
Constrained Optimization solution algorithms are restricted to point based solutions.
We present an approach for extracting optimal sets as approximate, where unmodified non-informed constraints are defined.
arXiv Detail & Related papers (2020-09-13T15:37:44Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope.
Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
arXiv Detail & Related papers (2020-06-11T17:43:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.