論文の概要: Fast Gradient Computation for Gromov-Wasserstein Distance

• arxiv url: http://arxiv.org/abs/2404.08970v1
• Date: Sat, 13 Apr 2024 11:23:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-16 17:53:43.826182
• Title: Fast Gradient Computation for Gromov-Wasserstein Distance
• Title（参考訳）: Gromov-Wasserstein距離の高速勾配計算
• Authors: Wei Zhang, Zihao Wang, Jie Fan, Hao Wu, Yong Zhang,
• Abstract要約: グロモフ=ワッサーシュタイン距離は最適な輸送の顕著な拡張である。 グロモフ=ワッサーシュタイン距離と輸送計画の計算は高価である。 本稿では,動的プログラミング手法により,精度の高い勾配計算を高速化する新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 17.47684854121659
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Gromov-Wasserstein distance is a notable extension of optimal transport. In contrast to the classic Wasserstein distance, it solves a quadratic assignment problem that minimizes the pair-wise distance distortion under the transportation of distributions and thus could apply to distributions in different spaces. These properties make Gromov-Wasserstein widely applicable to many fields, such as computer graphics and machine learning. However, the computation of the Gromov-Wasserstein distance and transport plan is expensive. The well-known Entropic Gromov-Wasserstein approach has a cubic complexity since the matrix multiplication operations need to be repeated in computing the gradient of Gromov-Wasserstein loss. This becomes a key bottleneck of the method. Currently, existing methods accelerate the computation focus on sampling and approximation, which leads to low accuracy or incomplete transport plan. In this work, we propose a novel method to accelerate accurate gradient computation by dynamic programming techniques, reducing the complexity from cubic to quadratic. In this way, the original computational bottleneck is broken and the new entropic solution can be obtained with total quadratic time, which is almost optimal complexity. Furthermore, it can be extended to some variants easily. Extensive experiments validate the efficiency and effectiveness of our method.
• Abstract（参考訳）: グロモフ=ワッサーシュタイン距離は最適な輸送の顕著な拡張である。 古典的なワッサーシュタイン距離とは対照的に、分布の輸送における対距離歪みを最小限に抑え、したがって異なる空間の分布に適用できる二次代入問題を解く。 これらの性質により、Gromov-Wassersteinはコンピュータグラフィックスや機械学習など多くの分野に適用できる。 しかし,Gromov-Wasserstein距離と輸送計画の計算は高価である。 よく知られたエントロピー的グロモフ=ワッセルシュタイン法は、グロモフ=ワッセルシュタイン損失の勾配を計算する際に行列乗算演算を繰り返す必要があるため、立方的複雑性を持つ。 これがメソッドの重要なボトルネックになります。 現在、既存の手法はサンプリングと近似に重点を置いて計算を加速しており、これは低い精度または不完全な輸送計画をもたらす。 本研究では,動的プログラミング手法による精度の高い勾配計算を高速化する手法を提案し,その複雑さを3次から2次へと低減する。 このように、元の計算ボトルネックは破壊され、新しいエントロピー解は2次時間で得られるが、これはほぼ最適な複雑さである。 さらに、いくつかの変種にも容易に拡張できる。 大規模な実験により,本手法の有効性と有効性について検証した。

関連論文リスト

• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein [27.2585517709102]
  また, 最適輸送によるGromov-Wassersteinアルゴリズムも最適であることを示す。 これらの結果は、Gromov-Wassersteinアルゴリズムを実際に展開するための最初の統計的正当性を与える。
  論文  参考訳（メタデータ） (2023-11-22T18:55:27Z)
• Approximation Theory, Computing, and Deep Learning on the Wasserstein Space [0.5735035463793009]
  有限標本からの無限次元空間における近似関数の挑戦に対処する。 我々の焦点はワッサーシュタイン距離関数であり、これは関連する例である。 機能近似を定義するために,機械学習に基づく3つのアプローチを採用する。
  論文  参考訳（メタデータ） (2023-10-30T13:59:47Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Algorithms for perturbative analysis and simulation of quantum dynamics [0.0]
  我々はダイソン級数とマグナス展開の両方を計算・利用するための汎用アルゴリズムを開発した。 モデルパラメータ空間の領域における忠実度を近似するためにこれらのツールの使い方を実証する。 計算前のステップを,元法よりも少ない項数で多変数展開問題と表現できることを示す。
  論文  参考訳（メタデータ） (2022-10-20T21:07:47Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Large-Scale Wasserstein Gradient Flows [84.73670288608025]
  ワッサーシュタイン勾配流を近似するスケーラブルなスキームを導入する。 我々のアプローチは、JKOステップを識別するために、入力ニューラルネットワーク(ICNN)に依存しています。 その結果、勾配拡散の各ステップで測定値からサンプリングし、その密度を計算することができる。
  論文  参考訳（メタデータ） (2021-06-01T19:21:48Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  高次元の2つの確率分布の間のワッサーシュタイン測地線を計算するための新しい定式化と学習戦略を提案する。 ラグランジュ乗算器の手法を最適輸送(OT)問題の動的定式化に適用することにより、サドル点がワッサーシュタイン測地線であるミニマックス問題を導出する。 次に、深層ニューラルネットワークによる関数のパラメータ化を行い、トレーニングのためのサンプルベースの双方向学習アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-02-05T04:25:28Z)
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance [36.97843660480747]
  wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。 最近提案された次元の呪いを和らげるためのアプローチは、サンプルデータを低次元の部分空間に投影し、それから投影されたデータ間のワッサーシュタイン距離を計算することである。 しかし、このアプローチは、実際には非常に難しいStiefel多様体上の最大分問題を解決する必要があります。 本研究では,Stiefel多様体上の正規化最大ミン問題の新たな再構成に基づく,この問題を解くための新しいブロック座標降下法(RBCD)を提案する。
  論文  参考訳（メタデータ） (2020-12-09T17:47:56Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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