Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints

• URL: http://arxiv.org/abs/2406.12383v2
• Date: Mon, 9 Sep 2024 07:37:07 GMT
• Title: Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints
• Authors: Dan-Xuan Liu, Chao Qian,
• Abstract summary: Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget. We propose BPODC, enhancing POMC with biased selection and warm-up strategies tailored for dynamic environments.
• Score: 23.67466377818849
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget, which has various applications such as influence maximization and maximum coverage. In real-world scenarios, the budget, representing available resources, may change over time, which requires that algorithms must adapt quickly to new budgets. However, in this dynamic environment, previous algorithms either lack theoretical guarantees or require a long running time. The state-of-the-art algorithm, POMC, is a Pareto optimization approach designed for static problems, lacking consideration for dynamic problems. In this paper, we propose BPODC, enhancing POMC with biased selection and warm-up strategies tailored for dynamic environments. We focus on the ability of BPODC to leverage existing computational results while adapting to budget changes. We prove that BPODC can maintain the best known $(\alpha_f/2)(1-e^{-\alpha_f})$-approximation guarantee when the budget changes. Experiments on influence maximization and maximum coverage show that BPODC adapts more effectively and rapidly to budget changes, with a running time that is less than that of the static greedy algorithm.

Related papers

• A Perturbation and Speciation-Based Algorithm for Dynamic Optimization Uninformed of Change [1.4425878137951238]
  Perturbation and Speciation-Based Particle Swarm Optimization (PSPSO) is a robust algorithm for uninformed dynamic optimization.<n> PSPSO combines speciation-based niching, deactivation, and a newly proposed random perturbation mechanism to handle DOPs.<n> PSPSO shows strength in functions with high dimensionality or high frequency of change in the Generalized Moving Peaks Benchmark.
  arXiv  Detail & Related papers  (2025-05-16T18:53:37Z)
• New Additive OCBA Procedures for Robust Ranking and Selection [0.9558392439655016]
  We develop new fixed-budget robust R&S procedures to minimize the probability of incorrect selection under a limited sampling budget. We then conduct a comprehensive numerical study to verify the superiority of our robust OCBA procedure over existing ones.
  arXiv  Detail & Related papers  (2024-12-08T18:42:07Z)
• An accelerate Prediction Strategy for Dynamic Multi-Objective Optimization [7.272641346606365]
  We introduce novel approaches for accelerating prediction strategies within the evolutionary algorithm framework. We propose an adaptive prediction strategy that incorporates second-order derivatives to predict and adjust the algorithms search behavior. We evaluate the performance of the proposed method against four state-of-the-art algorithms using standard DMOPs benchmark problems.
  arXiv  Detail & Related papers  (2024-10-08T08:13:49Z)
• An adaptive approach to Bayesian Optimization with switching costs [0.8246494848934447]
  We investigate modifications to Bayesian Optimization for a resource-constrained setting of sequential experimental design. We adapt two process-constrained batch algorithms to this sequential problem formulation, and propose two new methods: one cost-aware and one cost-ignorant.
  arXiv  Detail & Related papers  (2024-05-14T21:55:02Z)
• Stochastic Multi-round Submodular Optimization with Budget [7.902059578326225]
  We aim to adaptively maximize the sum, over multiple rounds, of a monotone submodular objective function defined on subsets of items. The objective function also depends on the realization of events, and the total number of items we can select over all rounds is bounded by a limited budget.
  arXiv  Detail & Related papers  (2024-04-21T18:24:43Z)
• Welfare Maximization Algorithm for Solving Budget-Constrained Multi-Component POMDPs [2.007262412327553]
  This paper presents an algorithm to find the optimal policy for a multi-component budget-constrained POMDP. We show that the proposed algorithm vastly outperforms the policy currently used in practice.
  arXiv  Detail & Related papers  (2023-03-18T01:43:47Z)
• 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)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs) We propose the underlineperiodically underlinerestarted underlineoptimistic underlinepolicy underlineoptimization algorithm (PROPO) PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement.
  arXiv  Detail & Related papers  (2021-10-18T02:33:20Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  Batch policy optimization considers leveraging existing data for policy construction before interacting with an environment. We show that any confidence-adjusted index algorithm is minimax optimal, whether it be optimistic, pessimistic or neutral. We introduce a new weighted-minimax criterion that considers the inherent difficulty of optimal value prediction.
  arXiv  Detail & Related papers  (2021-04-06T05:23:20Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)
• Provably Efficient Exploration in Policy Optimization [117.09887790160406]
  This paper proposes an Optimistic variant of the Proximal Policy Optimization algorithm (OPPO) OPPO achieves $tildeO(sqrtd2 H3 T )$ regret. To the best of our knowledge, OPPO is the first provably efficient policy optimization algorithm that explores.
  arXiv  Detail & Related papers  (2019-12-12T08:40:02Z)

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.