論文の概要: Hardness results for Multimarginal Optimal Transport problems

• arxiv url: http://arxiv.org/abs/2012.05398v1
• Date: Thu, 10 Dec 2020 01:36:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-15 06:07:35.165452
• Title: Hardness results for Multimarginal Optimal Transport problems
• Title（参考訳）: マルチマルジナル最適輸送問題に対する硬度結果
• Authors: Jason M. Altschuler and Enric Boix-Adsera
• Abstract要約: マルチマルジナル最適輸送(MOT)は、固定辺を持つ結合確率分布に対する線形プログラミングの問題である。 近年の研究では、MOTはポリ(n,k)サイズの暗黙表現を持つコストの特定のファミリーに対して、ポリ(n,k)時間可解であることが示されている。 本論文では,MOT問題に対するNP硬度および不近似結果を証明するツールキットを開発した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multimarginal Optimal Transport (MOT) is the problem of linear programming over joint probability distributions with fixed marginals. A key issue in many applications is the complexity of solving MOT: the linear program has exponential size in the number of marginals k and their support sizes n. A recent line of work has shown that MOT is poly(n,k)-time solvable for certain families of costs that have poly(n,k)-size implicit representations. However, it is unclear what further families of costs this line of algorithmic research can encompass. In order to understand these fundamental limitations, this paper initiates the study of intractability results for MOT. Our main technical contribution is developing a toolkit for proving NP-hardness and inapproximability results for MOT problems. We demonstrate this toolkit by using it to establish the intractability of a number of MOT problems studied in the literature that have resisted previous algorithmic efforts. For instance, we provide evidence that repulsive costs make MOT intractable by showing that several such problems of interest are NP-hard to solve--even approximately.
• Abstract（参考訳）: マルチマルジナル最適輸送(MOT)は、固定辺を持つ結合確率分布に対する線形プログラミングの問題である。 多くのアプリケーションにおいて鍵となる問題はmotの解決の複雑さである: 線形プログラムは、辺数 k とそのサポートサイズ n の指数関数的な大きさを持つ。最近の作業で、mot はpoly(n,k)-time であり、poly(n,k)-size implicit representations を持つ特定のコストファミリーに対して可解であることが示されている。 しかし、この一連のアルゴリズム研究がどのようなコストがかかるのかは明らかではない。 これらの基本的制約を理解するために,本論文はMOTの難読化結果の研究を開始する。 我々の主な技術的貢献は、MOT問題に対するNP硬さと不適応性を示すツールキットの開発である。 本手法は,過去のアルゴリズム的試みに抵抗した文献で研究されているmot問題の難解性を確立するために,このツールキットを用いて実証する。 例えば、抑止コストがMOTを誘引しやすくする証拠として、そのような関心事のいくつかがNP困難であることを示す。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Scalable Computation of Causal Bounds [11.193504036335503]
  本研究では、未観測の共創者と離散値の観測変数を持つ因果グラフ上の因果クエリの計算バウンダリの問題を考察する。 このような境界を計算するための既存の研究されていないアプローチは、線形プログラミング(LP)の定式化を使用しており、既存の解法にはすぐに難解になる。 このLPは,既存の手法に比べてはるかに大きな因果推論問題に対する境界を計算することができることを示す。
  論文  参考訳（メタデータ） (2023-08-04T21:00:46Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。 提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。 大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
  論文  参考訳（メタデータ） (2022-11-02T14:35:13Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• 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 the complexity of the optimal transport problem with graph-structured cost [9.24979291231758]
  マルチマージ最適輸送(Multi-marginal optimal transport、MOT)は、複数の辺縁への最適輸送の一般化である。 MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。
  論文  参考訳（メタデータ） (2021-10-01T19:29:59Z)
• Nonparametric estimation of continuous DPPs with kernel methods [0.0]
  パラメトリックおよび非パラメトリック推論法は、有限の場合、すなわち、点パターンが有限の基底集合に存在する場合において提案されている。 我々は、この最大可能性(MLE)問題の制限バージョンが、RKHSにおける非負関数に対する最近の表現定理の範囲内にあることを示す。 この有限次元問題を解くための固定点アルゴリズムを提案し,解析し,実証する。
  論文  参考訳（メタデータ） (2021-06-27T11:57:14Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Sliced Multi-Marginal Optimal Transport [21.82052188474956]
  複数の測度間の相違を定義できる最適輸送の一般化であるマルチマルジナル最適輸送について検討する。 分割されたマルチマルジナル不一致の計算は、多くの確率測度に対して非常にスケーラブルであり、最大107ドルのサンプルをサポートすることを示す。
  論文  参考訳（メタデータ） (2021-02-14T09:58:47Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)

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

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