論文の概要: Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set

• arxiv url: http://arxiv.org/abs/2502.03669v1
• Date: Wed, 05 Feb 2025 23:24:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-07 14:34:27.033057
• Title: Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
• Title（参考訳）: 非現実的な期待 - 最大独立セットに対するAIメソッドと古典的アルゴリズムの比較
• Authors: Yikai Wu, Haoyu Zhao, Sanjeev Arora,
• Abstract要約: 生成モデルや強化学習といったAI手法は、最近最適化(CO)問題、特にNPハード問題に応用されている。 本稿では、GPUベースの手法と、最大独立集合(MIS)上の古典的CPUベースの手法を比較する。 標準的なグラフファミリの実験では、AIベースのアルゴリズムは性能が上がらず、多くの場合、単一のCPU上で動作している最先端の古典的解法KaMISのソリューション品質に匹敵する。
• 参考スコア（独自算出の注目度）: 36.092099713670414
• License:
• Abstract: AI methods, such as generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on Maximum Independent Set (MIS). Experiments on standard graph families show that AI-based algorithms fail to outperform and, in many cases, to match the solution quality of the state-of-art classical solver KaMIS running on a single CPU. Some GPU-based methods even perform similarly to the simplest heuristic, degree-based greedy. Even with post-processing techniques like local search, AI-based methods still perform worse than CPU-based solvers. We develop a new mode of analysis to reveal that non-backtracking AI methods, e.g. LTFT (which is based on GFlowNets), end up reasoning similarly to the simplest degree-based greedy approach, and thus worse than KaMIS. We also find that CPU-based algorithms, notably KaMIS, have strong performance on sparse random graphs, which appears to refute a well-known conjectured upper bound for efficient algorithms from Coja-Oghlan & Efthymiou (2015).
• Abstract（参考訳）: 生成モデルや強化学習といったAI手法は、最近、組合せ最適化(CO)問題、特にNPハード問題に応用されている。 本稿では、GPUベースの手法と、最大独立セット(MIS)上の古典的CPUベースの手法を比較する。 標準的なグラフファミリの実験では、AIベースのアルゴリズムは性能が上がらず、多くの場合、単一のCPU上で動作している最先端の古典的解法KaMISのソリューション品質に匹敵する。 GPUベースのいくつかのメソッドは、最も単純なヒューリスティックな学位ベースの欲求と同じような機能を持つ。 ローカル検索のような後処理技術であっても、AIベースの手法は依然としてCPUベースの解法よりもパフォーマンスが悪い。 我々は,GFlowNetsをベースとした非バックトラック型AI手法(例えばLTFT,GFlowNetsをベースとする)が,最も単純な等級ベースの欲求的アプローチと同様に推論され,その結果,KaMISよりも悪くなることを明らかにするために,新たな解析方法を開発した。 また、CPUベースのアルゴリズム、特にKaMISはスパースランダムグラフに強い性能を持ち、Coja-Oghlan & Efthymiou (2015) の効率的なアルゴリズムについてよく知られた上限を否定している。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。 この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
  論文  参考訳（メタデータ） (2021-07-27T08:48:01Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。 本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
  論文  参考訳（メタデータ） (2021-01-25T01:49:10Z)
• Benchmarking Simulation-Based Inference [5.3898004059026325]
  確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。 推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。 性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
  論文  参考訳（メタデータ） (2021-01-12T18:31:22Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  二次代入問題 (QAP) はNPハード問題に属する最適化問題である。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
  論文  参考訳（メタデータ） (2020-07-29T15:02:07Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)
• Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs [5.486093983007419]
  本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。 高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
  論文  参考訳（メタデータ） (2020-04-14T14:11:00Z)

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

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