論文の概要: Algorithms for Tensor Network Contraction Ordering
- arxiv url: http://arxiv.org/abs/2001.08063v1
- Date: Wed, 15 Jan 2020 19:00:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 05:37:35.499482
- Title: Algorithms for Tensor Network Contraction Ordering
- Title(参考訳): テンソルネットワーク収縮順序付けアルゴリズム
- Authors: Frank Schindler, Adam S. Jermyn
- Abstract要約: 十分に設計された収縮シーケンスは、収縮コストを劇的に削減することができる。
この順序付け問題に対して、2つの一般的な離散最適化手法をベンチマークする。
検討するアルゴリズムは、同等の計算資源を与えられた欲求探索を一貫して上回っていることがわかった。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Contracting tensor networks is often computationally demanding. Well-designed
contraction sequences can dramatically reduce the contraction cost. We explore
the performance of simulated annealing and genetic algorithms, two common
discrete optimization techniques, to this ordering problem. We benchmark their
performance as well as that of the commonly-used greedy search on physically
relevant tensor networks. Where computationally feasible, we also compare them
with the optimal contraction sequence obtained by an exhaustive search. We find
that the algorithms we consider consistently outperform a greedy search given
equal computational resources, with an advantage that scales with tensor
network size. We compare the obtained contraction sequences and identify signs
of highly non-local optimization, with the more sophisticated algorithms
sacrificing run-time early in the contraction for better overall performance.
- Abstract(参考訳): テンソルネットワークの契約はしばしば計算上要求される。
適切に設計された収縮シーケンスは、収縮コストを劇的に削減することができる。
我々は,この順序問題に対する2つの共通離散最適化手法であるシミュレーションアニーリングと遺伝的アルゴリズムの性能について検討する。
彼らのパフォーマンスや、物理的に関連のあるテンソルネットワークでよく使われる欲望検索のパフォーマンスをベンチマークします。
また, 計算可能であれば, 徹底探索により得られた最適収縮シーケンスと比較する。
私たちが検討するアルゴリズムは、テンソルネットワークサイズでスケールする利点とともに、同等の計算資源を与えられた欲求探索を一貫して上回ります。
得られた縮約シーケンスと高度に非局所的な最適化の兆候を同定し、より洗練されたアルゴリズムにより、縮約の初期を犠牲にして全体的な性能を向上する。
関連論文リスト
- Approximating Metric Magnitude of Point Sets [4.522729058300309]
計量等級は、多くの望ましい幾何学的性質を持つ点雲の「大きさ」の尺度である。
様々な数学的文脈に適応しており、最近の研究は機械学習と最適化アルゴリズムを強化することを示唆している。
本稿では, 等級問題について検討し, 効率よく近似する方法を示し, 凸最適化問題として扱うことができるが, 部分モジュラ最適化としては適用できないことを示す。
本稿では,高速に収束し精度の高い反復近似アルゴリズムと,計算をより高速に行うサブセット選択法という,2つの新しいアルゴリズムについて述べる。
論文 参考訳(メタデータ) (2024-09-06T17:15:28Z) - Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
低ランク近似を用いてテンソルネットワークの収縮を効率的に近似する手法を提案する。
提案アルゴリズムは,低ランク近似を行う場合,環境の大部分を組み込む柔軟性を有する。
論文 参考訳(メタデータ) (2024-06-14T07:13:52Z) - Quantum and classical correlations in shrinking algorithms for optimization [0.0]
最適化問題(COP)の解法として量子コンピューティングを用いる。
本研究では,再帰的に縮小することでCOPを解くアルゴリズムを拡張し,解析する。
量子近似最適化アルゴリズム(QAOA)と古典線形計画法(LP)と半定値計画法(SDP)の相関性を備えたアルゴリズムの性能を比較した。
論文 参考訳(メタデータ) (2024-04-26T08:29:04Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳(メタデータ) (2023-06-28T00:46:58Z) - Performance Embeddings: A Similarity-based Approach to Automatic
Performance Optimization [71.69092462147292]
パフォーマンス埋め込みは、アプリケーション間でパフォーマンスチューニングの知識伝達を可能にする。
本研究では, 深層ニューラルネットワーク, 密度およびスパース線形代数合成, および数値風速予測ステンシルのケーススタディにおいて, この伝達チューニング手法を実証する。
論文 参考訳(メタデータ) (2023-03-14T15:51:35Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳(メタデータ) (2022-10-02T05:03:38Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳(メタデータ) (2021-01-12T18:31:22Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。