論文の概要: Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe

• arxiv url: http://arxiv.org/abs/2201.00730v1
• Date: Mon, 3 Jan 2022 16:07:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-04 15:31:00.680122
• Title: Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
• Title（参考訳）: 高速不均衡最適輸送:Sinkhornと1次元Frank-Wolfeの翻訳不変性
• Authors: Thibault S\'ejourn\'e, Fran\c{c}ois-Xavier Vialard and Gabriel Peyr\'e
• Abstract要約: 非平衡最適輸送(UOT)は、分布を比較するために質量変動を考慮した最適輸送(OT)を拡張する。 これは、OTをMLアプリケーションで成功させることで、データの正規化とアウトレイラに対して堅牢になる。 本研究では、この欠損の原因、すなわち、二元OTポテンシャルの翻訳に等価な、反復体の大域正規化の欠如を同定する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Unbalanced optimal transport (UOT) extends optimal transport (OT) to take into account mass variations to compare distributions. This is crucial to make OT successful in ML applications, making it robust to data normalization and outliers. The baseline algorithm is Sinkhorn, but its convergence speed might be significantly slower for UOT than for OT. In this work, we identify the cause for this deficiency, namely the lack of a global normalization of the iterates, which equivalently corresponds to a translation of the dual OT potentials. Our first contribution leverages this idea to develop a provably accelerated Sinkhorn algorithm (coined 'translation invariant Sinkhorn') for UOT, bridging the computational gap with OT. Our second contribution focusses on 1-D UOT and proposes a Frank-Wolfe solver applied to this translation invariant formulation. The linear oracle of each steps amounts to solving a 1-D OT problems, resulting in a linear time complexity per iteration. Our last contribution extends this method to the computation of UOT barycenter of 1-D measures. Numerical simulations showcase the convergence speed improvement brought by these three approaches.
• Abstract（参考訳）: 非平衡最適輸送(UOT)は、分布を比較するために質量変動を考慮した最適輸送(OT)を拡張する。 これは、OTをMLアプリケーションで成功させることで、データの正規化と外部化に対して堅牢になる。 ベースラインアルゴリズムはシンクホーンであるが、収束速度はOTよりもUTTの方がかなり遅い。 本研究では、この不足の原因、すなわち2つのotポテンシャルの翻訳に相当するイテレートのグローバル正規化の欠如を特定する。 最初のコントリビューションは、このアイデアを活用して、OTとの計算ギャップを埋める、証明可能な加速Sinkhornアルゴリズム("translation invariant Sinkhorn"と呼ばれる)を開発した。 第2のコントリビューションは1次元 UOT に着目し,この変換不変な定式化に適用したフランク・ウルフ解法を提案する。 各ステップの線形オラクルは、1-D OT問題の解決に相当し、イテレーション毎に線形時間複雑になる。 最後の貢献は、この手法を1次元測度の uot barycenter の計算に拡張することです。 数値シミュレーションは,これら3つの手法による収束速度の向上を示す。

関連論文リスト

• Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing [4.44549269470273]
  Sinkhornのアルゴリズムは、大規模な最適輸送(OT)問題を解決する方法である。 コンケーブスケジュールアルゴリズムがOTを解くことは、$beta_tto+infty$と$beta_t-beta_t-1to 0$の場合に限る。 本稿では, 緩和誤差を低減するため, 簡易なアンナーレ・シンクホーンの修正を提案する。
  論文  参考訳（メタデータ） (2024-08-21T13:47:01Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Sparsity-Constrained Optimal Transport [27.76137474217754]
  正規化された最適輸送は、ニューラルネットワークの損失層やマッチング層として、ますます利用されている。 本稿では,交通計画に明示的な基数制約を課したOTに対する新しいアプローチを提案する。 本手法は,非正規化OT($k$の場合)と二次正規化OT($k$が十分に大きい場合)の中間地盤と考えることができる。
  論文  参考訳（メタデータ） (2022-09-30T13:39:47Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem [20.661025590877774]
  凸半緩和最適輸送(OT)問題に対する高速ブロックコーディネートFrank-Wolfe (BCFW) アルゴリズムを提案する。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端のアルゴリズムを超越することを示した。
  論文  参考訳（メタデータ） (2022-05-27T05:54:45Z)
• An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem [2.1485350418225244]
  線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。 PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
  論文  参考訳（メタデータ） (2022-03-02T01:16:10Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Debiased Sinkhorn barycenters [110.79706180350507]
  最適輸送(OT)におけるエントロピー正則化(Entropy regularization)は、機械学習におけるWassersteinメトリクスやバリセンタに対する近年の関心の原動力となっている。 このバイアスがエントロピー正則化器を定義する基準測度とどのように密接に関連しているかを示す。 両世界の長所を保ち、エントロピーを滑らかにしないシンクホーン様の高速な反復をデバイアスド・ワッサースタインのバリセンタとして提案する。
  論文  参考訳（メタデータ） (2020-06-03T23:06:02Z)

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

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