論文の概要: Discrete Optimal Transport with Independent Marginals is #P-Hard

• arxiv url: http://arxiv.org/abs/2203.01161v1
• Date: Wed, 2 Mar 2022 15:04:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-03 14:17:55.902032
• Title: Discrete Optimal Transport with Independent Marginals is #P-Hard
• Title（参考訳）: 独立な辺縁を持つ離散最適輸送は#pハードである
• Authors: Bahar Ta\c{s}kesen, Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, Karthik Natarajan
• Abstract要約: 2つのK次元離散ランダムベクトルの分布間のワッサーシュタイン距離を評価する最適輸送問題の計算複雑性について検討する。 我々は,第1の確率ベクトルの成分が任意の独立分布に従うとき,擬似多項式時間でワッサーシュタイン距離を近似する動的プログラミング型アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 10.631390265238002
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector are independent, then this number can be exponential in K even though the size of the problem description scales linearly with K. We prove that the described optimal transport problem is #P-hard even if all components of the first random vector are independent uniform Bernoulli random variables, while the second random vector has merely two atoms, and even if only approximate solutions are sought. We also develop a dynamic programming-type algorithm that approximates the Wasserstein distance in pseudo-polynomial time when the components of the first random vector follow arbitrary independent discrete distributions, and we identify special problem instances that can be solved exactly in strongly polynomial time.
• Abstract（参考訳）: 2つのK次元離散ランダムベクトルの分布間のワッサーシュタイン距離を評価する最適輸送問題の計算複雑性について検討する。 この問題の最もよく知られたアルゴリズムは、2つの分布の原子数の最大で多項式時間で実行される。 しかし、一方の確率ベクトルの成分が独立であれば、問題記述のサイズが k と線形にスケールしているにもかかわらず、この数は k において指数関数となり得る。第一の確率ベクトルのすべての成分が独立な一様ベルヌーイ確率変数であるのに対して、第二の確率ベクトルは2つの原子しか持たず、近似解のみを求める場合でも、記述された最適輸送問題は #p-hard であることが証明される。 また, 1次ランダムベクトルの成分が任意の独立離散分布に従う場合, 擬似多項時間でのwasserstein距離を近似する動的計画型アルゴリズムを開発し, 強多項式時間で正確に解くことができる特殊問題インスタンスを同定した。

関連論文リスト

• Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
  所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。 我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。 超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
  論文  参考訳（メタデータ） (2023-11-02T17:51:10Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Concentration of Random Feature Matrices in High-Dimensions [7.1171757928258135]
  ランダムな特徴行列のスペクトルは、ランダムな特徴回帰問題に使用される線形システムの条件付けに関する情報を提供する。 2つの入力変数に対する2つの設定を考える。どちらもランダム変数か、一方はランダム変数で、もう一方は十分に分離されている。
  論文  参考訳（メタデータ） (2022-04-14T13:01:27Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• HighDist Framework: Algorithms and Applications [0.5584060970507505]
  量子回路の出力分布のモードが与えられた閾値よりも大きいかどうかを判定する問題を導入する。 空間複雑性が分布領域の大きさの対数的であるこれらの問題の有望バージョンに対する量子アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-03-16T13:06:36Z)
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization [106.70006655990176]
  分散最適化問題は機械学習や統計学で広く発生する。 本稿では,変分輸送と呼ばれる粒子に基づく新しいアルゴリズムを提案する。 目的関数がpolyak-Lojasiewicz (PL) (Polyak, 1963) の機能バージョンと滑らかな条件を満たすとき、変分輸送は線形に収束することを示す。
  論文  参考訳（メタデータ） (2020-12-21T18:33:13Z)
• Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations [79.23797234241471]
  分布の区別は多くの科学分野において重要な問題である。 線形最適輸送(LOT)は分布の空間を$L2$-スペースに埋め込む。 複数の分布分類問題に対するLOTの利点を実証する。
  論文  参考訳（メタデータ） (2020-08-20T19:09:33Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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