論文の概要: The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems

• arxiv url: http://arxiv.org/abs/2209.03393v1
• Date: Wed, 7 Sep 2022 18:02:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-09 12:37:28.820754
• Title: The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems
• Title（参考訳）: NPハード探索問題に対するヒューリスティック近似器の(Un)スケーラビリティ
• Authors: Sumedh Pendurkar, Taoan Huang, Sven Koenig, Guni Sharon
• Abstract要約: A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。 このような問題の多くに対する正確な近似もNPハードであることを示す。
• 参考スコア（独自算出の注目度）: 25.641418039598587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with an accurate heuristic function, A* can solve such problems in time complexity that is polynomial in the solution depth. This fact implies that accurate heuristic approximation for many such problems is also NP-hard. In this context, we examine a line of recent publications that propose the use of deep neural networks for heuristic approximation. We assert that these works suffer from inherent scalability limitations since -- under the assumption that P$\ne$NP -- such approaches result in either (a) network sizes that scale exponentially in the instance sizes or (b) heuristic approximation accuracy that scales inversely with the instance sizes. Our claim is supported by experimental results for three representative NP-hard search problems that show that fitting deep neural networks accurately to heuristic functions necessitates network sizes that scale exponentially with the instance size.
• Abstract（参考訳）: a*アルゴリズムはnp-ハードコンビネート最適化問題を解くためによく用いられる。 正確なヒューリスティック関数が与えられると、A* は解深さの多項式である時間複雑性のそのような問題を解くことができる。 この事実は、多くの問題に対する正確なヒューリスティック近似もまたNPハードであることを意味する。 本研究では,ヒューリスティック近似のための深層ニューラルネットワークの利用を提案する最近の論文シリーズについて考察する。 P$\ne$NP という仮定の下で、これらの作業は固有のスケーラビリティの制限に悩まされていると断言する。 (a)インスタンスサイズで指数関数的にスケールするネットワークサイズ、または (b)インスタンスサイズと逆スケールするヒューリスティック近似精度。 我々の主張は、深部ニューラルネットワークをヒューリスティック関数に正確に適合させるには、インスタンスサイズと指数関数的にスケールするネットワークサイズが必要であることを示す3つの代表的NPハードサーチ問題に対する実験結果によって裏付けられている。

関連論文リスト

• 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)
• SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization [5.982922468400901]
  ニューラルネットワークの重みの順に得られる誤差境界を達成可能であることを示す。 我々は、無限アルファベットと入力データに対する最小の仮定の下で、完全なネットワーク境界を達成できることを証明した。
  論文  参考訳（メタデータ） (2023-09-20T00:35:16Z)
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut [0.0]
  Nature Machine Intelligence 4, 367 (2022) において、Schuetzらは、様々な古典的なNPハード最適化問題を解決するためにニューラルネットワーク(GNN)を使用するスキームを提供している。 ネットワークがサンプルインスタンス上でどのようにトレーニングされているかを説明し、その結果のGNNは、広く使われているテクニックを適用して、その成功の可能性を判断する。 しかし, より綿密な検査により, このGNNの報告結果は勾配降下率よりもわずかに優れており, グリーディアルゴリズムにより性能が向上していることがわかった。
  論文  参考訳（メタデータ） (2022-10-02T20:50:33Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces [5.863264019032882]
  関数の近似化や積分に基づく(決定的あるいはランダム化)アルゴリズムの計算複雑性について検討する。 この分野における最も重要な問題の1つは、理論的に証明可能なニューラルネットワーク近似率を実現できるかどうかという問題である。
  論文  参考訳（メタデータ） (2021-04-06T18:55:20Z)
• Training Neural Networks is ER-complete [0.7251305766151019]
  ニューラルネットワーク、トレーニングデータ、およびしきい値を考えると、総誤差がしきい値以下であるようにニューラルネットワークにとってNPハードであることが知られていました。 ER完全であることを示すことにより、この根本的な問題を的確に決定する。 これは、ER方程式の系と整数係数と実未知のの不等式が解を持つかどうかを決定することと同値であることを意味する。
  論文  参考訳（メタデータ） (2021-02-19T08:28:37Z)
• Size and Depth Separation in Approximating Natural Functions with Neural Networks [52.73592689730044]
  本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。 我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。 また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
  論文  参考訳（メタデータ） (2021-01-30T21:30:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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