論文の概要: Time to Rethink AI for Combinatorial Optimization: Classical Algorithms Remain Tough to Match

• arxiv url: http://arxiv.org/abs/2502.03669v2
• Date: Mon, 30 Jun 2025 02:02:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-01 15:08:38.943395
• Title: Time to Rethink AI for Combinatorial Optimization: Classical Algorithms Remain Tough to Match
• Title（参考訳）: AIを再考する - 古典的アルゴリズムは相性が良くない
• Authors: Yikai Wu, Haoyu Zhao, Sanjeev Arora,
• Abstract要約: 先進的なAIにインスパイアされた手法は、最先端の古典的解法であるKaMISによって一貫して性能が向上していることを示す。 LTFT(GNetをベースとする)のような非バックトラックAIメソッドは、最も単純な学位ベースの欲求と同様の推論に終わる。
• 参考スコア（独自算出の注目度）: 36.092099713670414
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This position paper argues that the machine learning community should fundamentally rethink how AI-inspired methods are developed and evaluated for combinatorial optimization (CO). We present comprehensive empirical benchmarks comparing various recent AI-inspired GPU-based methods with several classical CPU-based solvers on the Maximum Independent Set (MIS) problem. Strikingly, even on in-distribution random graphs, leading AI-inspired methods are consistently outperformed by the state-of-the-art classical solver KaMIS, and some AI-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic. To better understand the source of these failures, we introduce a novel analysis, serialization, which reveals that non-backtracking AI methods, such as LTFT (based on GFlowNets), end up reasoning similarly to the simplest degree-based greedy heuristic, and thus worse than KaMIS. Our findings reveal three core issues: (1) Limited benchmarks and evaluation - AI-inspired methods are often tested only on small instances with very limited inference time, which covers up issues with scalability and resource usage; (2) Intrinsic hardness and learning limits - even under ideal, in-distribution conditions, learning-based approaches lag behind classical heuristics, highlighting inherent barriers that receive little attention; and (3) Insufficient use and understanding of classical heuristics - current learning frameworks often neglect to incorporate effective classical techniques. Although we use MIS as a testbed, similar gaps and challenges have been reported in other combinatorial optimization problems, suggesting broader relevance for our recommendations. We propose that future research must address these issues by rigorous benchmarking, deepening understanding of learning limitations, and integrating classical heuristics into AI-inspired methods.
• Abstract（参考訳）: このポジションペーパーでは、機械学習コミュニティは、AIにインスパイアされた手法をどのように開発し、組合せ最適化(CO)のために評価するかを根本的に再考すべきである、と論じている。 我々は、最近のAIにインスパイアされたGPUベースの様々な手法と、最大独立セット(MIS)問題に関する古典的なCPUベースの解法を比較した総合的な経験的ベンチマークを示す。 興味深いことに、非分配ランダムグラフでさえ、AIにインスパイアされたリードメソッドは、最先端の古典的解法であるKaMISによって一貫して優れており、いくつかのAIにインスパイアされたメソッドは、最も単純な学位ベースの欲求的ヒューリスティックでさえも上回らない。 これらの失敗の原因をよりよく理解するために,我々は,LTFT(GFlowNetsをベースとした)のような非バックトラック型AI手法が,最も単純な学位ベースの欲求的ヒューリスティックに類似し,結果としてKaMISよりも悪くなるという,新たな解析,シリアライゼーションを導入する。 その結果,(1) 限られたベンチマークと評価 – AIにインスパイアされたメソッドは,スケーラビリティやリソース使用に関する問題をカバーする,非常に限定された推論時間を持つ小さなインスタンスでのみテストされる場合が多い,(2) 理想的,非分配的な条件下であっても,学習ベースのアプローチは古典的ヒューリスティックスに遅れ,ほとんど注意を払わない固有の障壁を浮き彫りにする,(3) 古典的ヒューリスティックスの不十分な使用と理解 – 現在の学習フレームワークは,有効な古典的テクニックを取り入れることを無視することが多い,という3つの課題が明らかになった。 テストベッドとしてMISを使用しているが、他の組合せ最適化問題では同様のギャップや課題が報告されており、提案手法のより広範な妥当性が示唆されている。 今後の研究は、厳密なベンチマーク、学習制限の理解を深め、古典的ヒューリスティックスをAIにインスパイアされた手法に統合することによって、これらの課題に対処する必要があると提案する。

関連論文リスト

• 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)
• 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)
• 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)

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

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