論文の概要: A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data

• arxiv url: http://arxiv.org/abs/2303.06595v1
• Date: Sun, 12 Mar 2023 07:23:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-14 17:54:30.322225
• Title: A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data
• Title（参考訳）: グラフデータにおけるGromov-Wasserstein緩和のための収束単ループアルゴリズム
• Authors: Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So and Jose Blanchet
• Abstract要約: 本稿では,Gromov-Wasserstein (GW) 距離の近似解を提供する単一ループアルゴリズムであるBregman Alternating Projected Gradient (BAPG) を提案する。 本稿では,カップリングマップの実現可能性においていくつかの妥協点があるにもかかわらず,精度と計算効率のバランスをとる新しい緩和手法を提案する。
• 参考スコア（独自算出の注目度）: 37.89640056739607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we present the Bregman Alternating Projected Gradient (BAPG) method, a single-loop algorithm that offers an approximate solution to the Gromov-Wasserstein (GW) distance. We introduce a novel relaxation technique that balances accuracy and computational efficiency, albeit with some compromises in the feasibility of the coupling map. Our analysis is based on the observation that the GW problem satisfies the Luo-Tseng error bound condition, which relates to estimating the distance of a point to the critical point set of the GW problem based on the optimality residual. This observation allows us to provide an approximation bound for the distance between the fixed-point set of BAPG and the critical point set of GW. Moreover, under a mild technical assumption, we can show that BAPG converges to its fixed point set. The effectiveness of BAPG has been validated through comprehensive numerical experiments in graph alignment and partition tasks, where it outperforms existing methods in terms of both solution quality and wall-clock time.
• Abstract（参考訳）: 本稿では,gromov-wasserstein (gw) 距離に対する近似解を提供する単一ループアルゴリズムであるbregman alternating projectioned gradient (bapg) 法を提案する。 本稿では,結合マップの実現可能性にいくつかの妥協はあるものの,精度と計算効率のバランスをとる新しい緩和手法を提案する。 本解析は,gw問題の最適性残差に基づいて,gw問題の臨界点集合と点の距離を推定するためのluo-tseng誤差境界条件を満たした観測に基づく。 この観測により,BAPG の固定点集合と GW の臨界点集合との間の距離を近似的に推定できる。 さらに、穏やかな技術的仮定の下では、BAPGがその固定点集合に収束することを示すことができる。 BAPGの有効性は、グラフアライメントやパーティションタスクにおける包括的な数値実験を通じて検証され、ソリューションの品質と壁面時間の両方において既存の手法よりも優れている。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problems [8.673558396669806]
  Plug-noise-and-Play (Play) 法は画像逆問題に対する効率的な反復アルゴリズムである。 2つ提案する。 Bregman Score gradient Denoise 逆問題に基づくアルゴリズム。
  論文  参考訳（メタデータ） (2023-06-06T07:36:47Z)
• Outlier-Robust Gromov-Wasserstein for Graph Data [31.895380224961464]
  我々は、Gromov-Wasserstein (GW) 距離のRGWと呼ばれる新しい頑健なバージョンを導入する。 RGWは、クルバック・リーバーの発散に基づくあいまいさ集合の中で楽観的に摂動する限界制約を特徴とする。 サブグラフマッチングや部分形状対応などの実世界のグラフ学習におけるRGWの有効性を示す。
  論文  参考訳（メタデータ） (2023-02-09T12:57:29Z)
• Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Learning [37.89640056739607]
  2つのアルゴリズム、Bregman Alternating Projected Gradient (BAPG) とハイブリッドBregman Proximal Gradient (hBPG) は(ほぼ)収束することが証明されている。 グラフアライメント,グラフ分割,形状マッチングなど,タスクのホスト上での手法の有効性を検証するための総合的な実験を行った。
  論文  参考訳（メタデータ） (2022-05-17T06:26:54Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。 我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
  論文  参考訳（メタデータ） (2021-12-24T17:21:04Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Projection Robust Wasserstein Barycenter [36.97843660480747]
  ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です 本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
  論文  参考訳（メタデータ） (2021-02-05T19:23:35Z)
• Continuous Regularized Wasserstein Barycenters [51.620781112674024]
  正規化ワッサーシュタイン・バリセンタ問題に対する新しい双対定式化を導入する。 我々は、強い双対性を確立し、対応する主対関係を用いて、正規化された輸送問題の双対ポテンシャルを用いて暗黙的にバリセンターをパラメトリゼーションする。
  論文  参考訳（メタデータ） (2020-08-28T08:28:06Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)

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

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