論文の概要: Semidefinite Relaxations of the Gromov-Wasserstein Distance
- arxiv url: http://arxiv.org/abs/2312.14572v2
- Date: Wed, 27 Dec 2023 03:48:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 20:56:57.009341
- Title: Semidefinite Relaxations of the Gromov-Wasserstein Distance
- Title(参考訳): gromov-wasserstein距離の半定値緩和
- Authors: Junyu Chen, Binh T. Nguyen, Yong Sheng Soh
- Abstract要約: グロモフ・ワッサー距離(Gromov-Wasser distance, GW)は、空間間の物体の一致を可能にする最適輸送問題の変種である。
本稿では,GW距離の半定緩和法を提案する。
我々の緩和は、グローバル最適解への任意の輸送の比率を計算する方法を提供する。
- 参考スコア(独自算出の注目度): 11.014678654943234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Gromov-Wasserstein (GW) distance is a variant of the optimal transport
problem that allows one to match objects between incomparable spaces. At its
core, the GW distance is specified as the solution of a non-convex quadratic
program and is not known to be tractable to solve. In particular, existing
solvers for the GW distance are only able to find locally optimal solutions. In
this work, we propose a semi-definite programming (SDP) relaxation of the GW
distance. The relaxation can be viewed as the dual of the GW distance augmented
with constraints that relate the linear and quadratic terms of transportation
maps. Our relaxation provides a principled manner to compute the approximation
ratio of any transport map to the global optimal solution. Finally, our
numerical experiments suggest that the proposed relaxation is strong in that it
frequently computes the global optimal solution, together with a proof of
global optimality.
- Abstract(参考訳): グロモフ=ワッセルシュタイン距離(gromov-wasserstein distance)は、可比較空間間の対象をマッチングできる最適な輸送問題の変種である。
その中核では、GW距離は非凸二次プログラムの解として指定されており、解けないことは知られていない。
特に、GW距離の既存の解法は局所最適解のみを見つけることができる。
本稿では,GW距離の半定値プログラミング(SDP)緩和を提案する。
緩和は、輸送写像の線型項と二次項を関連付ける制約によって拡張されたgw距離の双対と見なすことができる。
我々の緩和は、任意の輸送写像の近似比を大域最適解に計算する原理的な方法を提供する。
最後に,数値実験により,大域的最適解を頻繁に計算し,大域的最適性の証明を行うことで,提案する緩和が強いことが示唆された。
関連論文リスト
- Normalizing flows as approximations of optimal transport maps via
linear-control neural ODEs [55.2480439325792]
ニューマライズフロー」は、深層ニューラルネットワークを用いて確率測度間の可逆輸送マップを構築するタスクに関連している。
我々は、絶対連続測度$mu,nuinmathcalP(mathbbRn)$間の$W$最適輸送マップ$T$を線形制御ニューラルネットワークのフローとして回収する問題を考える。
論文 参考訳(メタデータ) (2023-11-02T17:17:03Z) - A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein
in Graph Data [37.89640056739607]
本稿では,Gromov-Wasserstein (GW) 距離の近似解を提供する単一ループアルゴリズムであるBregman Alternating Projected Gradient (BAPG) を提案する。
本稿では,カップリングマップの実現可能性においていくつかの妥協点があるにもかかわらず,精度と計算効率のバランスをとる新しい緩和手法を提案する。
論文 参考訳(メタデータ) (2023-03-12T07:23:16Z) - Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds [53.110934987571355]
多様体グラフ上の熱核に基づく測地学的シンクホーンを提案する。
化学療法中の患者試料からの高次元単細胞データの複数分布のバリセンタの計算に本法を適用した。
論文 参考訳(メタデータ) (2022-11-02T00:51:35Z) - Efficient Approximation of Gromov-Wasserstein Distance using Importance
Sparsification [34.865115235547286]
本稿では,Gromov-Wasserstein距離を効率的に近似するために,Spar-GWと呼ばれる新しい重要空間分割法を提案する。
Spar-GW法は任意の地価でGW距離に適用可能であることを示す。
さらに、この方法は、エントロピーGW距離、融合GW距離、不均衡GW距離を含むGW距離の変種を近似するために拡張することができる。
論文 参考訳(メタデータ) (2022-05-26T18:30:40Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。
生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。
そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-03T13:45:36Z) - Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal
Transport [0.483420384410068]
エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。
また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大させることも検討した。
論文 参考訳(メタデータ) (2021-10-25T06:52:45Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - The Unbalanced Gromov Wasserstein Distance: Conic Formulation and
Relaxation [0.0]
距離測度空間(すなわち確率分布を持つ距離空間)を比較することは、多くの機械学習問題の中心である。
そのような距離空間の間の最も一般的な距離は計量測度Gro-Wasserstein (GW) 距離であり、その距離は二次である。
GW の定式化は、任意の正測度を持つ距離空間の比較を等距離まで緩和する。
論文 参考訳(メタデータ) (2020-09-09T12:38:14Z) - On Projection Robust Optimal Transport: Sample Complexity and Model
Misspecification [101.0377583883137]
射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。
私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。
次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
論文 参考訳(メタデータ) (2020-06-22T14:35:33Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。
我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。
AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文 参考訳(メタデータ) (2020-02-05T03:09:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。