論文の概要: Fast Unbalanced Optimal Transport on a Tree

• arxiv url: http://arxiv.org/abs/2006.02703v3
• Date: Fri, 8 Jan 2021 04:35:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-25 09:26:44.098915
• Title: Fast Unbalanced Optimal Transport on a Tree
• Title（参考訳）: 木上の高速不均衡最適輸送
• Authors: Ryoma Sato, Makoto Yamada, Hisashi Kashima
• Abstract要約: 本研究では、アルゴリズムの観点から、不均衡な最適輸送問題の時間的複雑さを初めて考察する。 ユークリッド計量におけるカントロヴィチ・ルビンシテイン距離と最適部分輸送が強い四進時間では計算できないことを証明した。 そこで本研究では,木メータ上での準線形時間において,より一般的な不均衡な最適輸送問題を正確に解くアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 40.60905158071766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We reveal which problems in unbalanced optimal transport can/cannot be solved efficiently. Specifically, we prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time under the strong exponential time hypothesis. Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric. The proposed algorithm processes a tree with one million nodes in less than one second. Our analysis forms a foundation for the theoretical study of unbalanced optimal transport algorithms and opens the door to the applications of unbalanced optimal transport to million-scale datasets.
• Abstract（参考訳）: 本研究では,非平衡最適輸送問題の時間的複雑度を,アルゴリズム的観点から初めて検討する。 不均衡な最適輸送のどの問題が効率的に解けるかを明らかにする。 特に, ユークリッド計量におけるカントロヴィチ・ルビンシュタイン距離と最適部分移動は, 強い指数時間仮説の下では強い準二次時間では計算できないことを証明した。 そこで本研究では,木計量の準線形時間において,より一般的な不均衡な最適輸送問題を解くアルゴリズムを提案する。 提案手法では,100万ノードのツリーを1秒未満で処理する。 本解析は,不均衡最適輸送アルゴリズムの理論研究の基礎を成し,不均衡最適輸送の百万規模のデータセットへの適用への扉を開く。

関連論文リスト

• Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [15.128885770407132]
  本研究では, エントロピー的最適輸送, ミラー降下, 共役勾配の文献から, 最適輸送のための新しいアルゴリズムを設計する。 我々のスケーラブルでGPU並列化可能なアルゴリズムは、ワッサースタイン距離を極端精度で計算することができ、数値安定性の問題なく相対誤差レート10～8ドルに達することができる。
  論文  参考訳（メタデータ） (2023-07-17T14:09:43Z)
• Generative modeling of time-dependent densities via optimal transport and projection pursuit [3.069335774032178]
  本稿では,時間的モデリングのための一般的なディープラーニングアルゴリズムの代替として,安価に提案する。 我々の手法は最先端の解法と比較して非常に競争力がある。
  論文  参考訳（メタデータ） (2023-04-19T13:50:13Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Learning Ultrametric Trees for Optimal Transport Regression [10.524752369156337]
  与えられた離散距離空間に対して最適な木構造を求める。 私たちのキーとなるアイデアの1つは、問題を超測度空間に配置することである。
  論文  参考訳（メタデータ） (2022-10-21T22:54:42Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。 生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。 そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-03T13:45:36Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution [8.465228064780748]
  2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。 目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。 双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
  論文  参考訳（メタデータ） (2021-03-10T18:53:59Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)

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

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