論文の概要: Approximative Algorithms for Multi-Marginal Optimal Transport and
Free-Support Wasserstein Barycenters
- arxiv url: http://arxiv.org/abs/2202.00954v1
- Date: Wed, 2 Feb 2022 10:59:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-03 15:18:29.876749
- Title: Approximative Algorithms for Multi-Marginal Optimal Transport and
Free-Support Wasserstein Barycenters
- Title（参考訳）: マルチMarginal Optimal Transport と Free-Support Wasserstein Barycenter の近似アルゴリズム
- Authors: Johannes von Lindheim
- Abstract要約: N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。
高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computationally solving multi-marginal optimal transport (MOT) with squared
Euclidean costs for $N$ discrete probability measures has recently attracted
considerable attention, in part because of the correspondence of its solutions
with Wasserstein-$2$ barycenters, which have many applications in data science.
In general, this problem is NP-hard, calling for practical approximative
algorithms. While entropic regularization has been successfully applied to
approximate Wasserstein barycenters, this loses the sparsity of the optimal
solution, making it difficult to solve the MOT problem directly in practice
because of the curse of dimensionality. Thus, for obtaining barycenters, one
usually resorts to fixed-support restrictions to a grid, which is, however,
prohibitive in higher ambient dimensions $d$. In this paper, after analyzing
the relationship between MOT and barycenters, we present two algorithms to
approximate the solution of MOT directly, requiring mainly just $N-1$ standard
two-marginal OT computations. Thus, they are fast, memory-efficient and easy to
implement and can be used with any sparse OT solver as a black box. Moreover,
they produce sparse solutions and show promising numerical results. We analyze
these algorithms theoretically, proving upper and lower bounds for the relative
approximation error.
- Abstract（参考訳）: n$の離散確率測度に対する二乗ユークリッド費用による多角的最適輸送(mot)を計算的に解くことは、近年、データサイエンスに多くの応用があるwasserstein-$2$ barycentersとの解の対応により、かなりの注目を集めている。
一般に、この問題はNPハードであり、実用的な近似アルゴリズムを要求する。
エントロピック正則化は近似ワッサーシュタインバリセンタにうまく適用されているが、これは最適解の空間性を失うため、次元性の呪いのため、実際にMOT問題を解くことは困難である。
したがって、バリセンタを得るためには、通常、グリッドに対する固定サポートの制約に頼るが、より高い環境次元では、$d$である。
本稿では,MOTとバリセンタの関係を解析した結果,MOTの解を直接近似する2つのアルゴリズムを提案する。
したがって、それらは高速でメモリ効率が高く、実装が容易であり、任意のスパースotソルバをブラックボックスとして使用できる。
さらに、スパース解を生成し、有望な数値結果を示す。
これらのアルゴリズムを理論的に解析し、相対近似誤差の上限と下限を証明した。
関連論文リスト
- Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances [9.608373793625107]
カーネル最大スライシング (KMS) ワッサーシュタイン距離は、この目的のために開発された。
KMS の 2$-Wasserstein 距離の計算は NP-hard であることを示す。
論文 参考訳（メタデータ） (2024-05-24T11:14:56Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
本稿では,Wasserstein Barycenter問題を解くための新しいスケーラブルなアプローチを提案する。
我々の手法は最近のNeural OTソルバをベースとしている。
また,提案手法の理論的誤差境界も確立する。
論文 参考訳（メタデータ） (2024-02-06T09:17:07Z) - Covariance alignment: from maximum likelihood estimation to
Gromov-Wasserstein [27.2585517709102]
また, 最適輸送によるGromov-Wassersteinアルゴリズムも最適であることを示す。
これらの結果は、Gromov-Wassersteinアルゴリズムを実際に展開するための最初の統計的正当性を与える。
論文 参考訳（メタデータ） (2023-11-22T18:55:27Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - On the complexity of the optimal transport problem with graph-structured
cost [9.24979291231758]
マルチマージ最適輸送(Multi-marginal optimal transport、MOT)は、複数の辺縁への最適輸送の一般化である。
MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。
論文 参考訳（メタデータ） (2021-10-01T19:29:59Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Projection Robust Wasserstein Barycenter [36.97843660480747]
ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です
本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
論文 参考訳（メタデータ） (2021-02-05T19:23:35Z) - Continuous Wasserstein-2 Barycenter Estimation without Minimax
Optimization [94.18714844247766]
ワッサーシュタイン・バリセンターは、最適輸送に基づく確率測度の重み付き平均の幾何学的概念を提供する。
本稿では,Wasserstein-2 バリセンタのサンプルアクセスを演算するスケーラブルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-02T21:01:13Z) - A Riemannian Block Coordinate Descent Method for Computing the
Projection Robust Wasserstein Distance [36.97843660480747]
wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。
最近提案された次元の呪いを和らげるためのアプローチは、サンプルデータを低次元の部分空間に投影し、それから投影されたデータ間のワッサーシュタイン距離を計算することである。
しかし、このアプローチは、実際には非常に難しいStiefel多様体上の最大分問題を解決する必要があります。
本研究では,Stiefel多様体上の正規化最大ミン問題の新たな再構成に基づく,この問題を解くための新しいブロック座標降下法(RBCD)を提案する。
論文 参考訳（メタデータ） (2020-12-09T17:47:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。