論文の概要: Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach
- arxiv url: http://arxiv.org/abs/2304.06549v2
- Date: Mon, 26 Jun 2023 18:18:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-28 17:05:42.415551
- Title: Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach
- Title(参考訳): シンクホーン反復とその勾配に対する非漸近収束境界:結合的アプローチ
- Authors: Giacomo Greco, Maxence Noble, Giovanni Conforti, Alain Durmus
- Abstract要約: 本稿では,アルゴリズムの効率的な解法を実現するために,元のOT問題であるエントロピックOT問題の緩和に焦点をあてる。
この定式化はSchr"odinger Bridge問題としても知られ、特に最適制御(SOC)と結びつき、人気のあるシンクホーンアルゴリズムで解くことができる。
- 参考スコア(独自算出の注目度): 10.568851068989972
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computational optimal transport (OT) has recently emerged as a powerful
framework with applications in various fields. In this paper we focus on a
relaxation of the original OT problem, the entropic OT problem, which allows to
implement efficient and practical algorithmic solutions, even in high
dimensional settings. This formulation, also known as the Schr\"odinger Bridge
problem, notably connects with Stochastic Optimal Control (SOC) and can be
solved with the popular Sinkhorn algorithm. In the case of discrete-state
spaces, this algorithm is known to have exponential convergence; however,
achieving a similar rate of convergence in a more general setting is still an
active area of research. In this work, we analyze the convergence of the
Sinkhorn algorithm for probability measures defined on the $d$-dimensional
torus $\mathbb{T}_L^d$, that admit densities with respect to the Haar measure
of $\mathbb{T}_L^d$. In particular, we prove pointwise exponential convergence
of Sinkhorn iterates and their gradient. Our proof relies on the connection
between these iterates and the evolution along the Hamilton-Jacobi-Bellman
equations of value functions obtained from SOC-problems. Our approach is novel
in that it is purely probabilistic and relies on coupling by reflection
techniques for controlled diffusions on the torus.
- Abstract(参考訳): 計算最適輸送(OT)は、近年、様々な分野で応用される強力なフレームワークとして登場した。
本稿では,従来のOT問題であるエントロピックOT問題の緩和に焦点をあて,高次元設定においても効率的で実用的なアルゴリズム解を実現できる。
この定式化はSchr\"odinger Bridge problemとしても知られ、特にSOC(Stochastic Optimal Control)と接続し、人気のあるシンクホーンアルゴリズムで解くことができる。
離散状態空間の場合、このアルゴリズムは指数収束を持つことが知られているが、より一般的な環境でも同様の収束率を達成することは研究の活発な領域である。
本研究では,$d$次元トーラス$\mathbb{t}_l^d$ 上で定義される確率測度に対するシンクホーンアルゴリズムの収束を解析し,その密度を$\mathbb{t}_l^d$ のハール測度に対して認める。
特に、シンクホーンイテレートとその勾配の点方向の指数収束性を証明する。
我々の証明は、これらの反復と、SOC-プロブレムから得られる値関数のハミルトン・ヤコビ・ベルマン方程式の進化の間の関係に依存する。
我々のアプローチは、純粋に確率的であり、トーラス上の制御拡散に対する反射法による結合に依存している。
関連論文リスト
- Convergence of Some Convex Message Passing Algorithms to a Fixed Point [0.0]
グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。
より強い結果(これは以前予想されたが、決して証明されなかった)を証明します。
本研究の主な結果とは対照的に,制約付き最適化問題に適用された座標降下の類似バージョンは収束しないことを示す。
論文 参考訳(メタデータ) (2024-03-07T13:14:21Z) - Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。
SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
論文 参考訳(メタデータ) (2024-01-20T21:23:09Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - Proximal denoiser for convergent plug-and-play optimization with
nonconvex regularization [7.0226402509856225]
Plug-and-Play ()メソッドは、ニューラルネットワーク演算子をデノナイジング演算子に置き換えることで、アルゴリズムによって、近位姿勢の逆問題を解決する。
このデノイザが実際に勾配関数に対応していることが示される。
論文 参考訳(メタデータ) (2022-01-31T14:05:20Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳(メタデータ) (2020-06-06T19:08:05Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳(メタデータ) (2020-05-15T21:14:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。