論文の概要: On the complexity of the optimal transport problem with graph-structured cost

• arxiv url: http://arxiv.org/abs/2110.00627v1
• Date: Fri, 1 Oct 2021 19:29:59 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-05 15:08:32.557507
• Title: On the complexity of the optimal transport problem with graph-structured cost
• Title（参考訳）: グラフ構造コストによる最適輸送問題の複雑性について
• Authors: Jiaojiao Fan, Isabel Haasler, Johan Karlsson, Yongxin Chen
• Abstract要約: マルチマージ最適輸送(Multi-marginal optimal transport、MOT)は、複数の辺縁への最適輸送の一般化である。 MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。
• 参考スコア（独自算出の注目度）: 9.24979291231758
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. With $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal{\tilde O}(d(G)m n^2\epsilon^{-2})$ bound for a $\epsilon$-accuracy when the problem is associated with a tree with diameter $d(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.
• Abstract（参考訳）: multi-marginal optimal transport (mot) は、複数の辺への最適輸送の一般化である。 最適なトランスポートは、多くの機械学習アプリケーションで重要なツールへと進化し、そのマルチマルジナル拡張は、機械学習の分野における新たな課題に対処するために開いている。 しかし、MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。 幸いなことに、バリセンタや補間問題などの多くのアプリケーションでは、コスト関数は構造に依存しており、これは近年、効率的な計算方法の開発に利用されてきた。 この研究では、これらの手法の計算限界を導出する。 m$ の辺分布が$n$ の点でサポートされたとき、直径 $d(G)$ のツリーと関係があるとき、$$$ epsilon$-精度に対して$ \mathcal{\tilde O}(d(G)m n^2\epsilon^{-2})$ が与えられる。 星の形をした木に対応するワッサーシュタイン・バリセンタ問題の特別な場合、我々の境界はそれに対応する既存の複雑さと一致している。

関連論文リスト

• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  最適輸送理論はそのような写像を構築するための原則化された枠組みを提供する。 本稿では,Wasserstein-1に基づく新しい最適輸送解法を提案する。 実験により,提案した解法は,2次元データセット上に一意かつ単調な写像を求める際に,$W$ OTソルバを模倣できることを示した。
  論文  参考訳（メタデータ） (2024-11-01T14:23:19Z)
• Progressive Entropic Optimal Transport Solvers [33.821924561619895]
  本稿では,計画図と輸送地図の両方を推定できる新しいEOT解法(ProgOT)を提案する。 我々は,ProgOTが標準解法よりも高速で堅牢な代替手段であることを示す実験的な証拠を提供する。 また、最適な輸送地図を推定するためのアプローチの統計的整合性も証明する。
  論文  参考訳（メタデータ） (2024-06-07T16:33:08Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters [0.0]
  N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。 高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2022-02-02T10:59:54Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。 まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。 我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
  論文  参考訳（メタデータ） (2021-08-18T06:46:59Z)
• Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems [0.0]
  CG内の二重状態が「逆」の役割を果たすMMOT用に作られた遺伝的学習法を使用します。 最大120のグリッドポイントと最大30のマージンを持つベンチマーク問題に対して,本手法は常に精度を見出した。
  論文  参考訳（メタデータ） (2021-03-23T15:24:50Z)
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance [36.97843660480747]
  wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。 最近提案された次元の呪いを和らげるためのアプローチは、サンプルデータを低次元の部分空間に投影し、それから投影されたデータ間のワッサーシュタイン距離を計算することである。 しかし、このアプローチは、実際には非常に難しいStiefel多様体上の最大分問題を解決する必要があります。 本研究では,Stiefel多様体上の正規化最大ミン問題の新たな再構成に基づく,この問題を解くための新しいブロック座標降下法(RBCD)を提案する。
  論文  参考訳（メタデータ） (2020-12-09T17:47:56Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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