論文の概要: Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm

• arxiv url: http://arxiv.org/abs/2105.14337v1
• Date: Sat, 29 May 2021 16:37:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-02 14:28:15.186825
• Title: Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm
• Title（参考訳）: f$-divergence regularizationと一般化シンクホーンアルゴリズムを用いた最適輸送
• Authors: D\'avid Terj\'ek (1) and Diego Gonz\'alez-S\'anchez (1) ((1) Alfr\'ed R\'enyi Institute of Mathematics)
• Abstract要約: エントロピー正則化は、元の最適輸送問題を一般化する。 Kullback-Leibler の発散を一般の$f$-divergence に置き換えると、自然な一般化につながる。 本稿では,正規化された最適輸送コストとその勾配を計算するための実用的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Entropic regularization provides a generalization of the original optimal transport problem. It introduces a penalty term defined by the Kullback-Leibler divergence, making the problem more tractable via the celebrated Sinkhorn algorithm. Replacing the Kullback-Leibler divergence with a general $f$-divergence leads to a natural generalization. Using convex analysis, we extend the theory developed so far to include $f$-divergences defined by functions of Legendre type, and prove that under some mild conditions, strong duality holds, optimums in both the primal and dual problems are attained, the generalization of the $c$-transform is well-defined, and we give sufficient conditions for the generalized Sinkhorn algorithm to converge to an optimal solution. We propose a practical algorithm for computing the regularized optimal transport cost and its gradient via the generalized Sinkhorn algorithm. Finally, we present experimental results on synthetic 2-dimensional data, demonstrating the effects of using different $f$-divergences for regularization, which influences convergence speed, numerical stability and sparsity of the optimal coupling.
• Abstract（参考訳）: エントロピー正則化は、元の最適輸送問題を一般化する。 Kullback-Leibler の発散によって定義されるペナルティ項を導入し、この問題をSinkhornアルゴリズムによってより魅力的にする。 Kullback-Leibler の発散を一般の$f$-divergence に置き換えると、自然な一般化につながる。 凸解析を用いて、ルジャンドル型の関数で定義される$f$-divergencesを含む理論を拡張し、いくつかの穏やかな条件下では、主問題と双対問題の両方における最適解が成立し、$c$-変換の一般化が適切に定義され、一般化されたシンクホーンアルゴリズムが最適解に収束する十分な条件を与える。 本稿では,一般化シンクホーンアルゴリズムを用いて,最適輸送コストとその勾配を計算するための実用的なアルゴリズムを提案する。 最後に, 最適結合の収束速度, 数値安定性, 疎結合性に影響を及ぼす正則化に異なる$f$-divergencesを用いることで, 合成2次元データに対する実験結果を示す。

関連論文リスト

• Independently-Normalized SGD for Generalized-Smooth Nonconvex Optimization [19.000530691874516]
  我々は、多くの非機械学習問題が従来の非スムーズな非スムーズな状態を超えるような条件を満たすことを示した。 独立サンプリングと正規化を利用する独立正規化勾配降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-17T21:52:00Z)
• A Sinkhorn-type Algorithm for Constrained Optimal Transport [14.935188572016635]
  この研究は、等式制約と不等式制約を組み合わせた一般的なOT問題に焦点をあてる。 対応するエントロピー正規化の定式化を導出し、理論的保証によって支持される制約付きOT問題に対してシンクホーン型アルゴリズムを導入する。 全体として、この研究は、エントロピー最適輸送の最近の理論的および数値的な進歩と制約されたケースを体系的に組み合わせ、実践者は複雑なシナリオにおいて近似的な輸送計画を引き出すことができる。
  論文  参考訳（メタデータ） (2024-03-08T05:01:43Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。 低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
  論文  参考訳（メタデータ） (2021-10-26T15:02:27Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。 決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。 我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
  論文  参考訳（メタデータ） (2021-09-20T21:48:19Z)
• 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)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  大規模な非最適化問題は、現代の機械学習ではユビキタスである。 我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
  論文  参考訳（メタデータ） (2020-02-09T09:56:06Z)

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

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