論文の概要: Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs

• arxiv url: http://arxiv.org/abs/2106.01128v1
• Date: Wed, 2 Jun 2021 12:50:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-03 23:12:42.480269
• Title: Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Title（参考訳）: 低ランク結合とコストを用いた線形時間Gromov Wasserstein距離
• Authors: Meyer Scetbon, Gabriel Peyr\'e, Marco Cuturi
• Abstract要約: 異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。 グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
• 参考スコア（独自算出の注目度）: 45.87981728307819
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem. Its main goal is to seek an assignment (more generally a coupling matrix) that can register points across otherwise incomparable datasets. As a non-convex and quadratic generalization of optimal transport (OT), GW is NP-hard. Yet, heuristics are known to work reasonably well in practice, the state of the art approach being to solve a sequence of nested regularized OT problems. While popular, that heuristic remains too costly to scale, with cubic complexity in the number of samples $n$. We show in this paper how a recent variant of the Sinkhorn algorithm can substantially speed up the resolution of GW. That variant restricts the set of admissible couplings to those admitting a low rank factorization as the product of two sub-couplings. By updating alternatively each sub-coupling, our algorithm computes a stationary point of the problem in quadratic time with respect to the number of samples. When cost matrices have themselves low rank, our algorithm has time complexity $\mathcal{O}(n)$. We demonstrate the efficiency of our method on simulated and real data.
• Abstract（参考訳）: 異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を果たす。 gromov-wasserstein (gw)形式はこの問題に取り組むのに役立つ。 その主な目標は、比較不能なデータセットにポイントを登録できる代入(より一般的には結合行列)を求めることである。 非凸かつ二次的な最適輸送(OT)の一般化として、GWはNPハードである。 しかし、ヒューリスティックスは実際かなりうまく機能することが知られており、最先端の手法は入れ子化された正規化ot問題の列を解くことである。 人気があるとはいえ、このヒューリスティックはスケールするにはコストがかかりすぎ、サンプル数に3分の1の複雑さがある。 本稿では,Sinkhornアルゴリズムの最近の変種が,GWの分解能を大幅に向上させる方法を示す。 この変種は、許容結合の集合を2つの部分結合の積として低階分解を許容するものに制限する。 各サブカップリングを交互に更新することで、本アルゴリズムはサンプル数に対して二次時間で問題の静止点を計算する。 コスト行列が低ランクであるとき、我々のアルゴリズムは時間複雑性$\mathcal{O}(n)$である。 シミュレーションおよび実データに対する提案手法の有効性を実証する。

関連論文リスト

• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Efficient Strongly Polynomial Algorithms for Quantile Regression [12.772027028644041]
  量子回帰(QR)の古典的手法を再考する 本稿では,様々な設定に対して,QRに対して高効率な古典的アルゴリズムを提案する。 2次元QRでは、$k$-setという幾何学的概念に結びつくため、$mathcalO(n4/3 polylog(n))$の最悪の時間複雑性を持つアルゴリズムを提案する。 2次元に対して$mathcalO(nlog2(n))$の期待時間複雑性を持つランダム化QRも提案する。
  論文  参考訳（メタデータ） (2023-07-14T03:07:42Z)
• Learning Transition Operators From Sparse Space-Time Samples [11.859913430860335]
  遷移作用素$mathbfA$を異なる時間における部分的な観測から学習する非線形問題を考察する。 我々は、$mathcalOrn log(nT)$ space-time sample が、ランク=r$演算子の正確な回復を保証するのに十分であることを示す。
  論文  参考訳（メタデータ） (2022-12-01T18:33:59Z)
• 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)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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