論文の概要: Learning-Based TSP-Solvers Tend to Be Overly Greedy

• arxiv url: http://arxiv.org/abs/2502.00767v1
• Date: Sun, 02 Feb 2025 12:06:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:01:24.319301
• Title: Learning-Based TSP-Solvers Tend to Be Overly Greedy
• Title（参考訳）: 学習ベースのTSP-Solvers、悲嘆に暮れる
• Authors: Xiayang Li, Shihua Zhang,
• Abstract要約: 本研究では, ランダムに生成した学習型解法の性質を検証するため, 最近傍密度と呼ばれる統計的尺度を構築した。 学習に基づく解法の性能が、そのような拡張データに大きく依存していることを検証する。 要するに、学習ベースのTSPソルバの限界は、過度に欲求的になりがちであり、AIを活用した最適化ソルバに深く影響する可能性がある。
• 参考スコア（独自算出の注目度）: 8.79364699260219
• License:
• Abstract: Deep learning has shown significant potential in solving combinatorial optimization problems such as the Euclidean traveling salesman problem (TSP). However, most training and test instances for existing TSP algorithms are generated randomly from specific distributions like uniform distribution. This has led to a lack of analysis and understanding of the performance of deep learning algorithms in out-of-distribution (OOD) generalization scenarios, which has a close relationship with the worst-case performance in the combinatorial optimization field. For data-driven algorithms, the statistical properties of randomly generated datasets are critical. This study constructs a statistical measure called nearest-neighbor density to verify the asymptotic properties of randomly generated datasets and reveal the greedy behavior of learning-based solvers, i.e., always choosing the nearest neighbor nodes to construct the solution path. Based on this statistical measure, we develop interpretable data augmentation methods that rely on distribution shifts or instance perturbations and validate that the performance of the learning-based solvers degenerates much on such augmented data. Moreover, fine-tuning learning-based solvers with augmented data further enhances their generalization abilities. In short, we decipher the limitations of learning-based TSP solvers tending to be overly greedy, which may have profound implications for AI-empowered combinatorial optimization solvers.
• Abstract（参考訳）: 深層学習はユークリッド旅行セールスマン問題(TSP)のような組合せ最適化問題の解決に大きな可能性を示している。 しかし、既存のTSPアルゴリズムのほとんどのトレーニングとテストインスタンスは、一様分布のような特定の分布からランダムに生成される。 これにより、組合わせ最適化分野における最悪の性能と密接な関係を持つOOD(out-of-distriion)一般化シナリオにおけるディープラーニングアルゴリズムの性能の分析と理解が欠如している。 データ駆動アルゴリズムでは、ランダムに生成されたデータセットの統計特性が重要である。 本研究は, ランダムに生成したデータセットの漸近特性を検証するため, 近接近傍密度と呼ばれる統計的尺度を構築し, 学習ベースソルバの欲求的挙動を明らかにする。 この統計的尺度に基づいて,分散シフトやインスタンスの摂動に依存する解釈可能なデータ拡張手法を開発し,学習に基づく解法の性能がそのような拡張データに大きく依存していることを検証する。 さらに、拡張データを用いた微調整学習に基づく解法により、さらに一般化能力が向上する。 要するに、学習ベースのTSPソルバの限界は、過度に欲求的になりがちであり、AIを駆使した組合せ最適化ソルバに重大な影響を及ぼす可能性がある。

関連論文リスト

• Analysis and Optimization of Wireless Federated Learning with Data Heterogeneity [72.85248553787538]
  本稿では、データの不均一性を考慮した無線FLの性能解析と最適化と、無線リソース割り当てについて述べる。 ロス関数の最小化問題を、長期エネルギー消費と遅延の制約の下で定式化し、クライアントスケジューリング、リソース割り当て、ローカルトレーニングエポック数(CRE)を共同で最適化する。 実世界のデータセットの実験により、提案アルゴリズムは学習精度とエネルギー消費の点で他のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-08-04T04:18:01Z)
• Personalized Decentralized Multi-Task Learning Over Dynamic Communication Graphs [59.96266198512243]
  本稿では,正と負の相関関係を持つタスクに対する分散・フェデレーション学習アルゴリズムを提案する。 本アルゴリズムでは,タスク間の相関関係を自動的に計算し,コミュニケーショングラフを動的に調整して相互に有益なタスクを接続し,互いに悪影響を及ぼす可能性のあるタスクを分離する。 合成ガウスデータセットと大規模セレブ属性(CelebA)データセットについて実験を行った。
  論文  参考訳（メタデータ） (2022-12-21T18:58:24Z)
• On the Generalization for Transfer Learning: An Information-Theoretic Analysis [8.102199960821165]
  一般化誤差と転帰学習アルゴリズムの過大なリスクを情報理論で解析する。 我々の結果は、おそらく予想通り、Kulback-Leibler divergenceD(mu|mu')$がキャラクタリゼーションにおいて重要な役割を果たすことを示唆している。 次に、$phi$-divergence や Wasserstein 距離といった他の発散点と結びついた相互情報を一般化する。
  論文  参考訳（メタデータ） (2022-07-12T08:20:41Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  相互依存信号のデータセットは、列が強い依存を示す行列として定義される。 ニューラルネットワークは、事前に構造として機能し、基礎となる信号相互依存性を明らかにするために使用される。 ディープ・アンローリングとディープ・平衡に基づくアルゴリズムが開発され、高度に解釈可能で簡潔なディープ・ラーニング・ベース・アーキテクチャを形成する。
  論文  参考訳（メタデータ） (2022-03-29T21:00:39Z)
• Contextual Model Aggregation for Fast and Robust Federated Learning in Edge Computing [88.76112371510999]
  フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。 既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。 そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
  論文  参考訳（メタデータ） (2022-03-23T21:42:31Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• Resource-constrained Federated Edge Learning with Heterogeneous Data: Formulation and Analysis [8.863089484787835]
  ヘテロジニアスデータによる不均一な統計的課題を解決するために, 分散されたニュートン型ニュートン型トレーニングスキームであるFedOVAを提案する。 FedOVAはマルチクラス分類問題をより単純なバイナリ分類問題に分解し、アンサンブル学習を用いてそれぞれの出力を結合する。
  論文  参考訳（メタデータ） (2021-10-14T17:35:24Z)
• Sample-based and Feature-based Federated Learning via Mini-batch SSCA [18.11773963976481]
  本稿ではサンプルベースおよび特徴ベース連合最適化について検討する。 提案アルゴリズムは,モデルアグリゲーション機構を通じてデータプライバシを保持できることを示した。 また,提案アルゴリズムは,各フェデレーション最適化問題のKarush-Kuhn-Tucker点に収束することを示した。
  論文  参考訳（メタデータ） (2021-04-13T08:23:46Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。 目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。 提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
  論文  参考訳（メタデータ） (2020-07-07T18:25:25Z)
• Dynamic Federated Learning [57.14673504239551]
  フェデレートラーニング(Federated Learning)は、マルチエージェント環境における集中的なコーディネーション戦略の包括的用語として登場した。 我々は、各イテレーションにおいて、利用可能なエージェントのランダムなサブセットがそのデータに基づいてローカル更新を実行する、フェデレートされた学習モデルを考える。 集約最適化問題に対する真の最小化器上の非定常ランダムウォークモデルの下で、アーキテクチャの性能は、各エージェントにおけるデータ変動率、各エージェントにおけるモデル変動率、アルゴリズムの学習率に逆比例する追跡項の3つの要因によって決定されることを示す。
  論文  参考訳（メタデータ） (2020-02-20T15:00:54Z)

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

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