論文の概要: Wasserstein Mirror Gradient Flow as the limit of the Sinkhorn Algorithm
- arxiv url: http://arxiv.org/abs/2307.16421v1
- Date: Mon, 31 Jul 2023 06:11:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-01 15:37:41.627199
- Title: Wasserstein Mirror Gradient Flow as the limit of the Sinkhorn Algorithm
- Title（参考訳）: シンクホーンアルゴリズムの限界としてのwassersteinミラー勾配流
- Authors: Nabarun Deb, Young-Heon Kim, Soumik Pal, and Geoffrey Schiebinger
- Abstract要約: シンクホーンアルゴリズムの反復から得られる限界の列が、ワッサーシュタイン空間上の絶対連続曲線に収束することを証明する。
この極限はシンクホーンフローと呼ばれ、ワッサーシュタインミラー勾配流の例である。
- 参考スコア（独自算出の注目度）: 0.15749416770494706
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that the sequence of marginals obtained from the iterations of the
Sinkhorn algorithm or the iterative proportional fitting procedure (IPFP) on
joint densities, converges to an absolutely continuous curve on the
$2$-Wasserstein space, as the regularization parameter $\varepsilon$ goes to
zero and the number of iterations is scaled as $1/\varepsilon$ (and other
technical assumptions). This limit, which we call the Sinkhorn flow, is an
example of a Wasserstein mirror gradient flow, a concept we introduce here
inspired by the well-known Euclidean mirror gradient flows. In the case of
Sinkhorn, the gradient is that of the relative entropy functional with respect
to one of the marginals and the mirror is half of the squared Wasserstein
distance functional from the other marginal. Interestingly, the norm of the
velocity field of this flow can be interpreted as the metric derivative with
respect to the linearized optimal transport (LOT) distance. An equivalent
description of this flow is provided by the parabolic Monge-Amp\`{e}re PDE
whose connection to the Sinkhorn algorithm was noticed by Berman (2020). We
derive conditions for exponential convergence for this limiting flow. We also
construct a Mckean-Vlasov diffusion whose marginal distributions follow the
Sinkhorn flow.
- Abstract（参考訳）: 我々は、シンクホーンアルゴリズムの反復あるいは関節密度に対する反復比例フィッティング手順(IPFP)から得られる限界の列が、正規化パラメータ $\varepsilon$ が 0 に収束し、反復の数が 1/\varepsilon$ (およびその他の技術的仮定) にスケールされるので、2$-ワッサーシュタイン空間上の絶対連続曲線に収束することを示した。
この限界は、我々がシンクホーン流と呼ぶもので、ワッサースタインミラー勾配流の一例であり、よく知られているユークリッドミラー勾配流に触発された概念である。
シンクホーンの場合、勾配は一方の辺点に関して相対エントロピー汎関数の勾配であり、鏡はもう一方の辺点から2乗ワッサースタイン距離汎関数の半分である。
興味深いことに、この流れの速度場のノルムは、線形化された最適輸送(LOT)距離に関する計量微分として解釈できる。
この流れの等価な記述は、Sinkhornアルゴリズムへの接続が Berman (2020) によって発見された放物型 Monge-Amp\`{e}re PDE によって提供される。
この制限流に対する指数収束条件を導出する。
また、シンクホーン流に沿う境界分布を持つMckean-Vlasov拡散も構成する。
関連論文リスト
- Iterated Schrödinger bridge approximation to Wasserstein Gradient Flows [1.5561923713703105]
我々は、同じ辺を持つシュリンガー橋を連続的に計算するワッサーシュタイン勾配流の新しい離散化スキームを導入する。
提案手法には2つの利点がある: 1つはスコア関数の使用を回避し、もう1つはシンクホーンアルゴリズムを用いて粒子ベースの近似を行うことができる。
論文 参考訳（メタデータ） (2024-06-16T07:23:26Z) - A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。
i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。
その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
論文 参考訳（メタデータ） (2024-04-18T16:46:08Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach [10.568851068989972]
本稿では,アルゴリズムの効率的な解法を実現するために,元のOT問題であるエントロピックOT問題の緩和に焦点をあてる。
この定式化はSchr"odinger Bridge問題としても知られ、特に最適制御(SOC)と結びつき、人気のあるシンクホーンアルゴリズムで解くことができる。
論文 参考訳（メタデータ） (2023-04-13T13:58:25Z) - Mirror Descent with Relative Smoothness in Measure Spaces, with
application to Sinkhorn and EM [11.007661197604065]
本稿では,無限次元環境下でのミラー降下アルゴリズムの収束性について検討する。
結果が結合分布とクルバック-リーブラー分岐に適用され、シンクホーンの最適輸送に対する原始的な反復がミラー降下に対応することを示す。
論文 参考訳（メタデータ） (2022-06-17T16:19:47Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Fast Margin Maximization via Dual Acceleration [52.62944011696364]
指数関数的尾の損失を持つ線形分類器を訓練するための運動量に基づく手法を提案し,解析する。
この運動量に基づく法は、最大マルジン問題の凸双対、特にこの双対にネステロフ加速度を適用することによって導出される。
論文 参考訳（メタデータ） (2021-07-01T16:36:39Z) - On the Convergence of Gradient Descent in GANs: MMD GAN As a Gradient
Flow [26.725412498545385]
パラメトリックカーネル化勾配流は、勾配正規化$mathrmMMD$GANにおけるmin-maxゲームに類似していることを示す。
次に、正規化$mathrmMMD$GANにおける生成元の空間上の勾配降下が、対象分布に大域的に収束することを保証する明示的な条件を導出する。
論文 参考訳（メタデータ） (2020-11-04T16:55:00Z) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳（メタデータ） (2020-07-22T18:18:28Z) - Debiased Sinkhorn barycenters [110.79706180350507]
最適輸送(OT)におけるエントロピー正則化(Entropy regularization)は、機械学習におけるWassersteinメトリクスやバリセンタに対する近年の関心の原動力となっている。
このバイアスがエントロピー正則化器を定義する基準測度とどのように密接に関連しているかを示す。
両世界の長所を保ち、エントロピーを滑らかにしないシンクホーン様の高速な反復をデバイアスド・ワッサースタインのバリセンタとして提案する。
論文 参考訳（メタデータ） (2020-06-03T23:06:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。