論文の概要: Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions

• arxiv url: http://arxiv.org/abs/2405.09644v1
• Date: Wed, 8 May 2024 09:25:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-19 13:49:26.404057
• Title: Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions
• Title（参考訳）: テンソル収縮経路の最適化: コスト関数を改良したグレディアルゴリズムアプローチ
• Authors: Sheela Orgler, Mark Blacher,
• Abstract要約: より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。 我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
• 参考スコア（独自算出の注目度）: 1.3812010983144802
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding efficient tensor contraction paths is essential for a wide range of problems, including model counting, quantum circuits, graph problems, and language models. There exist several approaches to find efficient paths, such as the greedy and random greedy algorithm by Optimized Einsum (opt_einsum), and the greedy algorithm and hypergraph partitioning approach employed in cotengra. However, these algorithms require a lot of computational time and resources to find efficient contraction paths. In this paper, we introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. Moreover, with our approach, we are even able to compute paths for large problems where modern algorithms fail.
• Abstract（参考訳）: 効率的なテンソル収縮経路を見つけることは、モデルカウント、量子回路、グラフ問題、言語モデルなど、幅広い問題に不可欠である。 例えば、Optimized Einsum (opt_einsum) によるgreedy and random greedy algorithm や、cotengra で用いられるgreedy algorithm や hypergraph partitioning approach などである。 しかし、これらのアルゴリズムは効率的な収縮経路を見つけるのに多くの計算時間と資源を必要とする。 本稿では,より少ない時間で効率的な収縮経路を計算するopo_einsumによる,欲求アルゴリズムに基づく新しい手法を提案する。 さらに,本手法では,現代のアルゴリズムが失敗する大問題に対して,経路を計算できる。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。 妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。 このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
  論文  参考訳（メタデータ） (2023-05-17T06:22:11Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。 同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
  論文  参考訳（メタデータ） (2021-04-14T07:59:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。 古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-03T20:37:05Z)

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

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