論文の概要: Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
- arxiv url: http://arxiv.org/abs/2609.31848v2
- Date: Tue, 29 Sep 2026 17:53:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-30 21:28:46.562119
- Title: Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
- Title（参考訳）: 平均ミラーディフレッシュ法とデュアルグラディエント法:エントロピックグロモフ・ワッサーシュタイン問題に対する収束アルゴリズム
- Abstract要約: Averaged Mirror Descent (AMD) を導入し, 連続MDステップを平均化し, その収束性を任意のコストで証明する。
また、固定ステップサイズの双対勾配法は、より複雑な反復のコストで任意のコストに対して収束することも確認した。
- 参考スコア（独自算出の注目度）: 1.0705399532413615
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.
- Abstract（参考訳）: グロモフ・ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、計量測度(mm)空間間の差を測り、その内在的構造のみに基づいてそれらの間の最適アライメントを特定する。
同型mm空間を識別するので、同型表現を許容するヘテロジニアスデータセットに対して、自然な距離の概念を提供する。
GW距離の計算を高速化するために、多くの実践者はエントロピー正規化を用いてエントロピーGW(EGW)問題を得る。
最も一般的なEGWソルバはミラー・ダイアンス (MD) アルゴリズムであり、これはEGW計算をエントロピー最適輸送 (EOT) 問題を各イテレーションで解く反復プロセスに還元する。
広く使われているにもかかわらず、この問題に対するMDの収束は、制限されたコストのクラスに対してのみ確立されている。
一方、最近提案された双対勾配法は一般的なコストで利用可能であるが、正規化パラメータに依存するステップサイズを選択する必要がある。
これら2つの問題に対処するために、連続MDステップを平均化し、任意のコストで収束するAveraged Mirror Descent (AMD)を導入する。
そして、固定ステップサイズの双対勾配法は、より複雑な反復のコストで任意のコストに対して収束することを示す。
どちらの場合も、実際には不可能な不正確なイテレーションも説明します。
我々はこれらの手法の実証的な性能を様々な設定で比較し、特にAMDと双対勾配法は古典的MDが失敗する例に収束することを示した。
関連論文リスト
- Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing [15.240268958496172]
グロモフ・ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、その内在的構造のみに基づいて測度(mm)空間を整列する原理的な枠組みを提供する。
近年,2乗ユークリッド分布と内積コストとのGW距離の双対形式が導出された。
この研究は、エントロピー正則化と非非負のGW距離に対する新しい双対性結果を与える。
本稿では,正規化GW問題に対する正規化保証の対象となる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-02T19:08:50Z) - Variational Entropic Optimal Transport [67.76725267984578]
本稿では,ドメイン翻訳問題に対する変分エントロピー最適輸送(VarEOT)を提案する。
VarEOTは、補助正の正規化子上のトラクタブルな一般化として、log-partition $log mathbbE[exp(cdot)$の正確な変分再構成に基づいている。
合成データと画像と画像の変換に関する実験は、競争力のあるか、あるいはより良い翻訳品質を示す。
論文 参考訳（メタデータ） (2026-02-02T15:48:44Z) - Interpolation-based coordinate descent method for parameterized quantum circuits [11.745089977547558]
量子回路(PQC)におけるパラメータ最適化問題に対処する座標降下法(ICD)を提案する。
ICDはPQCコスト関数を近似し、その基礎となる三角構造を効果的に復元し、各イテレーションで単一のパラメータに対してargmin更新を実行する。
構造最適化に関する従来の研究とは対照的に、量子計測から統計的誤差を緩和する最適なノードを決定する。
論文 参考訳（メタデータ） (2025-03-06T17:06:47Z) - Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [13.848861021326755]
離散最適輸送(OT)問題を高精度に解くための新しい手法として,ミラーDescent Optimal Transport (MDOT)を提案する。
我々は,GPU並列非線形共役アルゴリズム(PNCG)を用いて,従来のシンクホーンの繰り返しを弱い正規化の下で効率よく解く。
論文 参考訳（メタデータ） (2023-07-17T14:09:43Z) - Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。
フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
論文 参考訳（メタデータ） (2023-01-10T01:58:15Z) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。
我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。
AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文 参考訳（メタデータ） (2020-02-05T03:09:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。