論文の概要: Efficient Optimal Transport Algorithm by Accelerated Gradient descent

• arxiv url: http://arxiv.org/abs/2104.05802v1
• Date: Mon, 12 Apr 2021 20:23:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-15 03:49:34.560061
• Title: Efficient Optimal Transport Algorithm by Accelerated Gradient descent
• Title（参考訳）: 加速勾配降下による効率的な最適輸送アルゴリズム
• Authors: Dongsheng An, Na Lei and Xianfeng Gu
• Abstract要約: 本稿では,ネステロフの平滑化手法に基づく効率と精度をさらに向上させる新しいアルゴリズムを提案する。 提案手法は,同じパラメータでより高速な収束と精度を実現する。
• 参考スコア（独自算出の注目度）: 20.614477547939845
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport (OT) plays an essential role in various areas like machine learning and deep learning. However, computing discrete optimal transport plan for large scale problems with adequate accuracy and efficiency is still highly challenging. Recently, methods based on the Sinkhorn algorithm add an entropy regularizer to the prime problem and get a trade off between efficiency and accuracy. In this paper, we propose a novel algorithm to further improve the efficiency and accuracy based on Nesterov's smoothing technique. Basically, the non-smooth c-transform of the Kantorovich potential is approximated by the smooth Log-Sum-Exp function, which finally smooths the original non-smooth Kantorovich dual functional (energy). The smooth Kantorovich functional can be optimized by the fast proximal gradient algorithm (FISTA) efficiently. Theoretically, the computational complexity of the proposed method is given by $O(n^{\frac{5}{2}} \sqrt{\log n} /\epsilon)$, which is lower than that of the Sinkhorn algorithm. Empirically, compared with the Sinkhorn algorithm, our experimental results demonstrate that the proposed method achieves faster convergence and better accuracy with the same parameter.
• Abstract（参考訳）: 機械学習やディープラーニングなど、さまざまな分野において、最適な輸送(OT)が重要な役割を果たす。 しかし,大規模問題に対する離散的最適輸送計画の精度と効率性は依然として極めて困難である。 近年、シンクホーンアルゴリズムに基づく手法では、素問題にエントロピー正則化器を追加し、効率と精度のトレードオフを得る。 本論文では,ネステロフの平滑化技術に基づく効率と精度の向上を目的とした新しいアルゴリズムを提案する。 基本的に、カントロヴィチポテンシャルの非スムート c-変換は滑らかなlog-sum-exp関数によって近似され、最終的に元のスムートでないカントロヴィチ双対汎関数(エネルギー)を滑らかにする。 スムーズなカントロビッチ関数は高速近位勾配アルゴリズム(FISTA)によって効率的に最適化できる。 理論的には、提案手法の計算複雑性は、シンクホーンアルゴリズムよりも低い$O(n^{\frac{5}{2}} \sqrt{\log n} /\epsilon)$で与えられる。 実験により,Sinkhornアルゴリズムと比較して,提案手法がより高速に収束し,同じパラメータで精度が向上することを示した。

関連論文リスト

• PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport [12.551419304993209]
  本稿では,Sparse Newton法とSinkhorn法を用いて,大規模OT問題の高精度解を効率的に計算する手法を提案する。 全体空間と大域収束による計算複雑性の低減は厳密な理論解析によって保証される。 提案手法は,正確解に匹敵する精度を達成し,各イテレーションを段階的に高速化し,正規化パラメータに対する感度を低減し,ロバスト性を向上する。
  論文  参考訳（メタデータ） (2025-02-06T03:21:48Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
  2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。 本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
  論文  参考訳（メタデータ） (2023-09-04T19:47:04Z)
• Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [15.128885770407132]
  本研究では, エントロピー的最適輸送, ミラー降下, 共役勾配の文献から, 最適輸送のための新しいアルゴリズムを設計する。 我々のスケーラブルでGPU並列化可能なアルゴリズムは、ワッサースタイン距離を極端精度で計算することができ、数値安定性の問題なく相対誤差レート10～8ドルに達することができる。
  論文  参考訳（メタデータ） (2023-07-17T14:09:43Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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