論文の概要: 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})$ が与えられる。
星の形をした木に対応するワッサーシュタイン・バリセンタ問題の特別な場合、我々の境界はそれに対応する既存の複雑さと一致している。
関連論文リスト
- 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) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - 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) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳(メタデータ) (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。