論文の概要: Variational Annealing on Graphs for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2311.14156v1
- Date: Thu, 23 Nov 2023 18:56:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-27 16:24:50.586210
- Title: Variational Annealing on Graphs for Combinatorial Optimization
- Title(参考訳): 組合せ最適化のためのグラフ上の変分アニーリング
- Authors: Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, Sebastian
Lehner
- Abstract要約: 解変数間の統計的依存関係を捉える自己回帰的手法は,多くのCO問題に対して優れた性能を示すことを示す。
本稿では,一組の解変数の構成を単一トークンで表すサブグラフトークン化を提案する。
- 参考スコア(独自算出の注目度): 7.378582040635655
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several recent unsupervised learning methods use probabilistic approaches to
solve combinatorial optimization (CO) problems based on the assumption of
statistically independent solution variables. We demonstrate that this
assumption imposes performance limitations in particular on difficult problem
instances. Our results corroborate that an autoregressive approach which
captures statistical dependencies among solution variables yields superior
performance on many popular CO problems. We introduce subgraph tokenization in
which the configuration of a set of solution variables is represented by a
single token. This tokenization technique alleviates the drawback of the long
sequential sampling procedure which is inherent to autoregressive methods
without sacrificing expressivity. Importantly, we theoretically motivate an
annealed entropy regularization and show empirically that it is essential for
efficient and stable learning.
- Abstract(参考訳): いくつかの非教師なし学習手法は確率論的手法を用いて統計的に独立な解変数の仮定に基づいて組合せ最適化(CO)問題を解決する。
この仮定が特に難しい問題インスタンスにパフォーマンス上の制限を課すことを実証する。
その結果, 解変数間の統計的依存関係を捉える自己回帰的手法は, 多くのCO問題に対して優れた性能を示すことがわかった。
本稿では,ソリューション変数の集合の構成を単一のトークンで表現するサブグラフトークン化を導入する。
このトークン化技術は、表現性を犠牲にすることなく自己回帰法固有の長いシーケンシャルサンプリング手順の欠点を軽減する。
重要なのは、理論上、アニールエントロピー正規化を動機付け、効率的で安定した学習に必須であることを実証的に示すことである。
関連論文リスト
- Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
最近の構造化学習手法のストリームは、様々な最適化問題に対する技術の実践的状態を改善している。
鍵となる考え方は、インスタンスを別々に扱うのではなく、インスタンス上の統計分布を利用することだ。
本稿では,最適化を容易にし,一般化誤差を改善するポリシを摂動することでリスクを円滑にする手法について検討する。
論文 参考訳(メタデータ) (2024-07-24T12:00:30Z) - Distributionally Robust Model-based Reinforcement Learning with Large
State Spaces [55.14361269378122]
強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。
広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。
本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
論文 参考訳(メタデータ) (2023-09-05T13:42:11Z) - Resource-Adaptive Newton's Method for Distributed Learning [16.588456212160928]
本稿では,Newtonの手法の限界を克服するRANLというアルゴリズムを提案する。
従来の一階法とは異なり、RANLは問題の条件数から著しく独立している。
論文 参考訳(メタデータ) (2023-08-20T04:01:30Z) - Debiasing Conditional Stochastic Optimization [15.901623717313493]
本稿では,ポートフォリオ選択や強化学習,堅牢な学習など,さまざまな応用をカバーする条件因果最適化(CSO)問題について検討する。
有限変量変量CSO問題に対する新しいアルゴリズムを開発し、既存の結果を大幅に改善する。
我々は,本手法が他の最適化問題と同様の課題に対処するための有用なツールとなる可能性があると考えている。
論文 参考訳(メタデータ) (2023-04-20T19:19:55Z) - Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。
解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
論文 参考訳(メタデータ) (2023-03-31T02:10:30Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳(メタデータ) (2022-11-14T21:54:31Z) - SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum
Cocoercive Variational Inequalities [137.6408511310322]
有限サムコヒーレンシブ変分不等式の問題を考える。
強い単調な問題に対しては、この方法を用いて解への線形収束を達成することができる。
論文 参考訳(メタデータ) (2022-10-12T08:04:48Z) - Data-driven Prediction of Relevant Scenarios for Robust Optimization [0.0]
離散的な不確実性集合を持つロバストな1段階と2段階の問題について検討する。
本稿では,一連の開始シナリオで反復解法をシード化するデータ駆動型計算を提案する。
実験の結果,提案手法によって少数の優れたスタートシナリオを予測しても,反復的手法の時間を大幅に短縮できることがわかった。
論文 参考訳(メタデータ) (2022-03-30T19:52:29Z) - Differentiable Causal Discovery from Interventional Data [141.41931444927184]
本稿では、介入データを活用可能なニューラルネットワークに基づく理論的基盤化手法を提案する。
提案手法は,様々な環境下での美術品の状態と良好に比較できることを示す。
論文 参考訳(メタデータ) (2020-07-03T15:19:17Z) - Statistically Guided Divide-and-Conquer for Sparse Factorization of
Large Matrix [2.345015036605934]
統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。
第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。
第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
論文 参考訳(メタデータ) (2020-03-17T19:12:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。