論文の概要: Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More
- arxiv url: http://arxiv.org/abs/2405.08424v2
- Date: Fri, 24 May 2024 01:44:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-27 20:17:43.063001
- Title: Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More
- Title（参考訳）: 教師なしの組合せ最適化における有意な条件に対処する: 心力、最小限、カバーなど
- Authors: Fanchen Bu, Hyeonsoo Jo, Soo Yong Lee, Sungsoo Ahn, Kijung Shin,
- Abstract要約: 我々は、非監督的なCOにおける一般的な(つまり、一般的に関与する)条件に取り組むことを目指している。
まず、客観的な構築とデランドマイズのための目標を理論的に正当化する。
次に, 異なるCO問題に共通する諸条件に対して, 非自明な目的と, 目的を満たすためのデランドマイズを導出する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 組合せ最適化(CO)は自然に独立しており、微分可能な最適化に基づく機械学習が適用できない。
Karalias & Loukas (2020) はCOを微分可能な最適化に組み込む確率的手法を採用した。
彼らの研究は、確率論的目的とデランドマイゼーションという2つの主要な構成要素からなる、COの教師なし学習の研究に火をつけた。
しかし、各コンポーネントは固有の課題に直面します。
まず、様々な条件(例えば、濃度制約、最小限)の下で目的を導出するのは自明ではない。
第二に、デランドマイズ法は未探索であり、既存のデランドマイズ法はランダムサンプリングかナイーブラウンドである。
本研究は、非監督的COにおける一般的な(一般的に関与する)条件に取り組むことを目的としている。
まず、客観的な構築とデランドマイズのための目標を理論的に正当化する。
次に, 異なるCO問題に共通する諸条件に対して, 非自明な目的と, 目的を満たすためのデランドマイズを導出する。
最後に,CO問題への導出について述べる。
合成グラフと実世界のグラフに関する広範な実験により、導出の正しさを検証し、最適化品質と速度の両方で経験的優位性を示す。
関連論文リスト
- A Performance Analysis of Basin Hopping Compared to Established
Metaheuristics for Global Optimization [2.209921757303168]
BBOBテスト関数セットと2つの困難な実世界の問題を用いたIOHプロファイラ環境を用いた数値実験を行った。
その結果, 流域ホッピングは, より確立されたメタヒューリスティクスとともに, 大域的な数値最適化問題の候補となる可能性が示唆された。
論文 参考訳（メタデータ） (2024-03-09T11:02:47Z) - Comparison of Single- and Multi- Objective Optimization Quality for
Evolutionary Equation Discovery [77.34726150561087]
進化的微分方程式の発見は、より優先順位の低い方程式を得るための道具であることが証明された。
提案した比較手法は、バーガーズ方程式、波動方程式、コルテヴェーグ・ド・ブリーズ方程式といった古典的なモデル例で示される。
論文 参考訳（メタデータ） (2023-06-29T15:37:19Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - Optimization-based Causal Estimation from Heterogenous Environments [35.74340459207312]
CoCoは、純粋な予測と因果推論のギャップを埋める最適化アルゴリズムである。
本稿では,本手法の理論的基礎を説明し,シミュレーションおよび実データに対する有効性を示す。
論文 参考訳（メタデータ） (2021-09-24T14:21:58Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - The Perils of Learning Before Optimizing [16.97597806975415]
本稿では,最適化タスクを通じて予測モデルを識別することで,エンドツーエンドで予測モデルを学習する方法を示す。
2段階のアプローチとエンドツーエンドのアプローチのパフォーマンスギャップは、最適化における相関の概念の強調と密接に関係していることが示される。
論文 参考訳（メタデータ） (2021-06-18T20:43:47Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Practical Bayesian Optimization of Objectives with Conditioning
Variables [1.0497128347190048]
ユーザが複数の問題に直面している場合、状態変数に対してそれぞれを条件付きで最適化する必要がある場合を考える。
目的間の類似性は、それぞれの目的を2つの方法で最適化する。
本稿では条件最適化のためのフレームワークであるConBOを提案する。
論文 参考訳（メタデータ） (2020-02-23T22:06:26Z) - On the Performance of Metaheuristics: A Different Perspective [0.0]
我々は,遺伝的アルゴリズム (GA), Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Teaching-Learning-Based Optimization (TLBO), Cuckoo Optimization Algorithm (COA) のいくつかの基本的な進化的およびスワム知能メタヒューリスティックスについて検討した。
異なる特性を持つ20種類の最適化ベンチマーク関数について多数の実験が行われており、これらのメタヒューリスティックスの中での次の順位の他に、いくつかの基本的な結論が示されている。
論文 参考訳（メタデータ） (2020-01-24T09:34:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。