Pareto Optimization with Robust Evaluation for Noisy Subset Selection

• URL: http://arxiv.org/abs/2501.06813v1
• Date: Sun, 12 Jan 2025 14:04:20 GMT
• Title: Pareto Optimization with Robust Evaluation for Noisy Subset Selection
• Authors: Yi-Heng Xu, Dan-Xuan Liu, Chao Qian,
• Abstract summary: Subset selection is a fundamental problem in optimization, which has a wide range of applications such as influence and sparse regression. Previous algorithms, including the greedy algorithm and evolutionary evolutionary POSS, either struggle in noisy environments or consume excessive computational resources. We propose a novel approach based on Pareto Optimization with Robust Evaluation for noisy subset selection (PORE), which maximizes a robust evaluation function and minimizes the subset size simultaneously.
• Score: 34.83487850400559
• License:
• Abstract: Subset selection is a fundamental problem in combinatorial optimization, which has a wide range of applications such as influence maximization and sparse regression. The goal is to select a subset of limited size from a ground set in order to maximize a given objective function. However, the evaluation of the objective function in real-world scenarios is often noisy. Previous algorithms, including the greedy algorithm and multi-objective evolutionary algorithms POSS and PONSS, either struggle in noisy environments or consume excessive computational resources. In this paper, we focus on the noisy subset selection problem with a cardinality constraint, where the evaluation of a subset is noisy. We propose a novel approach based on Pareto Optimization with Robust Evaluation for noisy subset selection (PORE), which maximizes a robust evaluation function and minimizes the subset size simultaneously. PORE can efficiently identify well-structured solutions and handle computational resources, addressing the limitations observed in PONSS. Our experiments, conducted on real-world datasets for influence maximization and sparse regression, demonstrate that PORE significantly outperforms previous methods, including the classical greedy algorithm, POSS, and PONSS. Further validation through ablation studies confirms the effectiveness of our robust evaluation function.

Related papers

• An Adaptive Re-evaluation Method for Evolution Strategy under Additive Noise [3.92625489118339]
  We propose a novel method to adaptively choose the optimal re-evaluation number for function values corrupted by additive Gaussian white noise. We experimentally compare our method to the state-of-the-art noise-handling methods for CMA-ES on a set of artificial test functions.
  arXiv  Detail & Related papers  (2024-09-25T09:10:21Z)
• Joint Entropy Search for Multi-objective Bayesian Optimization [0.0]
  We propose a novel information-theoretic acquisition function for BO called Joint Entropy Search. We showcase the effectiveness of this new approach on a range of synthetic and real-world problems in terms of the hypervolume and its weighted variants.
  arXiv  Detail & Related papers  (2022-10-06T13:19:08Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Bayesian multi-objective optimization for stochastic simulators: an extension of the Pareto Active Learning method [0.0]
  This article focuses on the multi-objective optimization of simulators with high output variance. We rely on Bayesian optimization algorithms to make predictions about the functions to be optimized.
  arXiv  Detail & Related papers  (2022-07-08T11:51:48Z)
• Algorithmic Foundations of Empirical X-risk Minimization [51.58884973792057]
  This manuscript introduces a new optimization framework machine learning and AI, named bf empirical X-risk baseline (EXM). X-risk is a term introduced to represent a family of compositional measures or objectives.
  arXiv  Detail & Related papers  (2022-06-01T12:22:56Z)
• Robust Subset Selection by Greedy and Evolutionary Pareto Optimization [23.0838604893412]
  Subset selection aims to select a subset from a ground set to maximize some objective function. We show that a greedy algorithm can obtain an approximation ratio of $1-e-betagamma$, where $beta$ and $gamma$ are the correlation and submodularity ratios of the objective functions.
  arXiv  Detail & Related papers  (2022-05-03T11:00:54Z)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  We consider the problem of searching an input maximizing a black-box objective function given a static dataset of input-output queries. A popular approach to solving this problem is maintaining a proxy model that approximates the true objective function. Here, the main challenge is how to avoid adversarially optimized inputs during the search.
  arXiv  Detail & Related papers  (2021-10-27T05:37:12Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• An Efficient Algorithm for Deep Stochastic Contextual Bandits [10.298368632706817]
  In contextual bandit problems, an agent selects an action based on certain observed context to maximize the reward over iterations. Recently there have been a few studies using a deep neural network (DNN) to predict the expected reward for an action, and is trained by a gradient based method.
  arXiv  Detail & Related papers  (2021-04-12T16:34:43Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.