論文の概要: Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

• arxiv url: http://arxiv.org/abs/2405.15441v2
• Date: Thu, 30 May 2024 02:23:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 20:05:24.798846
• Title: Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
• Title（参考訳）: Kernel Max-Sliced Wasserstein 距離の統計的および計算的保証
• Authors: Jie Wang, March Boedihardjo, Yao Xie,
• Abstract要約: カーネル最大スライシング (KMS) ワッサーシュタイン距離は、この目的のために開発された。 KMS の 2$-Wasserstein 距離の計算は NP-hard であることを示す。
• 参考スコア（独自算出の注目度）: 9.608373793625107
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal transport has been very successful for various machine learning tasks; however, it is known to suffer from the curse of dimensionality. Hence, dimensionality reduction is desirable when applied to high-dimensional data with low-dimensional structures. The kernel max-sliced (KMS) Wasserstein distance is developed for this purpose by finding an optimal nonlinear mapping that reduces data into $1$ dimensions before computing the Wasserstein distance. However, its theoretical properties have not yet been fully developed. In this paper, we provide sharp finite-sample guarantees under milder technical assumptions compared with state-of-the-art for the KMS $p$-Wasserstein distance between two empirical distributions with $n$ samples for general $p\in[1,\infty)$. Algorithm-wise, we show that computing the KMS $2$-Wasserstein distance is NP-hard, and then we further propose a semidefinite relaxation (SDR) formulation (which can be solved efficiently in polynomial time) and provide a relaxation gap for the SDP solution. We provide numerical examples to demonstrate the good performance of our scheme for high-dimensional two-sample testing.
• Abstract（参考訳）: 最適輸送は様々な機械学習タスクで非常に成功したが、次元性の呪いに苦しむことが知られている。 したがって、低次元構造を持つ高次元データに適用する場合、次元減少が望ましい。 カーネル最大スライシング(KMS)ワッサースタイン距離は、ワッサースタイン距離を計算する前にデータを1ドルで次元に還元する最適な非線形写像を求めることによって、この目的のために開発された。 しかし、その理論的性質はまだ完全には発展していない。 本稿では、KMS$p$-ワッサーシュタイン距離と一般的な$p\in[1,\infty)$に対する$n$サンプルの2つの経験的分布に対する最先端のKMS$p$-Wasserstein距離と比較して、より穏やかな技術的仮定の下で、鋭い有限サンプル保証を提供する。 アルゴリズム的に、KMS 2$-Wasserstein 距離の計算はNPハードであることを示し、さらに、多項式時間で効率的に解ける半有限緩和法(SDR)の定式化を提案し、SDPソリューションに緩和ギャップを与える。 本研究では,高次元2サンプル試験における提案手法の優れた性能を示す数値的な例を示す。

関連論文リスト

• Private Geometric Median [10.359525525715421]
  データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。 我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
  論文  参考訳（メタデータ） (2024-06-11T16:13:09Z)
• Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
  近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。 本稿では,低次元センサマシン最適化問題に適用する。
  論文  参考訳（メタデータ） (2024-03-12T01:27:44Z)
• 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)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  ワッサーシュタイン・バリセンターは、最適輸送に基づく確率測度の重み付き平均の幾何学的概念を提供する。 本稿では,Wasserstein-2 バリセンタのサンプルアクセスを演算するスケーラブルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-02T21:01:13Z)
• Two-sample Test using Projected Wasserstein Distance [18.46110328123008]
  統計学と機械学習の基本的な問題である2サンプルテストのための予測されたワッサースタイン距離を開発する。 重要な貢献は、投影された確率分布の間のワッサーシュタイン距離を最大化する低次元線型写像を見つけるために最適射影を結合することである。
  論文  参考訳（メタデータ） (2020-10-22T18:08:58Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。 私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。 次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
  論文  参考訳（メタデータ） (2020-06-22T14:35:33Z)
• Augmented Sliced Wasserstein Distances [55.028065567756066]
  拡張スライスされたワッサーシュタイン距離(ASWD)と呼ばれる新しい距離測定法を提案する。 ASWDは、ニューラルネットワークによってパラメータ化された高次元超曲面への最初のマッピングサンプルによって構成される。 数値的な結果から、ASWDは、合成問題と実世界の問題の両方において、他のワッサーシュタイン変種を著しく上回っていることが示されている。
  論文  参考訳（メタデータ） (2020-06-15T23:00:08Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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