論文の概要: Latent Guided Sampling for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2506.03672v1
• Date: Wed, 04 Jun 2025 08:02:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 21:20:14.217799
• Title: Latent Guided Sampling for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための潜在ガイドサンプリング
• Authors: Sobihan Surendran, Adeline Fermanian, Sylvain Le Corff,
• Abstract要約: 最近の組合せ最適化手法は、深層学習を利用して解法戦略を学習し、監視学習または強化学習(RL)を通して訓練されている。 有望ではあるが、これらのアプローチは多くの場合、タスク固有の拡張に依存し、配布外のインスタンスではパフォーマンスが悪く、堅牢な推論機構が欠如している。 本稿では,効率的な問題インスタンスを条件づけた新しい潜在空間モデルLGS-Netを提案するとともに,効率的なニューラル推論手法であるLatent Guided Sampling(LGS)を提案する。
• 参考スコア（独自算出の注目度）: 3.636090511738153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial Optimization problems are widespread in domains such as logistics, manufacturing, and drug discovery, yet their NP-hard nature makes them computationally challenging. Recent Neural Combinatorial Optimization methods leverage deep learning to learn solution strategies, trained via Supervised or Reinforcement Learning (RL). While promising, these approaches often rely on task-specific augmentations, perform poorly on out-of-distribution instances, and lack robust inference mechanisms. Moreover, existing latent space models either require labeled data or rely on pre-trained policies. In this work, we propose LGS-Net, a novel latent space model that conditions on problem instances, and introduce an efficient inference method, Latent Guided Sampling (LGS), based on Markov Chain Monte Carlo and Stochastic Approximation. We show that the iterations of our method form a time-inhomogeneous Markov Chain and provide rigorous theoretical convergence guarantees. Empirical results on benchmark routing tasks show that our method achieves state-of-the-art performance among RL-based approaches.
• Abstract（参考訳）: 組合せ最適化問題は、ロジスティクス、製造、薬物発見などの領域で広く使われているが、そのNPハード性は計算的に困難である。 最近のNeural Combinatorial Optimizationメソッドは、ディープラーニングを利用してソリューション戦略を学び、Supervised or Reinforcement Learning (RL)を通じてトレーニングされている。 有望ではあるが、これらのアプローチは多くの場合、タスク固有の拡張に依存し、配布外のインスタンスではパフォーマンスが悪く、堅牢な推論機構が欠如している。 さらに、既存の潜在空間モデルはラベル付きデータを必要とするか、事前訓練されたポリシーに依存している。 本稿では,問題インスタンスを条件づけた新しい潜在空間モデルLGS-Netを提案し,マルコフ・チェイン・モンテカルロと確率近似に基づく効率的な推論手法であるLatent Guided Smpling(LGS)を提案する。 我々は,本手法の反復が時間的不均一なマルコフ連鎖を形成し,厳密な理論的収束を保証することを示す。 ベンチマークルーティングタスクにおける実験結果から,本手法がRLに基づく手法の最先端性能を実現することを示す。

関連論文リスト

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  我々は,非平均場(NMF)変動推定フレームワークにアンサンブルカルマンフィルタ(EnKF)を導入し,潜在状態の後方分布を近似する。 EnKFとGPSSMのこの新しい結婚は、変分分布の学習における広範なパラメータ化の必要性をなくすだけでなく、エビデンスの下限(ELBO)の解釈可能でクローズドな近似を可能にする。 得られたEnKF支援オンラインアルゴリズムは、データ適合精度を確保しつつ、モデル正規化を組み込んで過度適合を緩和し、目的関数を具現化する。
  論文  参考訳（メタデータ） (2023-12-10T15:22:30Z)
• Observation-Guided Diffusion Probabilistic Models [41.749374023639156]
  観測誘導拡散確率モデル(OGDM)と呼ばれる新しい拡散に基づく画像生成法を提案する。 本手法は,観測プロセスの指導をマルコフ連鎖と統合することにより,トレーニング目標を再構築する。 本研究では,強力な拡散モデルベースライン上での多様な推論手法を用いたトレーニングアルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2023-10-06T06:29:06Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。 広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。 本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
  論文  参考訳（メタデータ） (2023-09-05T13:42:11Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Single-Trajectory Distributionally Robust Reinforcement Learning [21.955807398493334]
  本研究では,分散ロバストRL (DRRL) を提案する。 既存のDRRLアルゴリズムはモデルベースか、1つのサンプル軌道から学習できないかのいずれかである。 単一軌道を用いた分散ロバストQ-ラーニング(DRQ)と呼ばれる,完全モデルフリーなDRRLアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-01-27T14:08:09Z)
• Latent Variable Representation for Reinforcement Learning [131.03944557979725]
  モデルに基づく強化学習のサンプル効率を改善するために、潜在変数モデルが学習、計画、探索をいかに促進するかは理論上、実証上、不明である。 状態-作用値関数に対する潜在変数モデルの表現ビューを提供する。これは、抽出可能な変分学習アルゴリズムと楽観主義/悲観主義の原理の効果的な実装の両方を可能にする。 特に,潜伏変数モデルのカーネル埋め込みを組み込んだUPB探索を用いた計算効率の良い計画アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-12-17T00:26:31Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。