論文の概要: A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm

• arxiv url: http://arxiv.org/abs/2412.09235v1
• Date: Thu, 12 Dec 2024 12:45:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-13 13:31:28.025989
• Title: A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
• Title（参考訳）: エントロピックプランの安定性とシンクホーンアルゴリズムの指数収束に対する半共空アプローチ
• Authors: Alberto Chiarini, Giovanni Conforti, Giacomo Greco, Luca Tamanini,
• Abstract要約: エントロピック最適輸送の枠組みにおける非有界体の安定性とシンクホーンのアルゴリズムの収束性について検討する。 新しい用途には、部分空間の弾性コスト、弱対数対数辺縁、軽い尾を持つ辺縁などがある。
• 参考スコア（独自算出の注目度）: 3.7498611358320733
• License:
• Abstract: We study stability of optimizers and convergence of Sinkhorn's algorithm in the framework of entropic optimal transport. We show entropic stability for optimal plans in terms of the Wasserstein distance between their marginals under a semiconcavity assumption on the sum of the cost and one of the two entropic potentials. When employed in the analysis of Sinkhorn's algorithm, this result gives a natural sufficient condition for its exponential convergence, which does not require the ground cost to be bounded. By controlling from above the Hessians of Sinkhorn potentials in examples of interest, we obtain new exponential convergence results. For instance, for the first time we obtain exponential convergence for log-concave marginals and quadratic costs for all values of the regularization parameter. Moreover, the convergence rate has a linear dependence on the regularization: this behavior is sharp and had only been previously obtained for compact distributions arXiv:2407.01202. Other interesting new applications include subspace elastic costs [Cuturi et al. PMLR 202(2023)], weakly log-concave marginals, marginals with light tails, where, under reinforced assumptions, we manage to improve the rates obtained in arXiv:2311.04041, the case of unbounded Lipschitz costs, and compact Riemannian manifolds.
• Abstract（参考訳）: エントロピック最適輸送の枠組みにおける最適化器の安定性とシンクホーンアルゴリズムの収束性について検討する。 コストの和と2つのエントロピーポテンシャルの和に関する半共空仮定の下で、ワッサーシュタイン距離の観点から最適計画に対するエントロピー安定性を示す。 シンクホーンのアルゴリズムの分析に使用されると、この結果は指数収束の自然な条件を与える。 興味のある例としてシンクホーンポテンシャルのヘシアンの上から制御することにより、新しい指数収束結果が得られる。 例えば、正則化パラメータのすべての値に対する対数凹辺の指数収束と二次コストを初めて得る。 さらに収束速度は正則化に線形依存しており、この挙動は鋭く、以前はコンパクト分布 arXiv:2407.01202 に対してのみ得られていた。 その他の興味深い新しい応用としては、部分空間弾性コスト (Cuturi et al PMLR 202(2023)) 、弱対数対数の辺縁、軽い尾を持つ辺辺、強化された仮定の下では、arXiv:2311.04041 で得られる速度、非有界リプシッツコストの場合、コンパクトリーマン多様体などが挙げられる。

関連論文リスト

• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。 また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
  論文  参考訳（メタデータ） (2023-04-27T06:27:37Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps [20.661025590877774]
  半緩和シンクホーン(Semi-Relaxed Sinkhorn、SR-Sinkhorn)は、半緩和最適輸送(SROT)問題のアルゴリズムである。 本稿では,SR-シンクホーンの総合収束解析について述べる。
  論文  参考訳（メタデータ） (2022-05-27T09:19:05Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport [0.483420384410068]
  エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。 また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大させることも検討した。
  論文  参考訳（メタデータ） (2021-10-25T06:52:45Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm [0.0]
  エントロピー正則化は、元の最適輸送問題を一般化する。 Kullback-Leibler の発散を一般の$f$-divergence に置き換えると、自然な一般化につながる。 本稿では,正規化された最適輸送コストとその勾配を計算するための実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T16:37:31Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  大規模な非最適化問題は、現代の機械学習ではユビキタスである。 我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
  論文  参考訳（メタデータ） (2020-02-09T09:56:06Z)

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

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