論文の概要: Faster Wasserstein Distance Estimation with the Sinkhorn Divergence
- arxiv url: http://arxiv.org/abs/2006.08172v2
- Date: Thu, 29 Oct 2020 15:15:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 05:01:39.002243
- Title: Faster Wasserstein Distance Estimation with the Sinkhorn Divergence
- Title（参考訳）: Sinkhorn Divergenceによるより高速なワッサースタイン距離推定
- Authors: Lenaic Chizat (LMO), Pierre Roussillon (DMA), Flavien L\'eger (DMA),
Fran\c{c}ois-Xavier Vialard (Univ Gustave Eiffel), Gabriel Peyr\'e (DMA)
- Abstract要約: 正方形ワッサーシュタイン距離(英: squared Wasserstein distance)は、非パラメトリックな設定における確率分布を比較する量である。
そこで本研究では,シンクホーンの発散量を用いて推定する手法を提案する。
滑らかな密度に対して、この推定器はサンプルの複雑さに匹敵するが、より高い正規化レベルが可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The squared Wasserstein distance is a natural quantity to compare probability
distributions in a non-parametric setting. This quantity is usually estimated
with the plug-in estimator, defined via a discrete optimal transport problem
which can be solved to $\epsilon$-accuracy by adding an entropic regularization
of order $\epsilon$ and using for instance Sinkhorn's algorithm. In this work,
we propose instead to estimate it with the Sinkhorn divergence, which is also
built on entropic regularization but includes debiasing terms. We show that,
for smooth densities, this estimator has a comparable sample complexity but
allows higher regularization levels, of order $\epsilon^{1/2}$, which leads to
improved computational complexity bounds and a strong speedup in practice. Our
theoretical analysis covers the case of both randomly sampled densities and
deterministic discretizations on uniform grids. We also propose and analyze an
estimator based on Richardson extrapolation of the Sinkhorn divergence which
enjoys improved statistical and computational efficiency guarantees, under a
condition on the regularity of the approximation error, which is in particular
satisfied for Gaussian densities. We finally demonstrate the efficiency of the
proposed estimators with numerical experiments.
- Abstract（参考訳）: 正方形ワッサーシュタイン距離は、非パラメトリックな設定における確率分布を比較する自然な量である。
この量は、例えばSinkhornのアルゴリズムを用いて、$\epsilon$-accuracy のエントロピー正規化を加えることで、$\epsilon$-accuracy に解決できる離散的な最適輸送問題によって定義されるプラグイン推定器で推定される。
本研究は,エントロピー正規化に基づくが,デバイアス項を含むシンクホーン分岐を用いて推定する手法を提案する。
滑らかな密度では、この推定器はサンプルの複雑さに匹敵するが、より高い正規化レベル、すなわち$\epsilon^{1/2}$を許容する。
我々の理論解析は、ランダムにサンプリングされた密度と一様格子上の決定論的離散化の両方の場合をカバーする。
また, ガウス密度に特に満足する近似誤差の正則性条件下で, 統計的および計算効率の保証が向上した, シンクホーン分岐のリチャードソン外挿に基づく推定器の提案と解析を行った。
数値実験により提案した推定器の効率性を実証した。
関連論文リスト
- Noise-Free Sampling Algorithms via Regularized Wasserstein Proximals [3.4240632942024685]
ポテンシャル関数が支配する分布からサンプリングする問題を考察する。
本研究は, 決定論的な楽譜に基づくMCMC法を提案し, 粒子に対する決定論的進化をもたらす。
論文 参考訳（メタデータ） (2023-08-28T23:51:33Z) - Statistical, Robustness, and Computational Guarantees for Sliced
Wasserstein Distances [18.9717974398864]
スライスされたワッサーシュタイン距離は古典的なワッサーシュタイン距離の性質を保ちながら、高次元での計算と推定によりスケーラブルである。
このスケーラビリティを, (i) 経験的収束率, (ii) データの汚染に対する堅牢性, (iii) 効率的な計算方法という3つの重要な側面から定量化する。
論文 参考訳（メタデータ） (2022-10-17T15:04:51Z) - Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
本研究では, スコアマッチングの統計的効率と推定される分布の等尺性との間に, 密接な関係を示す。
これらの結果はサンプル状態と有限状態の両方で定式化する。
論文 参考訳（メタデータ） (2022-10-03T06:09:01Z) - Wasserstein Distributionally Robust Estimation in High Dimensions:
Performance Analysis and Optimal Hyperparameter Tuning [0.0]
雑音線形測定から未知パラメータを推定するための分布的ロバストな推定フレームワークを提案する。
このような推定器の2乗誤差性能を解析する作業に着目する。
凸凹最適化問題の解法として2乗誤差を復元できることを示す。
論文 参考訳（メタデータ） (2022-06-27T13:02:59Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳（メタデータ） (2021-10-07T17:51:10Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Fast Approximation of the Sliced-Wasserstein Distance Using
Concentration of Random Projections [19.987683989865708]
Sliced-Wasserstein distance (SW) は、機械学習アプリケーションでますます使われている。
本稿では,測度現象の集中を利用してSWを近似する新しい視点を提案する。
提案手法は多数のランダムなプロジェクションをサンプリングする必要はなく,通常のモンテカルロ近似と比較して正確かつ容易に利用できる。
論文 参考訳（メタデータ） (2021-06-29T13:56:19Z) - Finite sample approximations of exact and entropic Wasserstein distances
between covariance operators and Gaussian processes [0.0]
2つの中心ガウス過程間のシンクホーンの発散を一貫して効率的に推定できることを示す。
固定正規化パラメータでは、収束率は次元非依存であり、ヒルベルト-シュミット距離のそれと同じ順序である。
rkhs の少なくとも一方が有限次元であれば、ガウス過程の間の正確なワッサーシュタイン距離の it 次元依存サンプル複雑性が得られる。
論文 参考訳（メタデータ） (2021-04-26T06:57:14Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。