論文の概要: Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach
- arxiv url: http://arxiv.org/abs/2304.06549v1
- Date: Thu, 13 Apr 2023 13:58:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-14 14:17:33.241765
- 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-プロブレムから得られる値関数のハミルトン・ヤコビ・ベルマン方程式の進化の間の関係に依存する。
我々のアプローチは、純粋に確率的であり、トーラス上の制御拡散に対する反射法による結合に依存している。
関連論文リスト
- 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) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳（メタデータ） (2020-12-07T19:14:49Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (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) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳（メタデータ） (2020-04-08T03:59:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。