論文の概要: On Multimarginal Partial Optimal Transport: Equivalent Forms and
Computational Complexity
- arxiv url: http://arxiv.org/abs/2108.07992v1
- Date: Wed, 18 Aug 2021 06:46:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-19 14:47:07.689724
- Title: On Multimarginal Partial Optimal Transport: Equivalent Forms and
Computational Complexity
- Title（参考訳）: 多層部分最適輸送について:等式と計算複雑性
- Authors: Khang Le and Huy Nguyen and Tung Pham and Nhat Ho
- Abstract要約: 我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。
まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。
我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
- 参考スコア（独自算出の注目度）: 11.280177531118206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the multi-marginal partial optimal transport (POT) problem between
$m$ discrete (unbalanced) measures with at most $n$ supports. We first prove
that we can obtain two equivalence forms of the multimarginal POT problem in
terms of the multimarginal optimal transport problem via novel extensions of
cost tensor. The first equivalence form is derived under the assumptions that
the total masses of each measure are sufficiently close while the second
equivalence form does not require any conditions on these masses but at the
price of more sophisticated extended cost tensor. Our proof techniques for
obtaining these equivalence forms rely on novel procedures of moving mass in
graph theory to push transportation plan into appropriate regions. Finally,
based on the equivalence forms, we develop optimization algorithm, named
ApproxMPOT algorithm, that builds upon the Sinkhorn algorithm for solving the
entropic regularized multimarginal optimal transport. We demonstrate that the
ApproxMPOT algorithm can approximate the optimal value of multimarginal POT
problem with a computational complexity upper bound of the order
$\tilde{\mathcal{O}}(m^3(n+1)^{m}/ \varepsilon^2)$ where $\varepsilon > 0$
stands for the desired tolerance.
- Abstract（参考訳）: 我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。
まず,マルチマルジナルポット問題の2つの同値形式を,コストテンソルの新規拡張によるマルチマルジナル最適輸送問題の観点から得られることを証明した。
第1同値形式は、各測度の総質量が十分近いという仮定の下で導かれるが、第2同値形式はこれらの質量に関する条件を必要とせず、より洗練された拡張コストテンソルの価格で導かれる。
これらの等価性を得るための実証技術は、グラフ理論における質量移動の新しい手順に依存し、輸送計画が適切な地域へ押し寄せる。
最後に,同値形式に基づく最適化アルゴリズムであるApproxMPOTアルゴリズムを開発し,エントロピー正規化マルチマルジナル最適輸送の解法であるシンクホーンアルゴリズムを構築した。
近似ポットアルゴリズムは、次数 $\tilde{\mathcal{o}}(m^3(n+1)^{m}/ \varepsilon^2)$ の計算複雑性の上限を持つ多元ポット問題の最適値を近似できることを実証する。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and
Efficient Gradient Methods [17.14725907264431]
本稿では,少なくとも$n$の支持を持つ2つの不均衡測度間の部分最適輸送(POT)問題について検討する。
我々はPOTの新しいラウンドリングアルゴリズムを提案し、次に、$mathcalwidetilde O(n2/varepsilon4)$の複雑さを補正した実行可能なシンクホーン手順を提供する。
論文 参考訳（メタデータ） (2023-12-21T15:56:09Z) - Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs [49.1574468325115]
ニューマライズフロー」は、深層ニューラルネットワークを用いて確率測度間の可逆輸送マップを構築するタスクに関連している。
我々は、絶対連続測度$mu,nuinmathcalP(mathbbRn)$間の$Wamma$-optimal transport map $T$を線形制御ニューラルネットワークのフローとして回収する問題を考える。
論文 参考訳（メタデータ） (2023-11-02T17:17:03Z) - Projected Langevin dynamics and a gradient flow for entropic optimal
transport [0.8057006406834466]
エントロピー規則化された最適輸送からサンプリングした類似拡散力学を導入する。
部分多様体 $Pi(mu,nu)$ の誘導されたワッサーシュタイン幾何学の研究により、SDE はこの結合空間上のワッサーシュタイン勾配フローとみなすことができると論じる。
論文 参考訳（メタデータ） (2023-09-15T17:55:56Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal
Transport [0.483420384410068]
エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。
また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大させることも検討した。
論文 参考訳（メタデータ） (2021-10-25T06:52:45Z) - On the complexity of the optimal transport problem with graph-structured
cost [9.24979291231758]
マルチマージ最適輸送(Multi-marginal optimal transport、MOT)は、複数の辺縁への最適輸送の一般化である。
MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。
論文 参考訳（メタデータ） (2021-10-01T19:29:59Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳（メタデータ） (2021-07-13T12:31:06Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Linear Optimal Transport Embedding: Provable Wasserstein classification
for certain rigid transformations and perturbations [79.23797234241471]
分布の区別は多くの科学分野において重要な問題である。
線形最適輸送(LOT)は分布の空間を$L2$-スペースに埋め込む。
複数の分布分類問題に対するLOTの利点を実証する。
論文 参考訳（メタデータ） (2020-08-20T19:09:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。