論文の概要: Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs

• arxiv url: http://arxiv.org/abs/2004.07300v1
• Date: Tue, 14 Apr 2020 14:11:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 09:06:07.899143
• Title: Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs
• Title（参考訳）: gumbel-softmax-based optimization:グラフ上の最適化問題のための単純な汎用フレームワーク
• Authors: Yaoxin Li, Jing Liu, Guozheng Lin, Yueyuan Hou, Muyun Mou and Jiang Zhang
• Abstract要約: 本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。 高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
• 参考スコア（独自算出の注目度）: 5.486093983007419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In computer science, there exist a large number of optimization problems defined on graphs, that is to find a best node state configuration or a network structure such that the designed objective function is optimized under some constraints. However, these problems are notorious for their hardness to solve because most of them are NP-hard or NP-complete. Although traditional general methods such as simulated annealing (SA), genetic algorithms (GA) and so forth have been devised to these hard problems, their accuracy and time consumption are not satisfying in practice. In this work, we proposed a simple, fast, and general algorithm framework based on advanced automatic differentiation technique empowered by deep learning frameworks. By introducing Gumbel-softmax technique, we can optimize the objective function directly by gradient descent algorithm regardless of the discrete nature of variables. We also introduce evolution strategy to parallel version of our algorithm. We test our algorithm on three representative optimization problems on graph including modularity optimization from network science, Sherrington-Kirkpatrick (SK) model from statistical physics, maximum independent set (MIS) and minimum vertex cover (MVC) problem from combinatorial optimization on graph. High-quality solutions can be obtained with much less time consuming compared to traditional approaches.
• Abstract（参考訳）: 計算機科学では、グラフ上に定義された最適化問題は多数存在し、最適なノード状態の設定やネットワーク構造を見つけることで、設計対象関数がいくつかの制約の下で最適化される。 しかしながら、これらの問題はNPハードまたはNP完全であるため、解決が難しいことで悪名高い。 シミュレーションアニール (SA) や遺伝的アルゴリズム (GA) といった従来の一般的な手法はこれらの難しい問題に対して考案されているが、その正確さや時間消費は実際には満足していない。 本研究では,ディープラーニングフレームワークによる高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。 Gumbel-softmax手法を導入することにより、変数の離散性に関係なく、勾配降下アルゴリズムにより目的関数を直接最適化することができる。 また,並列バージョンのアルゴリズムに進化戦略を導入する。 ネットワーク科学のモジュラリティ最適化,統計物理学のsherington-kirkpatrick (sk) モデル,mis (maximum independent set) およびmvc (minimum vertex cover) 問題を含む,グラフ上の3つの代表的な最適化問題に対してアルゴリズムをテストした。 高品質なソリューションは従来のアプローチに比べてはるかに少ない時間で得られる。

関連論文リスト

• Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization [6.896308995955336]
  グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。 本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
  論文  参考訳（メタデータ） (2023-12-06T01:16:10Z)
• Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
  最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
  論文  参考訳（メタデータ） (2023-10-01T00:12:31Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。 ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
  論文  参考訳（メタデータ） (2021-07-02T16:54:35Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。 理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T22:17:50Z)
• Transferable Graph Optimizers for ML Compilers [18.353830282858834]
  計算グラフ最適化(GO)のためのエンドツーエンドで転送可能な深層強化学習法を提案する。 GOは個々のノードに対して自動回帰ではなく,グラフ全体の決定を生成する。 GOは、人間の専門家よりも21%改善し、先行技術よりも18%改善し、15倍早く収束する。
  論文  参考訳（メタデータ） (2020-10-21T20:28:33Z)

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

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