論文の概要: Accelerating Sinkhorn Algorithm with Sparse Newton Iterations

• arxiv url: http://arxiv.org/abs/2401.12253v1
• Date: Sat, 20 Jan 2024 21:23:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-24 17:53:13.994710
• Title: Accelerating Sinkhorn Algorithm with Sparse Newton Iterations
• Title（参考訳）: スパースニュートンイテレーションによるシンクホーンアルゴリズムの高速化
• Authors: Xun Tang, Michael Shavlovsky, Holakou Rahmanian, Elisa Tardini, Kiran Koshy Thekumparampil, Tesi Xiao, Lexing Ying
• Abstract要約: 本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。 SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
• 参考スコア（独自算出の注目度）: 14.094908995798757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computing the optimal transport distance between statistical distributions is a fundamental task in machine learning. One remarkable recent advancement is entropic regularization and the Sinkhorn algorithm, which utilizes only matrix scaling and guarantees an approximated solution with near-linear runtime. Despite the success of the Sinkhorn algorithm, its runtime may still be slow due to the potentially large number of iterations needed for convergence. To achieve possibly super-exponential convergence, we present Sinkhorn-Newton-Sparse (SNS), an extension to the Sinkhorn algorithm, by introducing early stopping for the matrix scaling steps and a second stage featuring a Newton-type subroutine. Adopting the variational viewpoint that the Sinkhorn algorithm maximizes a concave Lyapunov potential, we offer the insight that the Hessian matrix of the potential function is approximately sparse. Sparsification of the Hessian results in a fast $O(n^2)$ per-iteration complexity, the same as the Sinkhorn algorithm. In terms of total iteration count, we observe that the SNS algorithm converges orders of magnitude faster across a wide range of practical cases, including optimal transportation between empirical distributions and calculating the Wasserstein $W_1, W_2$ distance of discretized densities. The empirical performance is corroborated by a rigorous bound on the approximate sparsity of the Hessian matrix.
• Abstract（参考訳）: 統計分布間の最適な輸送距離を計算することは機械学習の基本的なタスクである。 最近の顕著な進歩の1つはエントロピー正則化とシンクホーンアルゴリズムであり、これは行列スケーリングのみを利用し、ニア線形ランタイムで近似された解を保証する。 Sinkhornアルゴリズムの成功にもかかわらず、収束に必要なイテレーションが多すぎる可能性があるため、実行は遅くなる可能性がある。 超指数収束を実現するために,マトリクススケーリングステップの早期停止とニュートン型サブルーチンを特徴とする第2段を導入することで,シンクホーンアルゴリズムの拡張であるsns(singhorn-newton-sparse)を提案する。 シンクホーンアルゴリズムが凹リアプノフポテンシャルを最大化する変分的視点を採用することにより、ポテンシャル関数のヘッセン行列がおよそスパースであることを示す。 ヘッセンのスパーシフィケーションは、シンクホーンのアルゴリズムと同じ、高速な$O(n^2)$/iteration複雑性をもたらす。 合計反復数に関して、SNSアルゴリズムは、経験的分布間の最適な移動や、ワッサーシュタイン$W_1, W_2$の離散密度距離の計算を含む、幅広い実践事例において、桁違いに高速に収束する。 経験的性能は、ヘッセン行列の近似スパース性に厳密な束縛によって裏付けられる。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Compressed online Sinkhorn [3.2534959204741085]
  我々は最近導入された[Mensch and Peyr'e, 2020]オンラインシンクホーンアルゴリズムを再考する。 我々は、オンラインシンクホーンアルゴリズムの収束解析を改善し、パラメータ選択によって得られる新しいレートは、以前のレートよりも高速である。 次に, オンラインシンクホーン法と, オンラインシンクホーン法を組み合わせた圧縮オンラインシンクホーン法を提案する。
  論文  参考訳（メタデータ） (2023-10-08T05:33:32Z)
• Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach [10.568851068989972]
  本稿では,アルゴリズムの効率的な解法を実現するために,元のOT問題であるエントロピックOT問題の緩和に焦点をあてる。 この定式化はSchr"odinger Bridge問題としても知られ、特に最適制御(SOC)と結びつき、人気のあるシンクホーンアルゴリズムで解くことができる。
  論文  参考訳（メタデータ） (2023-04-13T13:58:25Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
  本稿では,ネステロフの平滑化手法に基づく効率と精度をさらに向上させる新しいアルゴリズムを提案する。 提案手法は,同じパラメータでより高速な収束と精度を実現する。
  論文  参考訳（メタデータ） (2021-04-12T20:23:29Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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