論文の概要: Dimensionality Reduction for Wasserstein Barycenter
- arxiv url: http://arxiv.org/abs/2110.08991v2
- Date: Tue, 19 Oct 2021 01:10:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-20 12:01:29.305861
- Title: Dimensionality Reduction for Wasserstein Barycenter
- Title（参考訳）: Wasserstein Barycenter の次元化
- Authors: Zachary Izzo, Sandeep Silwal, Samson Zhou
- Abstract要約: 本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。
ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。
また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
- 参考スコア（独自算出の注目度）: 6.327655795051619
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Wasserstein barycenter is a geometric construct which captures the notion
of centrality among probability distributions, and which has found many
applications in machine learning. However, most algorithms for finding even an
approximate barycenter suffer an exponential dependence on the dimension $d$ of
the underlying space of the distributions. In order to cope with this "curse of
dimensionality," we study dimensionality reduction techniques for the
Wasserstein barycenter problem. When the barycenter is restricted to support of
size $n$, we show that randomized dimensionality reduction can be used to map
the problem to a space of dimension $O(\log n)$ independent of both $d$ and
$k$, and that \emph{any} solution found in the reduced dimension will have its
cost preserved up to arbitrary small error in the original space. We provide
matching upper and lower bounds on the size of the reduced dimension, showing
that our methods are optimal up to constant factors. We also provide a coreset
construction for the Wasserstein barycenter problem that significantly
decreases the number of input distributions. The coresets can be used in
conjunction with random projections and thus further improve computation time.
Lastly, our experimental results validate the speedup provided by
dimensionality reduction while maintaining solution quality.
- Abstract（参考訳）: wasserstein barycenterは、確率分布間の中心性の概念を捉えた幾何学的構成であり、機械学習に多くの応用がある。
しかし、近似的なバリーセンターを見つけるアルゴリズムの多くは、分布の基底空間の次元 $d$ に指数関数的に依存する。
この「次元の曲線」に対処するために,ワッサースタイン・バリセンター問題の次元性低減手法について検討した。
barycenter が $n$ の大きさのサポートに制限されている場合、ランダム化された次元の縮小は、その問題を $d$ と $k$ の両方に依存しない次元 $o(\log n)$ の空間にマッピングするのに使用され、縮小次元にある \emph{any} の解は元の空間における任意の小さな誤差までコストが保たれることを示した。
縮小次元の大きさの上限値と下限値とを一致させて,本手法が定数因子まで最適であることを示す。
また,wasserstein barycenter問題に対するコアセット構成も提供し,入力分布の数を大幅に減少させる。
コアセットはランダムなプロジェクションと組み合わせて使用することができ、計算時間をさらに改善することができる。
最後に, ソリューションの品質を維持しつつ, 次元減少によるスピードアップを検証した。
関連論文リスト
- Max-sliced Wasserstein concentration and uniform ratio bounds of empirical measures on RKHS [9.783697404304025]
最適なトランスポートとワッサーシュタイン距離$mathcalW_p$は最近、統計学、機械学習、データサイエンス、物理科学の分野で多くの応用例を見てきた。
しかし、これらの応用は次元性の呪いによって厳しく制限されているため、これらの問題を推定するために必要なデータポイントの数は次元において指数関数的に増加する。
ここでは、これらの変種の一つ、すなわち最大スライスされたワッサーシュタイン計量 $overlinemathcalW_p$ に焦点を当てる。
論文 参考訳（メタデータ） (2024-05-21T18:47:43Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
本稿では,Wasserstein Barycenter問題を解くための新しいスケーラブルなアプローチを提案する。
我々の手法は最近のNeural OTソルバをベースとしている。
また,提案手法の理論的誤差境界も確立する。
論文 参考訳（メタデータ） (2024-02-06T09:17:07Z) - Krylov Cubic Regularized Newton: A Subspace Second-Order Method with
Dimension-Free Convergence Rate [83.3933097134767]
次元に依存しない大域収束率を$Oleft(frac1mk+frac1k2right)$とする,新しい部分空間正規化ニュートン法を導入する。
提案手法は,特に高次元問題に対して,既存のランダム部分空間法よりも高速に収束する。
論文 参考訳（メタデータ） (2024-01-05T20:24:18Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
生成モデルを用いて連続測度のワッサーシュタイン2バリセンターを近似するアルゴリズムを提案する。
有名人の顔のデータセットに基づいて、バリセンタアルゴリズムの定量的評価に使用できるAve, celeba!データセットを構築した。
論文 参考訳（メタデータ） (2022-01-28T16:59:47Z) - Randomized Dimensionality Reduction for Facility Location and
Single-Linkage Clustering [13.208510864854894]
ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。
本稿では,施設配置問題と単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。
論文 参考訳（メタデータ） (2021-07-05T05:55:26Z) - 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) - Wasserstein barycenters are NP-hard to compute [0.0]
Wasserstein barycenters(a.k.a.)の計算の問題
Optimal Transport Barycenters)は、データサイエンスの多くの応用により、近年注目を集めています。
この指数依存性が依存に対して即興であるかどうかは明らかな疑問である。
本稿では,計算における「次元の帰結」を明らかにする。
論文 参考訳（メタデータ） (2021-01-04T17:16:45Z) - Sinkhorn Barycenter via Functional Gradient Descent [125.89871274202439]
我々はシンクホーン発散の下で確率分布の集合のバリ中心を計算することの問題を考察する。
この問題は最近、グラフィックス、学習、ビジョンなど、さまざまな領域にまたがるアプリケーションを見つけました。
Sinkhorn Descent という関数勾配降下法を開発した。
論文 参考訳（メタデータ） (2020-07-20T20:16:47Z) - On a minimum enclosing ball of a collection of linear subspaces [16.466372560527827]
本稿では、線型部分空間の集合のミニマックス中心について述べる。
ミニマックスセンターのランクによってパラメータ化される最適化問題を提案・解決する。
目的を拡大し、ランク=k$ミニマックス中心で失われた情報をペナライズすることにより、最適な次元である$k*$と中心部分空間である$U* in$Gr$(k*,n)$を最小囲み球の中心で共に回収する。
論文 参考訳（メタデータ） (2020-03-27T15:00:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。