論文の概要: Low-Rank Sinkhorn Factorization

• arxiv url: http://arxiv.org/abs/2103.04737v1
• Date: Mon, 8 Mar 2021 13:18:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-10 11:27:19.020162
• Title: Low-Rank Sinkhorn Factorization
• Title（参考訳）: 低速シンクホーンファクタリゼーション
• Authors: Meyer Scetbon, Marco Cuturi, Gabriel Peyr\'e
• Abstract要約: 本稿では,テキストサブカップリング係数の積として,低位結合の明示的な因子化を導入する。 このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。
• 参考スコア（独自算出の注目度）: 45.87981728307819
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Several recent applications of optimal transport (OT) theory to machine learning have relied on regularization, notably entropy and the Sinkhorn algorithm. Because matrix-vector products are pervasive in the Sinkhorn algorithm, several works have proposed to \textit{approximate} kernel matrices appearing in its iterations using low-rank factors. Another route lies instead in imposing low-rank constraints on the feasible set of couplings considered in OT problems, with no approximations on cost nor kernel matrices. This route was first explored by Forrow et al., 2018, who proposed an algorithm tailored for the squared Euclidean ground cost, using a proxy objective that can be solved through the machinery of regularized 2-Wasserstein barycenters. Building on this, we introduce in this work a generic approach that aims at solving, in full generality, the OT problem under low-rank constraints with arbitrary costs. Our algorithm relies on an explicit factorization of low rank couplings as a product of \textit{sub-coupling} factors linked by a common marginal; similar to an NMF approach, we alternatively updates these factors. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.
• Abstract（参考訳）: 機械学習への最適輸送(OT)理論の最近の適用は正規化、特にエントロピーとシンクホーンアルゴリズムに依存している。 行列ベクトル積はシンクホーンアルゴリズムで広く普及しているため、いくつかの研究が低ランク因子を用いて反復で現れるカーネル行列に対して提案されている。 別の経路は、ot問題で考慮されるカップリングの実行可能な集合に低ランク制約を課すことであり、コストやカーネル行列の近似は含まない。 この経路は2018年にforrowらによって初めて研究され、正則化された2-wasserstein barycentersの機械で解くことができるプロキシの目的を用いて、二乗ユークリッドの地上コストに合わせたアルゴリズムを提案した。 そこで本研究では,低ランク制約下におけるOT問題を完全一般化して,任意のコストで解決することを目的とした汎用的なアプローチを提案する。 提案アルゴリズムは, NMF法と同様に, これらの因子を更新するために, 共通限界によって関連づけられた {textit{sub-coupling} 因子の積として, 低階結合の明示的な分解に依存する。 このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle [16.290192687098383]
  本稿では,アフィン制約を伴う凸複合最適化問題について考察する。 正確なプロジェクション/近距離計算が難解な高次元アプリケーションにより,テキスト投影のないラグランジアン型拡張手法を提案する。
  論文  参考訳（メタデータ） (2022-10-25T12:51:43Z)
• Rethinking Initialization of the Sinkhorn Algorithm [36.72281550968301]
  データ依存型初期化器は、暗黙の微分が用いられる限り、微分可能性に影響を与えない、劇的なスピードアップをもたらすことを示す。 我々の手法は、1D、ガウス、GMM設定で知られている正確なOT解や近似OT解に対して閉形式に依存している。
  論文  参考訳（メタデータ） (2022-06-15T16:23:03Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
  核ノルムへの凸緩和を最小化することは、推奨システムと堅牢な主成分分析に重要である。 本研究では, ブイロとルクシロによる核プログラムのランク因数分解のための効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-13T19:04:37Z)

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

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