論文の概要: 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 15:30:40.566547
• 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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) の効率的なアルゴリズムについてよく知られた上限を否定している。

関連論文リスト

• An island-parallel ensemble metaheuristic algorithm for large graph coloring problems [0.4915744683251149]
  大規模GCPインスタンスを解決するために,島並列アンサンブルメタヒューリスティックアルゴリズム(PEM-Color)を提案する。 私たちの知る限りでは、これはメタヒューリスティックスを組み合わせて、アンサンブルアプローチを使用してGCPに適用する最初の研究です。
  論文  参考訳（メタデータ） (2025-04-21T13:15:23Z)
• Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs [76.43407125275202]
  o1のようなモデルは、推論中に人間のような長時間の思考をエミュレートすることができる。 本論文は,これらのモデルにおける過度な考察の課題に関する,最初の包括的研究である。 精度を損なうことなく、過剰思考を緩和し、推論プロセスを合理化するための戦略を提案する。
  論文  参考訳（メタデータ） (2024-12-30T18:55:12Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding [76.67608003501479]
  POGEMAは、学習のための高速環境、問題インスタンスジェネレータ、可視化ツールキットを含む、総合的なツールセットである。 また、プライマリ評価指標に基づいて計算されるドメイン関連メトリクスの範囲を規定する評価プロトコルを導入し、定義する。 この比較の結果は、様々な最先端のMARL、検索ベース、ハイブリッド手法を含む。
  論文  参考訳（メタデータ） (2024-07-20T16:37:21Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Unveiling the Limits of Learned Local Search Heuristics: Are You the Mightiest of the Meek? [14.195843311387591]
  Tabu Searchに基づく単純な学習は、パフォーマンスと一般化性の点で最先端の学習を超越していることが示される。 今後の研究に向けて,本研究は仮定に挑戦し,エキサイティングな道を開いた。
  論文  参考訳（メタデータ） (2023-10-30T20:16:42Z)
• Multivariate Time Series Anomaly Detection: Fancy Algorithms and Flawed Evaluation Methodology [2.043517674271996]
  本稿では、MVTS異常検出の文脈において、正常によいプロトコルが弱点を持つ可能性について論じる。 本稿では,PCA(Principal Components Analysis)に基づくシンプルな,かつ難しいベースラインを提案する。このベースラインは,最近のDeep Learning(DL)ベースのアプローチにおいて,一般的なベンチマークデータセットよりも驚くほど優れています。
  論文  参考訳（メタデータ） (2023-08-24T20:24:12Z)
• Deep learning applied to computational mechanics: A comprehensive review, state of the art, and the classics [77.34726150561087]
  人工知能,特に深層学習(DL)の最近の進歩を概観する。 ハイブリッドおよび純粋機械学習(ML)の手法について論じる。 AIの歴史と限界は、特に古典の誤解や誤解を指摘し、議論され、議論される。
  論文  参考訳（メタデータ） (2022-12-18T02:03:00Z)
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization [2.9882027965916413]
  影響最大化(IM)は、モバイルネットワーク、ソーシャルコンピューティング、レコメンデーションシステムで広く用いられる古典的な最適化問題である。 主な課題は、IM問題のNP硬度と、影響力の広がりを推定する#P硬度である。 我々は,関連する背景知識,基本原則,共通手法,応用研究の要約に重点を置いている。
  論文  参考訳（メタデータ） (2022-11-06T10:13:42Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  ROC曲線 (AUC) の下の領域は、不均衡学習やレコメンダシステムといった問題に対するよく知られたランキング基準である。 本稿では,マルチクラスAUCメトリクスを最適化することで,多クラススコアリング関数を学習する問題について検討する。
  論文  参考訳（メタデータ） (2021-07-28T05:18:10Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。 この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
  論文  参考訳（メタデータ） (2021-07-27T08:48:01Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  学習は現代の情報処理の中核技術になっているが、バイアス、安全でない、偏見のあるソリューションにつながるという証拠はたくさんある。
  論文  参考訳（メタデータ） (2021-03-08T23:10:33Z)
• 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)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• 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)

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

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