論文の概要: New Algorithmic Directions in Optimal Transport and Applications for Product Spaces
- arxiv url: http://arxiv.org/abs/2509.21502v1
- Date: Thu, 25 Sep 2025 19:58:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-29 20:57:53.967311
- Title: New Algorithmic Directions in Optimal Transport and Applications for Product Spaces
- Title（参考訳）: 最適輸送における新しいアルゴリズムの方向性と製品空間への応用
- Authors: Salman Beigi, Omid Etesami, Mohammad Mahmoody, Amir Najafi,
- Abstract要約: アルゴリズムの観点から2つの高次元分布$mu,nu$ in$Rn$の最適輸送について検討する。
実行時間は、$mu,nu$の完全な表現サイズではなく、次元に依存する。
ガウス測度$varepsilon$の場合、ほとんどの$Phin$サンプルは距離$O(sqrtlog 1/varepsilon)$ in $poly(n/varepsilon)$にマッピングできる。
- 参考スコア（独自算出の注目度）: 5.9725566031600925
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study optimal transport between two high-dimensional distributions $\mu,\nu$ in $R^n$ from an algorithmic perspective: given $x \sim \mu$, find a close $y \sim \nu$ in $poly(n)$ time, where $n$ is the dimension of $x,y$. Thus, running time depends on the dimension rather than the full representation size of $\mu,\nu$. Our main result is a general algorithm for transporting any product distribution $\mu$ to any $\nu$ with cost $\Delta + \delta$ under $\ell_p^p$, where $\Delta$ is the Knothe-Rosenblatt transport cost and $\delta$ is a computational error decreasing with runtime. This requires $\nu$ to be "sequentially samplable" with bounded average sampling cost, a new but natural notion. We further prove: An algorithmic version of Talagrand's inequality for transporting the standard Gaussian $\Phi^n$ to arbitrary $\nu$ under squared Euclidean cost. For $\nu = \Phi^n$ conditioned on a set $\mathcal{S}$ of measure $\varepsilon$, we construct the sequential sampler in expected time $poly(n/\varepsilon)$ using membership oracle access to $\mathcal{S}$. This yields an algorithmic transport from $\Phi^n$ to $\Phi^n|\mathcal{S}$ in $poly(n/\varepsilon)$ time and expected squared distance $O(\log 1/\varepsilon)$, optimal for general $\mathcal{S}$ of measure $\varepsilon$. As corollary, we obtain the first computational concentration result (Etesami et al. SODA 2020) for Gaussian measure under Euclidean distance with dimension-independent transportation cost, resolving an open question of Etesami et al. Specifically, for any $\mathcal{S}$ of Gaussian measure $\varepsilon$, most $\Phi^n$ samples can be mapped to $\mathcal{S}$ within distance $O(\sqrt{\log 1/\varepsilon})$ in $poly(n/\varepsilon)$ time.
- Abstract（参考訳）: アルゴリズムの観点から、2つの高次元分布間の最適な輸送について研究する:$x \sim \mu$, find a close $y \sim \nu$ in $poly(n)$ time, where $n$ is the dimension of $x,y$。
したがって、実行時間は、$\mu,\nu$の完全な表現サイズではなく、次元に依存する。
我々の主な成果は、コスト$\Delta + \delta$ under $\ell_p^p$, where $\Delta$ is the Knothe-Rosenblatt transport cost, $\delta$は実行時に減少する計算誤差である。
これは、新しいが自然な概念である、有界な平均サンプリングコストを持つ「逐次サンプリング可能な」ために$\nu$を必要とする。
さらに、標準的なガウスの$\Phi^n$をユークリッドのコストで任意の$\nu$に輸送するアルゴリズム的なタラグランドの不等式が証明される。
for $\nu = \Phi^n$ conditioned on a set $\mathcal{S}$ of measure $\varepsilon$, we construct the sequence sampler in expected time $poly(n/\varepsilon)$ using membership oracle access to $\mathcal{S}$.
これは、$\Phi^n$から$\Phi^n|\mathcal{S}$ in $poly(n/\varepsilon)$ time and expected squared distance $O(\log 1/\varepsilon)$, optimal for general $\mathcal{S}$ of measure $\varepsilon$である。
特に、任意の$\mathcal{S}$ of Gaussian measure $\varepsilon$, most $\Phi^n$ sample can mapping to $\mathcal{S}$ within distance $O(\sqrt{\log 1/\varepsilon)$ in $poly(n/\varepsilon)$ time。
関連論文リスト
- Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳（メタデータ） (2025-08-09T08:28:06Z) - $k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation [16.942733472657622]
整数 $kgeq1$ と集合 $P$ of $n$ points in $REALd$ が与えられたとき、古典近似 $k$-PCA は Affinemph$fty distance を近似する。
実世界のデータセットに関するオープンコードと実験結果も提供されている。
論文 参考訳（メタデータ） (2025-07-19T14:00:50Z) - Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。
We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。
また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
論文 参考訳（メタデータ） (2025-03-26T03:36:36Z) - Sparsifying Suprema of Gaussian Processes [6.638504164134713]
我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。
また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
論文 参考訳（メタデータ） (2024-11-22T01:43:58Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳（メタデータ） (2020-06-23T20:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。