On the Robustness of Lexicase Selection to Contradictory Objectives

• URL: http://arxiv.org/abs/2403.06805v1
• Date: Mon, 11 Mar 2024 15:23:35 GMT
• Title: On the Robustness of Lexicase Selection to Contradictory Objectives
• Authors: Shakiba Shahbandegan, Emily Dolson
• Abstract summary: We study lexicase and epsilon-lexicase selection's performance on contradictory objectives. We find that lexicase and epsilon-lexicase selection each have a region of parameter space where they are incapable of optimizing contradictory objectives. We propose theoretically-backed guidelines for parameter choice.
• Score: 0.9208007322096533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lexicase and epsilon-lexicase selection are state of the art parent selection techniques for problems featuring multiple selection criteria. Originally, lexicase selection was developed for cases where these selection criteria are unlikely to be in conflict with each other, but preliminary work suggests it is also a highly effective many-objective optimization algorithm. However, to predict whether these results generalize, we must understand lexicase selection's performance on contradictory objectives. Prior work has shown mixed results on this question. Here, we develop theory identifying circumstances under which lexicase selection will succeed or fail to find a Pareto-optimal solution. To make this analysis tractable, we restrict our investigation to a theoretical problem with maximally contradictory objectives. Ultimately, we find that lexicase and epsilon-lexicase selection each have a region of parameter space where they are incapable of optimizing contradictory objectives. Outside of this region, however, they perform well despite the presence of contradictory objectives. Based on these findings, we propose theoretically-backed guidelines for parameter choice. Additionally, we identify other properties that may affect whether a many-objective optimization problem is a good fit for lexicase or epsilon-lexicase selection.

Related papers

• Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization [9.838618121102053]
  In real-world applications, users often favor structurally diverse design choices over one high-quality solution. This paper presents a fresh perspective on this challenge by considering the problem of identifying a fixed number of solutions with a pairwise distance above a specified threshold.
  arXiv  Detail & Related papers  (2024-08-29T09:55:55Z)
• Detecting and Identifying Selection Structure in Sequential Data [53.24493902162797]
  We argue that the selective inclusion of data points based on latent objectives is common in practical situations, such as music sequences. We show that selection structure is identifiable without any parametric assumptions or interventional experiments. We also propose a provably correct algorithm to detect and identify selection structures as well as other types of dependencies.
  arXiv  Detail & Related papers  (2024-06-29T20:56:34Z)
• In Search of Insights, Not Magic Bullets: Towards Demystification of the Model Selection Dilemma in Heterogeneous Treatment Effect Estimation [92.51773744318119]
  This paper empirically investigates the strengths and weaknesses of different model selection criteria. We highlight that there is a complex interplay between selection strategies, candidate estimators and the data used for comparing them.
  arXiv  Detail & Related papers  (2023-02-06T16:55:37Z)
• Calculating lexicase selection probabilities is NP-Hard [0.0]
  I prove that this problem, which I name lex-prob, is NP-Hard. I achieve this proof by reducing SAT, a well-known NP-Complete problem, to lex-prob in time.
  arXiv  Detail & Related papers  (2023-01-17T06:51:44Z)
• Bi-objective Ranking and Selection Using Stochastic Kriging [0.0]
  We consider bi-objective ranking and selection problems in which the two objective outcomes have been observed with uncertainty. We propose a novel Bayesian bi-objective ranking and selection method that sequentially allocates extra samples to competitive solutions. Experimental results show that the proposed method outperforms the standard allocation method, as well as a well-known state-of-the-art algorithm.
  arXiv  Detail & Related papers  (2022-09-05T23:51:07Z)
• Bounding Counterfactuals under Selection Bias [60.55840896782637]
  We propose a first algorithm to address both identifiable and unidentifiable queries. We prove that, in spite of the missingness induced by the selection bias, the likelihood of the available data is unimodal.
  arXiv  Detail & Related papers  (2022-07-26T10:33:10Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• 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)
• An Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality [62.997667081978825]
  We introduce an "exploration diagnostic" that diagnoses a selection scheme's capacity for search space exploration. We verify that lexicase selection out-explores tournament selection. We find that relaxing lexicase's elitism with epsilon lexicase can further improve exploration.
  arXiv  Detail & Related papers  (2021-07-20T20:43:06Z)
• 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)
• Solution Subset Selection for Final Decision Making in Evolutionary Multi-Objective Optimization [7.745468825770201]
  We discuss subset selection from a viewpoint of the final decision making. We show that the formulated function is the same as the IGD plus indicator.
  arXiv  Detail & Related papers  (2020-06-15T06:26:58Z)

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.