論文の概要: Generalized Sobolev Transport for Probability Measures on a Graph

• arxiv url: http://arxiv.org/abs/2402.04516v1
• Date: Wed, 7 Feb 2024 01:49:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-08 17:04:51.339360
• Title: Generalized Sobolev Transport for Probability Measures on a Graph
• Title（参考訳）: グラフ上の確率測度に対する一般化ソボレフ輸送
• Authors: Tam Le, Truyen Nguyen, Kenji Fukumizu
• Abstract要約: グラフ距離空間上での測度に対する最適輸送(OT)問題について検討する。 我々は、Orlicz構造に対する特定の凸関数のクラスを活用し、一般化されたソボレフ輸送(GST)を提案する。 我々は GST が Orlicz-Wasserstein (OW) よりも数次高速であることを示す。
• 参考スコア（独自算出の注目度）: 29.950797721275574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the optimal transport (OT) problem for measures supported on a graph metric space. Recently, Le et al. (2022) leverage the graph structure and propose a variant of OT, namely Sobolev transport (ST), which yields a closed-form expression for a fast computation. However, ST is essentially coupled with the $L^p$ geometric structure within its definition which makes it nontrivial to utilize ST for other prior structures. In contrast, the classic OT has the flexibility to adapt to various geometric structures by modifying the underlying cost function. An important instance is the Orlicz-Wasserstein (OW) which moves beyond the $L^p$ structure by leveraging the \emph{Orlicz geometric structure}. Comparing to the usage of standard $p$-order Wasserstein, OW remarkably helps to advance certain machine learning approaches. Nevertheless, OW brings up a new challenge on its computation due to its two-level optimization formulation. In this work, we leverage a specific class of convex functions for Orlicz structure to propose the generalized Sobolev transport (GST). GST encompasses the ST as its special case, and can be utilized for prior structures beyond the $L^p$ geometry. In connection with the OW, we show that one only needs to simply solve a univariate optimization problem to compute the GST, unlike the complex two-level optimization problem in OW. We empirically illustrate that GST is several-order faster than the OW. Moreover, we provide preliminary evidences on the advantages of GST for document classification and for several tasks in topological data analysis.
• Abstract（参考訳）: グラフ計量空間上で支援される測度に対する最適輸送(ot)問題について検討する。 最近、Le et al. (2022) はグラフ構造を利用し、高速な計算のために閉形式表現を生成する OT の変種、すなわち Sobolev transport (ST) を提案する。 しかし、ST は定義の中で $L^p$ の幾何構造と結合しているため、他の先行構造に対して ST を利用するのは自明ではない。 対照的に古典的なOTは、基礎となるコスト関数を変更して様々な幾何学構造に適応する柔軟性を持っている。 重要な例はOrlicz-Wasserstein (OW) であり、これは \emph{Orlicz 幾何構造を利用して$L^p$構造を超えて動く。 標準的な$p$-order wassersteinの使用と比較すると、owは特定の機械学習アプローチを進めるのに非常に役立ちます。 それでもOWは、2レベル最適化の定式化により、計算に新たな課題を提起している。 本研究では,Orlicz構造に対する特定の凸関数のクラスを利用して,一般化ソボレフ輸送(GST)を提案する。 GSTはSTを特別な場合として包含し、$L^p$幾何を超える事前構造に利用できる。 OW に関して、OW の複雑な二段階最適化問題とは異なり、GST を計算するには単変量最適化問題を単に解くだけでよいことを示す。 GSTはOWよりも数桁高速であることを示す。 さらに,文書分類におけるGSTの利点とトポロジカルデータ解析におけるいくつかの課題について,予備的な証拠を提供する。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  最適輸送理論はそのような写像を構築するための原則化された枠組みを提供する。 本稿では,Wasserstein-1に基づく新しい最適輸送解法を提案する。 実験により,提案した解法は,2次元データセット上に一意かつ単調な写像を求める際に,$W$ OTソルバを模倣できることを示した。
  論文  参考訳（メタデータ） (2024-11-01T14:23:19Z)
• Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
  GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。 GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。 これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
  論文  参考訳（メタデータ） (2024-07-11T09:37:21Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  本稿では,SGDの軌道に局在する新しい被覆手法を提案する。 このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。 これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
  論文  参考訳（メタデータ） (2022-09-19T12:11:07Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Kantorovich Strikes Back! Wasserstein GANs are not Optimal Transport? [138.1080446991979]
  Wasserstein Generative Adversarial Networks (WGANs) は、最適輸送(OT)理論とカントロビッチ双対性に基づく一般的な生成モデルである。 WGANの成功にもかかわらず、基礎となるOT双対解器が、発生器の更新に必要なOTコスト(Wasserstein-1 距離、$mathbbW_1$)とOT勾配をどの程度よく近似するかは、まだ不明である。 我々は1-Lipschitz関数を構築し、それらを光モノトン輸送計画の構築に用いる。この戦略は、解析的に知られたOT計画、OTコスト、OTと連続ベンチマーク分布のペアを生成する。
  論文  参考訳（メタデータ） (2022-06-15T19:07:46Z)
• On the complexity of the optimal transport problem with graph-structured cost [9.24979291231758]
  マルチマージ最適輸送(Multi-marginal optimal transport、MOT)は、複数の辺縁への最適輸送の一般化である。 MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。
  論文  参考訳（メタデータ） (2021-10-01T19:29:59Z)
• Efficient and Stable Graph Scattering Transforms via Pruning [86.76336979318681]
  グラフ散乱変換(GST)は、グラフデータから特徴を抽出する訓練のないディープGCNモデルを提供する。 GSTが支払う価格は、層の数によって増加する空間と時間の指数関数的な複雑さである。 本研究は, GST の複雑性の限界に対処し, 効率的な (p) GST アプローチを導入する。
  論文  参考訳（メタデータ） (2020-01-27T16:05:56Z)

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

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