Fugu-MT 論文翻訳(概要): A Study of Performance of Optimal Transport

論文の概要: A Study of Performance of Optimal Transport

arxiv url: http://arxiv.org/abs/2005.01182v1
Date: Sun, 3 May 2020 20:37:05 GMT
ステータス: 処理完了
システム内更新日: 2022-12-07 06:58:52.738725
Title: A Study of Performance of Optimal Transport
Title（参考訳）: 最適輸送性能に関する研究
Authors: Yihe Dong, Yu Gao, Richard Peng, Ilya Razenshteyn, Saurabh Sawlani
Abstract要約: 本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 16.847501106437534
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We investigate the problem of efficiently computing optimal transport (OT) distances, which is equivalent to the node-capacitated minimum cost maximum flow problem in a bipartite graph. We compare runtimes in computing OT distances on data from several domains, such as synthetic data of geometric shapes, embeddings of tokens in documents, and pixels in images. We show that in practice, combinatorial methods such as network simplex and augmenting path based algorithms can consistently outperform numerical matrix-scaling based methods such as Sinkhorn [Cuturi'13] and Greenkhorn [Altschuler et al'17], even in low accuracy regimes, with up to orders of magnitude speedups. Lastly, we present a new combinatorial algorithm that improves upon the classical Kuhn-Munkres algorithm.
Abstract（参考訳）: 2部グラフにおけるノード容量最小コスト最大フロー問題と等価な最適輸送(OT)距離を効率的に計算する問題について検討する。我々は,幾何形状の合成データや文書へのトークンの埋め込み,画像中のピクセルなど,複数の領域のデータに対するot距離を計算する際のランタイムを比較した。実際,ネットワーク・シンプレックスや拡張パスベースアルゴリズムといった組合せ手法は,低精度のシステムであっても,最大最大速度アップで,シンクホーン [cuturi'13] やグリーンホーン [altschuler et al'17] のような数値行列スケーリングベースの手法を一貫して上回ることができる。最後に,従来のKuhn-Munkresアルゴリズムを改良した新しい組合せアルゴリズムを提案する。

関連論文リスト

Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [15.128885770407132]
本研究では, エントロピー的最適輸送, ミラー降下, 共役勾配の文献から, 最適輸送のための新しいアルゴリズムを設計する。我々のスケーラブルでGPU並列化可能なアルゴリズムは、ワッサースタイン距離を極端精度で計算することができ、数値安定性の問題なく相対誤差レート10～8ドルに達することができる。
論文参考訳（メタデータ） (2023-07-17T14:09:43Z)
Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文参考訳（メタデータ） (2023-02-14T22:12:16Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文参考訳（メタデータ） (2022-10-14T01:42:05Z)
Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More [7.484063729015126]
最適輸送のためのコスト行列の2つの効率的な対数線形時間近似を提案する。これらの近似は、複雑な高次元空間に対してもよく機能するエントロピー規則化OTに対する一般的な対数線形時間アルゴリズムを可能にする。グラフ距離回帰のために,グラフニューラルネットワーク(GNN)と拡張シンクホーンを組み合わせたグラフトランスポートネットワーク(GTN)を提案する。
論文参考訳（メタデータ） (2021-07-14T17:40:08Z)
Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文参考訳（メタデータ） (2021-06-08T15:54:44Z)
Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
本稿では,ネステロフの平滑化手法に基づく効率と精度をさらに向上させる新しいアルゴリズムを提案する。提案手法は,同じパラメータでより高速な収束と精度を実現する。
論文参考訳（メタデータ） (2021-04-12T20:23:29Z)
Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文参考訳（メタデータ） (2021-04-02T16:05:00Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
論文参考訳（メタデータ） (2020-01-12T15:54:20Z)

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