Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More

• URL: http://arxiv.org/abs/2405.08424v2
• Date: Fri, 24 May 2024 01:44:42 GMT
• Title: Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More
• Authors: Fanchen Bu, Hyeonsoo Jo, Soo Yong Lee, Sungsoo Ahn, Kijung Shin,
• Abstract summary: We aim to tackle prevalent (i.e., commonly involved) conditions in unsupervised CO. First, we concretize the targets for objective construction and derandomization with theoretical justification. Then, for various conditions commonly involved in different CO problems, we derive nontrivial objectives and derandomization to meet the targets.
• Score: 28.920691288421484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization (CO) is naturally discrete, making machine learning based on differentiable optimization inapplicable. Karalias & Loukas (2020) adapted the probabilistic method to incorporate CO into differentiable optimization. Their work ignited the research on unsupervised learning for CO, composed of two main components: probabilistic objectives and derandomization. However, each component confronts unique challenges. First, deriving objectives under various conditions (e.g., cardinality constraints and minimum) is nontrivial. Second, the derandomization process is underexplored, and the existing derandomization methods are either random sampling or naive rounding. In this work, we aim to tackle prevalent (i.e., commonly involved) conditions in unsupervised CO. First, we concretize the targets for objective construction and derandomization with theoretical justification. Then, for various conditions commonly involved in different CO problems, we derive nontrivial objectives and derandomization to meet the targets. Finally, we apply the derivations to various CO problems. Via extensive experiments on synthetic and real-world graphs, we validate the correctness of our derivations and show our empirical superiority w.r.t. both optimization quality and speed.

Related papers

• Causal Invariance Learning via Efficient Optimization of a Nonconvex Objective [12.423111378195667]
  We propose a novel method for finding causal relationships among variables. We show that our method converges to a standard gradient method. Our algorithm avoids exhaustive searches, making it especially when the number of covariants is large.
  arXiv  Detail & Related papers  (2024-12-16T15:11:02Z)
• A Performance Analysis of Basin Hopping Compared to Established Metaheuristics for Global Optimization [2.209921757303168]
  We perform numerical experiments using the IOH profiler environment with the BBOB test function set and two difficult real-world problems. Results show that Basin Hopping can be considered a good candidate for global numerical optimization problems along with the more established metaheuristics.
  arXiv  Detail & Related papers  (2024-03-09T11:02:47Z)
• Comparison of Single- and Multi- Objective Optimization Quality for Evolutionary Equation Discovery [77.34726150561087]
  Evolutionary differential equation discovery proved to be a tool to obtain equations with less a priori assumptions. The proposed comparison approach is shown on classical model examples -- Burgers equation, wave equation, and Korteweg - de Vries equation.
  arXiv  Detail & Related papers  (2023-06-29T15:37:19Z)
• 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)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  We show that the preferability of optimization methods depends critically on whether exact gradients are used. Second, to explain these findings we introduce the concept of committal rate for policy optimization. Third, we show that in the absence of external oracle information, there is an inherent trade-off between exploiting geometry to accelerate convergence versus achieving optimality almost surely.
  arXiv  Detail & Related papers  (2021-10-29T06:35:44Z)
• Optimization-based Causal Estimation from Heterogenous Environments [35.74340459207312]
  CoCo is an optimization algorithm that bridges the gap between pure prediction and causal inference. We describe the theoretical foundations of this approach and demonstrate its effectiveness on simulated and real datasets.
  arXiv  Detail & Related papers  (2021-09-24T14:21:58Z)
• 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)
• 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)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Practical Bayesian Optimization of Objectives with Conditioning Variables [1.0497128347190048]
  We consider the more general case where a user is faced with multiple problems that each need to be optimized conditional on a state variable. Similarity across objectives boosts optimization of each objective in two ways. We propose a framework for conditional optimization: ConBO.
  arXiv  Detail & Related papers  (2020-02-23T22:06:26Z)
• On the Performance of Metaheuristics: A Different Perspective [0.0]
  We study some basic evolutionary and swam-intelligence metaheuristics i.e. Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Teaching-Learning-Based Optimization (TLBO) and Cuckoo Optimization algorithm (COA) A large number of experiments have been conducted on 20 different optimization benchmark functions with different characteristics, and the results reveal to us some fundamental conclusions besides the following ranking order among these metaheuristics.
  arXiv  Detail & Related papers  (2020-01-24T09:34:10Z)

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.