論文の概要: A Fast and Accurate Splitting Method for Optimal Transport: Analysis and
Implementation
- arxiv url: http://arxiv.org/abs/2110.11738v1
- Date: Fri, 22 Oct 2021 12:16:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-25 15:56:58.052943
- Title: A Fast and Accurate Splitting Method for Optimal Transport: Analysis and
Implementation
- Title（参考訳）: 最適輸送のための高速かつ正確な分割法:解析と実装
- Authors: Vien V. Mai, Jacob Lindb\"ack, Mikael Johansson
- Abstract要約: 我々は,高速かつ信頼性の高い大規模最適輸送(OT)問題を,前例のない速度と精度の組み合わせで解く方法を開発した。
ダグラス・ラフフォード分割法に基づいて構築され、近似正規化問題を解く代わりに、元のOT問題に直接取り組んだ。
- 参考スコア（独自算出の注目度）: 19.6590956326761
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a fast and reliable method for solving large-scale optimal
transport (OT) problems at an unprecedented combination of speed and accuracy.
Built on the celebrated Douglas-Rachford splitting technique, our method
tackles the original OT problem directly instead of solving an approximate
regularized problem, as many state-of-the-art techniques do. This allows us to
provide sparse transport plans and avoid numerical issues of methods that use
entropic regularization. The algorithm has the same cost per iteration as the
popular Sinkhorn method, and each iteration can be executed efficiently, in
parallel. The proposed method enjoys an iteration complexity $O(1/\epsilon)$
compared to the best-known $O(1/\epsilon^2)$ of the Sinkhorn method. In
addition, we establish a linear convergence rate for our formulation of the OT
problem. We detail an efficient GPU implementation of the proposed method that
maintains a primal-dual stopping criterion at no extra cost. Substantial
experiments demonstrate the effectiveness of our method, both in terms of
computation times and robustness.
- Abstract（参考訳）: 我々は,高速かつ信頼性の高い大規模最適輸送(OT)問題を,前例のない速度と精度の組み合わせで解く方法を開発した。
ダグラス・ラフフォード分割法に基づいて構築され、多くの最先端技術と同様に、近似正規化問題を解く代わりに、元のOT問題に直接取り組む。
これにより、疎輸送計画を提供し、エントロピー正規化を利用する手法の数値問題を回避することができる。
アルゴリズムは、一般的なシンクホーン法と同じイテレーション毎のコストを持ち、各イテレーションを並列に効率的に実行できる。
提案手法は,Sinkhorn法において最もよく知られた$O(1/\epsilon^2)$と比較して,反復複雑性が$O(1/\epsilon)$である。
さらに,OT問題を定式化するための線形収束率を確立する。
本稿では,提案手法のGPUによる効率的な実装について述べる。
計算時間とロバスト性の観点から,本手法の有効性を実証する実験を行った。
関連論文リスト
- Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。
WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
論文 参考訳（メタデータ） (2024-10-28T04:47:39Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Bringing regularized optimal transport to lightspeed: a splitting method
adapted for GPUs [9.297785393486976]
正規化された最適輸送のための効率的なアルゴリズムを提案する。
従来の手法とは対照的に、ダグラス・ラフフォード分割法を用いて、幅広い正規化器を扱える効率的な解法を開発した。
論文 参考訳（メタデータ） (2023-05-29T12:04:55Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。