論文の概要: Accelerated Sinkhorn Algorithms for Partial Optimal Transport

• arxiv url: http://arxiv.org/abs/2601.17196v1
• Date: Fri, 23 Jan 2026 21:55:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:07.411744
• Title: Accelerated Sinkhorn Algorithms for Partial Optimal Transport
• Title（参考訳）: 部分最適輸送のための加速シンクホーンアルゴリズム
• Authors: Nghia Thu Truong, Qui Phu Pham, Quang Nguyen, Dung Luong, Mai Tran,
• Abstract要約: 我々は,POT設定においてNesterovスタイルの加速度と交互に最小化を統合するASPOT(Accelerated Sinkhorn for POT)を導入する。 エントロピーパラメータを$$で選択することで、古典的なシンクホーン法の精度が向上することを示す。
• 参考スコア（独自算出の注目度）: 1.6528632644902823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Partial Optimal Transport (POT) addresses the problem of transporting only a fraction of the total mass between two distributions, making it suitable when marginals have unequal size or contain outliers. While Sinkhorn-based methods are widely used, their complexity bounds for POT remain suboptimal and can limit scalability. We introduce Accelerated Sinkhorn for POT (ASPOT), which integrates alternating minimization with Nesterov-style acceleration in the POT setting, yielding a complexity of $\mathcal{O}(n^{7/3}\varepsilon^{-5/3})$. We also show that an informed choice of the entropic parameter $γ$ improves rates for the classical Sinkhorn method. Experiments on real-world applications validate our theories and demonstrate the favorable performance of our proposed methods.
• Abstract（参考訳）: 部分最適輸送 (Partial Optimal Transport, POT) は、2つの分布間の総質量のごく一部しか輸送しない問題に対処する。 Sinkhornベースの手法は広く使われているが、POTの複雑性境界は最適以下であり、スケーラビリティを制限できる。 我々は POT (ASPOT) に対して Accelerated Sinkhorn を導入し、これは POT 設定において Nesterov スタイルの加速度と交互に最小化を統合することで、$\mathcal{O}(n^{7/3}\varepsilon^{-5/3})$ の複雑さをもたらす。 また、エントロピーパラメータ$γ$の情報選択により、古典的なシンクホーン法の速度が向上することを示す。 実世界の応用実験は、我々の理論を検証し、提案手法の良好な性能を実証する。

関連論文リスト

• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods [17.14725907264431]
  本稿では,少なくとも$n$の支持を持つ2つの不均衡測度間の部分最適輸送(POT)問題について検討する。 我々はPOTの新しいラウンドリングアルゴリズムを提案し、次に、$mathcalwidetilde O(n2/varepsilon4)$の複雑さを補正した実行可能なシンクホーン手順を提供する。
  論文  参考訳（メタデータ） (2023-12-21T15:56:09Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [13.848861021326755]
  離散最適輸送(OT)問題を高精度に解くための新しい手法として,ミラーDescent Optimal Transport (MDOT)を提案する。 我々は,GPU並列非線形共役アルゴリズム(PNCG)を用いて,従来のシンクホーンの繰り返しを弱い正規化の下で効率よく解く。
  論文  参考訳（メタデータ） (2023-07-17T14:09:43Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。 まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。 我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
  論文  参考訳（メタデータ） (2021-08-18T06:46:59Z)

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

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