論文の概要: Polynomial-time algorithms for Multimarginal Optimal Transport problems
with structure
- arxiv url: http://arxiv.org/abs/2008.03006v4
- Date: Sat, 16 Jul 2022 17:14:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 02:09:28.187412
- Title: Polynomial-time algorithms for Multimarginal Optimal Transport problems
with structure
- Title（参考訳）: 多変数最適輸送問題に対する多項式時間アルゴリズム
- Authors: Jason M. Altschuler and Enric Boix-Adsera
- Abstract要約: マルチマルジナル最適輸送(MOT)は、機械学習、統計学、科学の応用により、大きな関心を集めている。
本稿では,MOT をポリ(n,k) 時間で解ける構造が何か,という一般的な理論を発展させる。
- 参考スコア（独自算出の注目度）: 2.66512000865131
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multimarginal Optimal Transport (MOT) has attracted significant interest due
to applications in machine learning, statistics, and the sciences. However, in
most applications, the success of MOT is severely limited by a lack of
efficient algorithms. Indeed, MOT in general requires exponential time in the
number of marginals k and their support sizes n. This paper develops a general
theory about what "structure" makes MOT solvable in poly(n,k) time.
We develop a unified algorithmic framework for solving MOT in poly(n,k) time
by characterizing the "structure" that different algorithms require in terms of
simple variants of the dual feasibility oracle. This framework has several
benefits. First, it enables us to show that the Sinkhorn algorithm, which is
currently the most popular MOT algorithm, requires strictly more structure than
other algorithms do to solve MOT in poly(n,k) time. Second, our framework makes
it much simpler to develop poly(n,k) time algorithms for a given MOT problem.
In particular, it is necessary and sufficient to (approximately) solve the dual
feasibility oracle -- which is much more amenable to standard algorithmic
techniques.
We illustrate this ease-of-use by developing poly(n,k) time algorithms for
three general classes of MOT cost structures: (1) graphical structure; (2)
set-optimization structure; and (3) low-rank plus sparse structure. For
structure (1), we recover the known result that Sinkhorn has poly(n,k) runtime;
moreover, we provide the first poly(n,k) time algorithms for computing
solutions that are exact and sparse. For structures (2)-(3), we give the first
poly(n,k) time algorithms, even for approximate computation. Together, these
three structures encompass many -- if not most -- current applications of MOT.
- Abstract（参考訳）: マルチマルジナル最適輸送(MOT)は、機械学習、統計学、科学の応用によって大きな関心を集めている。
しかし、ほとんどのアプリケーションでは、MOTの成功は効率的なアルゴリズムの欠如によって著しく制限されている。
実際、MOT は一般に、辺数 k とそのサポートサイズ n の指数時間を必要とする。
本稿では,MOT をポリ(n,k) 時間で解ける構造が何か,という一般的な理論を発展させる。
我々は、異なるアルゴリズムが必要とする「構造」を二重実現可能性オラクルの単純な変種の観点から特徴づけることで、MOTをポリ(n,k)時間で解くための統一的なアルゴリズムフレームワークを開発する。
この枠組みにはいくつかの利点がある。
まず、現在最も人気のあるMOTアルゴリズムであるシンクホーンアルゴリズムが、ポリ(n,k)時間でMOTを解決するために他のアルゴリズムよりも厳密な構造を必要とすることを示す。
第二に、我々のフレームワークは、与えられたMOT問題に対するポリ(n,k)時間アルゴリズムの開発を非常に簡単にする。
特に、(ほぼ)双対実現可能性オラクルを解くには必要で十分である。
本稿では,motコスト構造の3つの汎用クラス,(1)グラフィカル構造,(2)セット最適化構造,(3)低ランク+スパース構造に対してpoly(n,k)時間アルゴリズムを開発することで,この使いやすさを示す。
構造 (1) に対して、シンクホーンがポリ(n,k) ランタイムを持つという既知の結果を回復し、さらに、正確でスパースな計算解に対する最初のポリ(n,k) 時間アルゴリズムを提供する。
構造(2)-(3)に対して、近似計算でさえも、最初のポリ(n,k)時間アルゴリズムを与える。
これら3つの構造は、MOTの現在の応用の多くを含む。
関連論文リスト
- EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。
EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。
我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
論文 参考訳（メタデータ） (2024-05-16T15:11:37Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Scalable Anytime Algorithms for Learning Formulas in Linear Temporal
Logic [2.631744051718347]
トレースを分類する公式を学習する際の問題点を考察する。
既存の解には2つの制限がある: それらは小さな公式を超えてスケールせず、結果を返すことなく計算資源を消費する。
我々は,両問題に対処する新しいアルゴリズムを導入する。我々のアルゴリズムは,従来よりも桁違いに大きい式を構築でき,いつでも可能である。
論文 参考訳（メタデータ） (2021-10-13T13:57:31Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z) - Optimal Sparse Decision Trees [25.043477914272046]
この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。
このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。
我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
論文 参考訳（メタデータ） (2019-04-29T17:56:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。