論文の概要: Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

• arxiv url: http://arxiv.org/abs/2605.20122v1
• Date: Tue, 19 May 2026 17:10:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.547338
• Title: Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
• Title（参考訳）: ワッサーシュタイン距離推定のための計算統計的実行量の最適化
• Authors: Peter Matthew Jacobs, Jeff M. Phillips,
• Abstract要約: 正方形距離は確率分布間の差を測定するのによく使われるツールである。 我々は,サンプルの正規カルテシアングリッドスケッチを導入するためのSample-$計算パラダイムを開発した。 我々は、$W(P, Q)$を$-max(2,fracd+1+o(1)1+)$ time for $0 1$ Hlder smooth distributions の$$エラー内で近似する。
• 参考スコア（独自算出の注目度）: 8.375876290025586
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size $n$ from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems $\left( d \in \{2,3\} \right)$, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of $n$ and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to $ε$-additive error in expectation with respect to the sampling; we allow $O(1)$ computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under $α$-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate $W_2^2(P,Q)$ within $ε$ error in $ε^{-\max(2,\frac{d+1+o(1)}{1+α})}$ time for $0 < α< 1$ Hölder smooth distributions $P,Q$ on $(0,1)^{d}$; an optimal $Θ(ε^{-2})$ for $α> 1/2$ when $d=2$ and nearly optimal as $α\to 1$ when $d = 3$.
• Abstract（参考訳）: 正方形ワッサーシュタイン距離は確率分布間の差を測定するのによく使われるツールである。 この距離は通常、2つの基礎となるランダムサンプルから n$ の大きさの経験的測度の間で計算される。 残念なことに、低次元ユークリッド空間問題 $\left(d \in \{2,3\} \right)$ であっても、近似的あるいは正確な精度を持つワッサーシュタイン距離計算のアルゴリズムは、$n$ の関数と所望の精度で実行時に不十分なスケールを保証している。 これに対し,本研究の目的は,標本収集に要する$O(1)$の計算コストを,標本採取に要する$O(1)$の計算コストを期待して,潜在的にスムーズな測定値と最大$ε$-加法誤差の間の標本から推定することである。 そこで本研究では,サンプルの正規カルテジアングリッドスケッチを導入するSample-Sketch-Solveパラダイムを提案する。 我々は、(特に$α$-Hölderの滑らかな分布の下で)漸近誤差を増大させることなくデータを圧縮でき、また、より高速な正確なアルゴリズムを実現する構造を正規化できることを示した。 最終的に$W_2^2(P, Q)$ in $ε$ error in $ε^{-\max(2,\frac{d+1+o(1)}{1+α})}$time for $0 < α<1$ Hölder smooth distributions $P,Q$ on $(0,1)^{d}$; antimal $(ε^{-2})$ for $α> 1/2$ if $d=2$ and almost optimal as $α\to 1$ if $d = 3$.} となる。

関連論文リスト

• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Multiple-policy Evaluation via Density Estimation [30.914344538340412]
  本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。 低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
  論文  参考訳（メタデータ） (2024-03-29T23:55:25Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
  本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。 また、ディキンウォークの「ソフトパイ」バージョンも提示する。
  論文  参考訳（メタデータ） (2021-11-07T13:44:50Z)

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

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