論文の概要: A Riemannian Block Coordinate Descent Method for Computing the
Projection Robust Wasserstein Distance
- arxiv url: http://arxiv.org/abs/2012.05199v3
- Date: Wed, 13 Jan 2021 22:11:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-16 02:08:48.178416
- Title: A Riemannian Block Coordinate Descent Method for Computing the
Projection Robust Wasserstein Distance
- Title（参考訳）: 射影ロバスト・ワッサーシュタイン距離計算のためのリーマンブロック座標Descent法
- Authors: Minhui Huang, Shiqian Ma and Lifeng Lai
- Abstract要約: wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。
最近提案された次元の呪いを和らげるためのアプローチは、サンプルデータを低次元の部分空間に投影し、それから投影されたデータ間のワッサーシュタイン距離を計算することである。
しかし、このアプローチは、実際には非常に難しいStiefel多様体上の最大分問題を解決する必要があります。
本研究では,Stiefel多様体上の正規化最大ミン問題の新たな再構成に基づく,この問題を解くための新しいブロック座標降下法(RBCD)を提案する。
- 参考スコア（独自算出の注目度）: 36.97843660480747
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Wasserstein distance has become increasingly important in machine
learning and deep learning. Despite its popularity, the Wasserstein distance is
hard to approximate because of the curse of dimensionality. A recently proposed
approach to alleviate the curse of dimensionality is to project the sampled
data from the high dimensional probability distribution onto a
lower-dimensional subspace, and then compute the Wasserstein distance between
the projected data. However, this approach requires to solve a max-min problem
over the Stiefel manifold, which is very challenging in practice. The only
existing work that solves this problem directly is the RGAS (Riemannian
Gradient Ascent with Sinkhorn Iteration) algorithm, which requires to solve an
entropy-regularized optimal transport problem in each iteration, and thus can
be costly for large-scale problems. In this paper, we propose a Riemannian
block coordinate descent (RBCD) method to solve this problem, which is based on
a novel reformulation of the regularized max-min problem over the Stiefel
manifold. We show that the complexity of arithmetic operations for RBCD to
obtain an $\epsilon$-stationary point is $O(\epsilon^{-3})$. This significantly
improves the corresponding complexity of RGAS, which is $O(\epsilon^{-12})$.
Moreover, our RBCD has very low per-iteration complexity, and hence is suitable
for large-scale problems. Numerical results on both synthetic and real datasets
demonstrate that our method is more efficient than existing methods, especially
when the number of sampled data is very large.
- Abstract（参考訳）: wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。
その人気にもかかわらず、ワッサーシュタイン距離は次元の呪いのために近似が難しい。
最近提案された次元の呪いを緩和するためのアプローチは、サンプルデータを高次元確率分布から低次元部分空間に投影し、投影されたデータ間のワッサースタイン距離を計算することである。
しかし、このアプローチはスティフェル多様体上の極小問題を解く必要があり、これは実際は非常に難しい。
この問題を直接解く既存の仕事は、rgas(riemannian gradient ascent with sinkhorn iteration)アルゴリズムのみであり、各イテレーションでエントロピー正規化された最適輸送問題を解く必要があるため、大規模な問題にはコストがかかる。
本稿では,この問題をStiefel多様体上の正規化最大ミン問題の新たな再定式化に基づく,リーマンブロック座標降下法(RBCD)を提案する。
RBCDの算術演算の複雑さから、$\epsilon$-stationary point は$O(\epsilon^{-3})$であることが示される。
これは RGAS の複雑性を大幅に改善し、これは$O(\epsilon^{-12})$である。
さらに,我々のRBCDは点数当たりの複雑性が非常に低く,大規模な問題に適している。
合成データと実データの両方における数値的な結果から,本手法は既存の手法よりも効率的であることが明らかとなった。
関連論文リスト
- Fast Gradient Computation for Gromov-Wasserstein Distance [17.47684854121659]
グロモフ=ワッサーシュタイン距離は最適な輸送の顕著な拡張である。
グロモフ=ワッサーシュタイン距離と輸送計画の計算は高価である。
本稿では,動的プログラミング手法により,精度の高い勾配計算を高速化する新しい手法を提案する。
論文 参考訳（メタデータ） (2024-04-13T11:23:34Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Approximative Algorithms for Multi-Marginal Optimal Transport and
Free-Support Wasserstein Barycenters [0.0]
N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。
高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
論文 参考訳（メタデータ） (2022-02-02T10:59:54Z) - 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) - Partial Wasserstein Covering [10.52782170493037]
我々は、大規模なデータセットをエミュレートする目的で、部分的なWassersteinと呼ばれる一般的なタスクについて検討する。
この問題をワッサーシュタイン偏微分を目的関数とする離散最適化問題としてモデル化する。
我々は、シーンデータセットの駆動を含む部分的なワッサースタインの発散の観点から、2つのデータセットを効率的に作成できることを示します。
論文 参考訳（メタデータ） (2021-06-02T01:48:41Z) - Projection Robust Wasserstein Barycenter [36.97843660480747]
ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です
本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
論文 参考訳（メタデータ） (2021-02-05T19:23:35Z) - Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
高次元の2つの確率分布の間のワッサーシュタイン測地線を計算するための新しい定式化と学習戦略を提案する。
ラグランジュ乗算器の手法を最適輸送(OT)問題の動的定式化に適用することにより、サドル点がワッサーシュタイン測地線であるミニマックス問題を導出する。
次に、深層ニューラルネットワークによる関数のパラメータ化を行い、トレーニングのためのサンプルベースの双方向学習アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-02-05T04:25:28Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。