論文の概要: Wasserstein barycenters are NP-hard to compute

• arxiv url: http://arxiv.org/abs/2101.01100v1
• Date: Mon, 4 Jan 2021 17:16:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-11 22:47:31.178828
• Title: Wasserstein barycenters are NP-hard to compute
• Title（参考訳）: Wasserstein Barycentersは計算にNPハードである
• Authors: Jason M. Altschuler and Enric Boix-Adsera
• Abstract要約: Wasserstein barycenters(a.k.a.)の計算の問題 Optimal Transport Barycenters)は、データサイエンスの多くの応用により、近年注目を集めています。 この指数依存性が依存に対して即興であるかどうかは明らかな疑問である。 本稿では,計算における「次元の帰結」を明らかにする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) has attracted considerable recent attention due to many applications in data science. While there exist polynomial-time algorithms in any fixed dimension, all known runtimes suffer exponentially in the dimension. It is an open question whether this exponential dependence is improvable to a polynomial dependence. This paper proves that unless P=NP, the answer is no. This uncovers a "curse of dimensionality" for Wasserstein barycenter computation which does not occur for Optimal Transport computation. Moreover, our hardness results for computing Wasserstein barycenters extend to approximate computation, to seemingly simple cases of the problem, and to averaging probability distributions in other Optimal Transport metrics.
• Abstract（参考訳）: Wasserstein Barycenters (a.k.a.) の計算の問題点 データサイエンスにおける多くの応用により、最適なトランスポートバリセンタ)が近年注目されている。 任意の固定次元に多項式時間アルゴリズムが存在するが、すべての既知のランタイムはその次元で指数関数的に苦しむ。 この指数依存が多項式依存に対して即効性を持つかどうかは、明らかな問題である。 この論文は、P=NP がなければ、答えは No であることを示す。 これは、最適な輸送計算では起こらないワッサースタイン・バリセン計算の「次元の曲線」を明らかにする。 さらに,wasserstein barycentersの計算の難しさは,近似計算,一見単純な問題,そして他の最適輸送指標における確率分布の平均化にまで及んでいる。

関連論文リスト

• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters [0.0]
  N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。 高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2022-02-02T10:59:54Z)
• Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
  生成モデルを用いて連続測度のワッサーシュタイン2バリセンターを近似するアルゴリズムを提案する。 有名人の顔のデータセットに基づいて、バリセンタアルゴリズムの定量的評価に使用できるAve, celeba!データセットを構築した。
  論文  参考訳（メタデータ） (2022-01-28T16:59:47Z)
• Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
  本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。 ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。 また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
  論文  参考訳（メタデータ） (2021-10-18T02:57:25Z)
• Fixed Support Tree-Sliced Wasserstein Barycenter [40.087553363884396]
  本研究では, 固定支持木-ワッセルシュタインバリセンタ (FS-TWB) と呼ばれる木-ワッセルシュタイン距離下のバリセンタと, 固定支持木-スライスされたワッセルシュタインバリセンタ (FS-TSWB) と呼ばれる拡張部を提案する。 FS-TWB と FS-TSWB は,元の Wasserstein バリセンタよりも2桁早く解けることを示す。
  論文  参考訳（メタデータ） (2021-09-08T04:50:33Z)
• 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 can be computed in polynomial time in fixed dimension [2.66512000865131]
  ヴァッサーシュタインのバリセンタが時間で計算できるか、高精度に計算できるかは不明である。 我々のアプローチは指数関数サイズの線形プログラミングの定式化を解くことである。
  論文  参考訳（メタデータ） (2020-06-14T20:24:27Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。