論文の概要: An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph

• arxiv url: http://arxiv.org/abs/2502.00739v2
• Date: Fri, 24 Oct 2025 02:52:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 09:00:14.800463
• Title: An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph
• Title（参考訳）: グラフ上での不均衡な措置を伝達するための効率的なオリケンツ・ソボレフ法
• Authors: Tam Le, Truyen Nguyen, Hideitsu Hino, Kenji Fukumizu,
• Abstract要約: 本研究では,全質量の異なるグラフ距離空間における測度に対する最適輸送(OT)について検討する。 従来の$Lp$幾何の制限を緩和するために、Orlicz-Wasserstein (OW) と一般化された Sobolev transport (GST) はOrlicz の幾何学構造を用いる。 二進探索アルゴリズムを用いてOrlicz-EPTを解く理論的背景を確立する。
• 参考スコア（独自算出の注目度）: 26.692344867327332
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We investigate optimal transport (OT) for measures on graph metric spaces with different total masses. To mitigate the limitations of traditional $L^p$ geometry, Orlicz-Wasserstein (OW) and generalized Sobolev transport (GST) employ Orlicz geometric structure, leveraging convex functions to capture nuanced geometric relationships and remarkably contribute to advance certain machine learning approaches. However, both OW and GST are restricted to measures with equal total mass, limiting their applicability to real-world scenarios where mass variation is common, and input measures may have noisy supports, or outliers. To address unbalanced measures, OW can either incorporate mass constraints or marginal discrepancy penalization, but this leads to a more complex two-level optimization problem. Additionally, GST provides a scalable yet rigid framework, which poses significant challenges to extend GST to accommodate nonnegative measures. To tackle these challenges, in this work we revisit the entropy partial transport (EPT) problem. By exploiting Caffarelli & McCann (2010)'s insights, we develop a novel variant of EPT endowed with Orlicz geometric structure, called Orlicz-EPT. We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach. Especially, by leveraging the dual EPT and the underlying graph structure, we formulate a novel regularization approach that leads to the proposed Orlicz-Sobolev transport (OST). Notably, we demonstrate that OST can be efficiently computed by simply solving a univariate optimization problem, in stark contrast to the intensive computation needed for Orlicz-EPT. Building on this, we derive geometric structures for OST and draw its connections to other transport distances. We empirically illustrate that OST is several-order faster than Orlicz-EPT.
• Abstract（参考訳）: 本研究では,全質量の異なるグラフ距離空間における測度に対する最適輸送(OT)について検討する。 従来の$L^p$幾何の制限を緩和するために、Orlicz-Wasserstein (OW) と一般ソボレフ輸送(英語版)(GST)はOrlicz幾何構造を採用し、凸関数を利用してニュアンス付き幾何学的関係を捕捉し、特定の機械学習アプローチの進歩に著しく貢献する。 しかし、OWとGSTはいずれも同じ質量を持つ測度に制限されており、質量変動が一般的である現実のシナリオに適用可能であり、入力測度はノイズの多い支持や外れ値を持つ可能性がある。 アンバランスな測度に対処するために、OW は質量制約や限界差のペナル化を組み込むことができるが、これはより複雑な2段階最適化問題をもたらす。 さらに、GSTはスケーラブルだが堅固なフレームワークを提供しており、非負の措置に対応するためにGSTを拡張する上で大きな課題となる。 これらの課題に対処するため、本研究では、エントロピー部分輸送(EPT)問題を再考する。 Caffarelli & McCann (2010) の洞察を利用して、Orlicz-EPT と呼ばれるOrlicz 幾何学構造を持つ新しい EPT の変種を開発する。 二進探索アルゴリズムを用いてOrlicz-EPTを解く理論的背景を確立する。 特に、双対EPTと基礎となるグラフ構造を利用して、提案されたオルリッツ・ソボレフ輸送(OST)につながる新しい正規化アプローチを定式化する。 特に,OST は Orlicz-EPT に必要とされる計算量とは対照的に,単変量最適化問題を解くだけで効率的に計算できることを示す。 これに基づいてOSTの幾何学的構造を導出し、他の輸送距離に接続する。 我々はOSTがOrlicz-EPTより数桁高速であることを示す。

関連論文リスト

• All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
  我々は、グラフ上の効果的な抵抗と最適輸送は、最大$p$を選択するまで、一つと同じものとして理解されるべきであると主張する。 最適停止時間とグラフ上のランダムウォーク,グラフソボレフ空間,ベナモ・ブレニエ型式に対する2ドルベックマン距離の明示的な接続を示す。 本稿では、ワッサーシュタイン距離が計算ボトルネックを引き起こす可能性のあるこれらの指標のさらなる利用法を提案する。
  論文  参考訳（メタデータ） (2024-04-23T17:50:52Z)
• Generalized Sobolev Transport for Probability Measures on a Graph [26.64899319099165]
  グラフ距離空間上での測度に対する最適輸送(OT)問題について検討する。 我々は、Orlicz構造に対する特定の凸関数のクラスを活用し、一般化されたソボレフ輸送(GST)を提案する。 我々は GST が Orlicz-Wasserstein (OW) よりも数次高速であることを示す。
  論文  参考訳（メタデータ） (2024-02-07T01:49:03Z)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  MLで使用されるほとんどの数学的歪みは、本質的に自然界において積分的である。 本稿では,これらの歪みを改善するための基礎的理論とツールを公表し,機械学習の要件に対処する。 我々は、最近MLで注目を集めた問題、すなわち、ハイパーボリック埋め込みを「チープ」で正確なエンコーディングで適用する方法を示す。
  論文  参考訳（メタデータ） (2024-02-06T17:21:06Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  フービニ・スタディ計量に基づく絡み合い尺度は、Cocchiarellaと同僚によって最近導入された。 本稿では,多モードガウス状態に対する幾何絡み合いの一般化であるガウスエンタングルメント尺度(GEM)を提案する。 自由度の高い系に対する計算可能な多部絡み合わせ測度を提供することにより、自由なボゾン場理論の洞察を得るために、我々の定義が利用できることを示す。
  論文  参考訳（メタデータ） (2024-01-31T15:50:50Z)
• Scalable Unbalanced Sobolev Transport for Measures on a Graph [23.99177001129992]
  最適輸送(OT)は確率測度を比較する強力なツールである。 OT にはいくつかの欠点がある: (i) 同じ質量を持つために必要な入力測度、(ii)高い計算複雑性、(iii)不確定性。 Le et al. (2022) は、支持体上のグラフ構造を利用して、同じ総質量のグラフ上の測度に対して、最近ソボレフ輸送を提案した。 提案した不均衡なソボレフ輸送は高速計算のための閉形式式を許容し,また負の定式であることを示す。
  論文  参考訳（メタデータ） (2023-02-24T07:35:38Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。 フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
  論文  参考訳（メタデータ） (2023-01-10T01:58:15Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。 まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。 我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
  論文  参考訳（メタデータ） (2021-08-18T06:46:59Z)
• Entropy Partial Transport with Tree Metrics: Theory and Practice [5.025654873456756]
  我々は,質量の異なる木上の非負測度に対するtextitentropy partial transport (ept)問題を考える。 高速計算と負の確定性を認める新しい EPT 規則化を提案する。 我々は、正規化が効果的な近似をもたらすことを実証的に証明する。
  論文  参考訳（メタデータ） (2021-01-24T17:04:24Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。 私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。 次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
  論文  参考訳（メタデータ） (2020-06-22T14:35:33Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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