Fugu-MT 論文翻訳(概要): Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

論文の概要: Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

arxiv url: http://arxiv.org/abs/2110.12678v1
Date: Mon, 25 Oct 2021 06:52:45 GMT
ステータス: 処理完了
システム内更新日: 2021-10-26 17:39:55.552006
Title: Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport
Title（参考訳）: 半離散エントロピー最適輸送のための近位収束境界
Authors: Alex Delalande (LMO, DATASHAPE)
Abstract要約: エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大させることも検討した。
参考スコア（独自算出の注目度）: 0.483420384410068
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. These bounds quantify the stability of the dual solutions of the regularized problem (sometimes called Sinkhorn potentials) w.r.t. the regularization parameter, for which we ensure a better than Lipschitz dependence. Such facts may be a first step towards a mathematical justification of annealing or $\eps$-scaling heuristics for the numerical resolution of regularized semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.
Abstract（参考訳）: エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。これらの境界は正規化問題(シンクホーンポテンシャルと呼ばれることもある)の双対解の安定性を、正規化パラメータ w.r.t で定量化する。このような事実は、正規化された半離散的最適輸送の数値解法に対するアニーリングの数学的正当化や$\eps$-scalingのヒューリスティックスへの第一歩かもしれない。また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大することを示した。

関連論文リスト

A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm [3.7498611358320733]
エントロピック最適輸送の枠組みにおける非有界体の安定性とシンクホーンのアルゴリズムの収束性について検討する。新しい用途には、部分空間の弾性コスト、弱対数対数辺縁、軽い尾を持つ辺縁などがある。
論文参考訳（メタデータ） (2024-12-12T12:45:31Z)
Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文参考訳（メタデータ） (2023-06-29T01:20:44Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Convergence Rates for Regularized Optimal Transport via Quantization [3.04585143845864]
正規化パラメータが消滅するにつれて, 分散正則化最適輸送の収束について検討する。量子化とマーチンゲール結合を用いた新しい手法は、非コンパクトなマーチンゲールに適している。
論文参考訳（メタデータ） (2022-08-30T16:58:40Z)
An improved central limit theorem and fast convergence rates for entropic transportation costs [13.9170193921377]
亜ガウス確率測度間のエントロピー輸送コストに対する中心極限定理を証明した。これらの結果を,実証的尺度間の期待エントロピー輸送コストに対する,新しい,より高速な,収束率で補完する。
論文参考訳（メタデータ） (2022-04-19T19:26:59Z)
Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文参考訳（メタデータ） (2021-10-20T02:57:21Z)
A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization [7.483040617090451]
本研究では,ソフトマックスパラメータ化の下で,エントロピー規則化制約付きマルコフ決定過程(CMDP)について検討する。我々の理論的解析は、ラグランジアン双対函数は滑らかであり、ラグランジアン双対性ギャップは原始性ギャップと制約違反に分解できることを示している。
論文参考訳（メタデータ） (2021-10-17T21:26:40Z)
Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。この理論を2つの画像のマッチング問題に適用する。
論文参考訳（メタデータ） (2021-07-13T12:31:06Z)
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文参考訳（メタデータ） (2021-06-30T18:32:46Z)
Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution [8.465228064780748]
2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
論文参考訳（メタデータ） (2021-03-10T18:53:59Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)

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