論文の概要: A Push-Relabel Based Additive Approximation for Optimal Transport
- arxiv url: http://arxiv.org/abs/2203.03732v1
- Date: Mon, 7 Mar 2022 21:40:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-09 15:42:16.326058
- Title: A Push-Relabel Based Additive Approximation for Optimal Transport
- Title（参考訳）: プッシュ・レラベルに基づく最適輸送のための加法近似
- Authors: Nathaniel Lahn, Sharath Raghvendra, Kaiyi Zhang
- Abstract要約: 最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
- 参考スコア（独自算出の注目度）: 5.111364864495785
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimal Transport is a popular distance metric for measuring similarity
between distributions. Exact algorithms for computing Optimal Transport can be
slow, which has motivated the development of approximate numerical solvers
(e.g. Sinkhorn method). We introduce a new and very simple combinatorial
approach to find an $\varepsilon$-approximation of the OT distance. Our
algorithm achieves a near-optimal execution time of $O(n^2/\varepsilon^2)$ for
computing OT distance and, for the special case of the assignment problem, the
execution time improves to $O(n^2/\varepsilon)$. Our algorithm is based on the
push-relabel framework for min-cost flow problems.
Unlike the other combinatorial approach (Lahn, Mulchandani and Raghvendra,
NeurIPS 2019) which does not have a fast parallel implementation, our algorithm
has a parallel execution time of $O(\log n/\varepsilon^2)$. Interestingly,
unlike the Sinkhorn algorithm, our method also readily provides a compact
transport plan as well as a solution to an approximate version of the dual
formulation of the OT problem, both of which have numerous applications in
Machine Learning. For the assignment problem, we provide both a CPU
implementation as well as an implementation that exploits GPU parallelism.
Experiments suggest that our algorithm is faster than the Sinkhorn algorithm,
both in terms of CPU and GPU implementations, especially while computing
matchings with a high accuracy.
- Abstract（参考訳）: 最適輸送は分布間の類似度を測定するための一般的な距離計量である。
最適輸送を計算するための厳密なアルゴリズムは遅くなり、近似数値解法(例えばシンクホーン法)の開発の動機となった。
我々は、OT距離の$\varepsilon$-approximationを求めるために、新しく非常に単純な組合せアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n^2/\varepsilon^2)$のほぼ最適実行時間を実現し、特別の場合には、O(n^2/\varepsilon)$に改善する。
本アルゴリズムは, 最小コストフロー問題に対するPush-relabelフレームワークに基づいている。
高速な並列実装を持たない他の組合せアプローチ(Lahn, Mulchandani, Raghvendra, NeurIPS 2019)とは異なり、我々のアルゴリズムは並列実行時間を$O(\log n/\varepsilon^2)$とする。
興味深いことに、Sinkhornアルゴリズムとは違って、我々の手法はコンパクトな輸送計画とOT問題の双対定式化の解も容易に提供し、どちらも機械学習に多くの応用がある。
代入問題に対しては、CPU実装とGPU並列性を利用した実装の両方を提供する。
実験の結果,このアルゴリズムは,特に高い精度でマッチングを計算しながら,cpuとgpuの実装の両方において,spinhornアルゴリズムよりも高速であることが示唆された。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision [6.574107319036238]
Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。
既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
論文 参考訳（メタデータ） (2022-02-01T14:06:27Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。