論文の概要: Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions
- arxiv url: http://arxiv.org/abs/2609.13010v1
- Date: Fri, 11 Sep 2026 16:07:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-15 07:38:31.802347
- Title: Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions
- Title（参考訳）: 大規模最適輸送路におけるデュアルガイド型階層エッジ位置決め
- Abstract要約: HELLOは、エッジローカライゼーションとして大規模な離散OTをキャストする階層的解法である。
単一の桁から数千までの特徴次元にまたがって、実行時の順序改善によって、低い輸送目標を達成する。
標準的な離散OT以外にも、半離散OT、Gromov--Wasserstein、アンバランスOT、OTベースのフローマッチングのためのスケーラブルな平衡OTオラクルとして機能する。
- 参考スコア（独自算出の注目度）: 2.9671123446635708
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimal transport (OT) compares distributions and aligns datasets in machine learning, yet unregularized discrete OT requires a linear program with quadratically many transport variables. We propose HELLO, a hierarchical solver that casts large-scale discrete OT as edge localization and uses dual potentials to guide both coarse-to-fine initialization and within-level refinement. Initialization propagates coarse dual potentials across a recursive subsampling hierarchy to assign candidate edges. Refinement then iteratively inserts the largest dual violators in each row and column until the relative KKT residual meets a prescribed tolerance, while budgeted pruning ensures linear memory complexity. For exact-arithmetic refinement, we prove finite termination at a global optimum under a symbolic lexicographic rule. At the million-point scale, HELLO attains lower transport objectives with order-of-magnitude runtime improvements over strong baselines across feature dimensions from single digits to thousands. It further scales to 1.28 million samples per marginal in 8192 dimensions on a single H100, using 41.6 GiB peak GPU memory while satisfying a full relative KKT residual below $10^{-6}$. Beyond standard discrete OT, the framework supports general pairwise costs and serves as a scalable balanced-OT oracle for semi-discrete OT, Gromov--Wasserstein, unbalanced OT, and OT-based Flow Matching.
- Abstract（参考訳）: 最適なトランスポート(OT)は、分散を比較し、機械学習のデータセットを整列させるが、非正規化された離散OTは、二次的に多くのトランスポート変数を持つ線形プログラムを必要とする。
本稿では,大規模離散OTをエッジローカライゼーションとして用いた階層型解法HELLOを提案する。
初期化(initialization)は、再帰的なサブサンプリング階層をまたいで粗い双対ポテンシャルを伝播し、候補エッジを割り当てる。
その後、リファインメントは、相対的なKKT残差が所定の許容値に達するまで、各行と列に最大2つのバイオレータを反復的に挿入し、一方、予算付きプルーニングは線形メモリ複雑性を保証する。
正確な算術的洗練のために、シンボリックな語彙規則の下で、大域的最適点において有限終端を証明した。
百万ポイントのスケールで、HELLOは、単一桁から数千のフィーチャーディメンジョンにまたがる強力なベースラインよりも、高次ランタイムの改善によって、低いトランスポート目標を達成する。
さらに、1つのH100上で8192次元の辺りあたり128万のサンプルにスケールし、41.6 GiBのピークGPUメモリを使用し、KKT残差が10^{-6}$未満の完全な相対的KKTを満足する。
標準的な離散OT以外にも、このフレームワークは一般的なペアワイズコストをサポートし、半離散OT、Gromov--Wasserstein、アンバランスOT、OTベースのフローマッチングのためのスケーラブルな平衡OTオラクルとして機能する。
関連論文リスト
- Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
モデルマージは、個別に調整された複数の専門家をトレーニングデータなしで単一のマルチタスクモデルに結合する。
State-of-the-art merging method formulate merging as a layer-wise interference problem。
本稿では,逐次降下の勾配-流路に一致するソフト指数フィルタを組み合わせた閉形式手法SWUDIを提案する。
論文 参考訳（メタデータ） (2026-06-05T14:00:47Z) - Scaling Parallel Sequence Models to Foundation-Scale Vision Encoders [123.58723804218151]
ビジョンファウンデーションモデルは、自己注意の二次的なコストによってボトルネックとなる。
2次元空間伝搬伝搬に基づくC-GSPNを提案する。
論文 参考訳（メタデータ） (2026-05-30T14:29:43Z) - Hierarchical Transformer Preconditioning for Interactive Physics Simulation [28.137076331332413]
階層型トランスフォーマープレコンディショナー(Hierarchical Transformer Preconditioner)は、弱い許容率のH行列分割に固定されたニューラルプレコンディショナーである。
ネットワークは低ランクの遠距離因子を通して逆をモデル化する。
高速道路の接続を利用して、奥行きを隔ててコンテキストを伝播する。
論文 参考訳（メタデータ） (2026-05-13T11:02:27Z) - Distributed Variational Quantum Linear Solver [2.7835589988032887]
NVIDIA-Q上に構築された分散VQLSフレームワークにより,O(L2)コスト関数評価のスケーラブルな分散を実現する。
高速ウォルシュ・アダマール変換(英語版) (FWHT) によるパウリ分解はLCU項の指数関数的な成長を抑制し、L を n > 6 ビットで O(2n) から O(1) に還元する。
10ビットの3重対角トープリッツ系の場合、これは256倍減少し、99.99%以上の解忠実度を保っている。
論文 参考訳（メタデータ） (2026-04-15T21:27:16Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Transport Clustering: Solving Low-Rank Optimal Transport via Clustering [0.9558392439655014]
我々は,低ランクOT計画の計算アルゴリズムであるトランスポートクラスタリングを導入し,低ランクOTを対応レートのフルテキスト型問題に還元する。
実験的に、トランスポートクラスタリングは、合成ベンチマークや大規模で高次元のデータセットにおいて、既存の低ランクOTソルバよりも優れています。
論文 参考訳（メタデータ） (2026-03-03T23:12:14Z) - GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
一般化空間伝搬ネットワーク(GSPN)は2次自己アテンションを直線走査型伝搬方式に置き換えることでこの問題に対処する。
GSPN-2は、視覚アプリケーションにおけるグローバル空間コンテキストをモデル化するための新しい効率フロンティアを確立する。
論文 参考訳（メタデータ） (2025-11-28T07:26:45Z) - Hierarchical Refinement: Optimal Transport to Infinity and Beyond [1.8749305679160366]
階層化リファインメントはログ線形時間と線形空間で動作し、低ランクOTの利点を保ちながら、その限定解像度を克服していることを示す。
我々は、100万以上のポイントを含むデータセットを含む複数のデータセットで階層的リファインメントの利点を示し、Sinkhornの範囲を超える問題にフルランクOTをスケールする。
論文 参考訳（メタデータ） (2025-03-04T22:00:12Z) - Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
本稿では, コントラスト損失計算を任意の小ブロックに分割するタイルベースの戦略を提案する。
分散システムの階層構造を活用するためのマルチレベルタイリング戦略も導入する。
SOTAメモリ効率のソリューションと比較すると、同等の速度を維持しながら、メモリの2桁の削減を実現している。
論文 参考訳（メタデータ） (2024-10-22T17:59:30Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。