論文の概要: Sinkhorn Algorithm for Sequentially Composed Optimal Transports
- arxiv url: http://arxiv.org/abs/2412.03120v2
- Date: Thu, 05 Dec 2024 03:06:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-06 11:19:21.356477
- Title: Sinkhorn Algorithm for Sequentially Composed Optimal Transports
- Title（参考訳）: Sinkhorn Algorithm for Sequentially Composed Optimal Transports (特集:情報ネットワーク)
- Authors: Kazuki Watanabe, Noboru Isobe,
- Abstract要約: Sinkhornアルゴリズムは最適な輸送のためのデファクト標準近似アルゴリズムである。
本稿では,効率的な近似アルゴリズム,すなわち,逐次的に合成された最適輸送のためのシンクホーンアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Sinkhorn algorithm is the de-facto standard approximation algorithm for optimal transport, which has been applied to a variety of applications, including image processing and natural language processing. In theory, the proof of its convergence follows from the convergence of the Sinkhorn--Knopp algorithm for the matrix scaling problem, and Altschuler et al. show that its worst-case time complexity is in near-linear time. Very recently, sequentially composed optimal transports were proposed by Watanabe and Isobe as a hierarchical extension of optimal transports. In this paper, we present an efficient approximation algorithm, namely Sinkhorn algorithm for sequentially composed optimal transports, for its entropic regularization. Furthermore, we present a theoretical analysis of the Sinkhorn algorithm, namely (i) its exponential convergence to the optimal solution with respect to the Hilbert pseudometric, and (ii) a worst-case complexity analysis for the case of one sequential composition.
- Abstract（参考訳）: Sinkhornアルゴリズムは最適な輸送のためのデファクト標準近似アルゴリズムであり、画像処理や自然言語処理など様々な用途に応用されている。
理論上、その収束の証明は、行列スケーリング問題に対するシンクホーン-ノックアルゴリズムの収束によるものであり、Altschulerらは、その最悪の時間複雑性がほぼ直線時間であることを示した。
最近では, 渡辺, 石部によって, 最適輸送の階層的拡張として, 逐次的に合成された最適輸送が提案されている。
本稿では, エントロピー正則化のための効率的な近似アルゴリズム, Sinkhorn アルゴリズムを提案する。
さらに,Sinkhornアルゴリズムの理論的解析,すなわちSinkhornアルゴリズムについて述べる。
(i)ヒルベルト擬測度に関する最適解に対する指数収束、及び
(II)1つの連続合成の場合の最悪のケース複雑性解析。
関連論文リスト
- A Sinkhorn-type Algorithm for Constrained Optimal Transport [14.935188572016635]
この研究は、等式制約と不等式制約を組み合わせた一般的なOT問題に焦点をあてる。
対応するエントロピー正規化の定式化を導出し、理論的保証によって支持される制約付きOT問題に対してシンクホーン型アルゴリズムを導入する。
全体として、この研究は、エントロピー最適輸送の最近の理論的および数値的な進歩と制約されたケースを体系的に組み合わせ、実践者は複雑なシナリオにおいて近似的な輸送計画を引き出すことができる。
論文 参考訳（メタデータ） (2024-03-08T05:01:43Z) - Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。
SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
論文 参考訳（メタデータ） (2024-01-20T21:23:09Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Efficient and Accurate Optimal Transport with Mirror Descent and
Conjugate Gradients [15.128885770407132]
本研究では, エントロピー的最適輸送, ミラー降下, 共役勾配の文献から, 最適輸送のための新しいアルゴリズムを設計する。
我々のスケーラブルでGPU並列化可能なアルゴリズムは、ワッサースタイン距離を極端精度で計算することができ、数値安定性の問題なく相対誤差レート10～8ドルに達することができる。
論文 参考訳（メタデータ） (2023-07-17T14:09:43Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Optimal transport with $f$-divergence regularization and generalized
Sinkhorn algorithm [0.0]
エントロピー正則化は、元の最適輸送問題を一般化する。
Kullback-Leibler の発散を一般の$f$-divergence に置き換えると、自然な一般化につながる。
本稿では,正規化された最適輸送コストとその勾配を計算するための実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-29T16:37:31Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。