論文の概要: Compressed online Sinkhorn
- arxiv url: http://arxiv.org/abs/2310.05019v1
- Date: Sun, 8 Oct 2023 05:33:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 13:25:59.859084
- Title: Compressed online Sinkhorn
- Title（参考訳）: 圧縮オンラインシンクホーン
- Authors: Fengpei Wang and Clarice Poon and Tony Shardlow
- Abstract要約: 我々は最近導入された[Mensch and Peyr'e, 2020]オンラインシンクホーンアルゴリズムを再考する。
我々は、オンラインシンクホーンアルゴリズムの収束解析を改善し、パラメータ選択によって得られる新しいレートは、以前のレートよりも高速である。
次に, オンラインシンクホーン法と, オンラインシンクホーン法を組み合わせた圧縮オンラインシンクホーン法を提案する。
- 参考スコア（独自算出の注目度）: 3.2534959204741085
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The use of optimal transport (OT) distances, and in particular
entropic-regularised OT distances, is an increasingly popular evaluation metric
in many areas of machine learning and data science. Their use has largely been
driven by the availability of efficient algorithms such as the Sinkhorn
algorithm. One of the drawbacks of the Sinkhorn algorithm for large-scale data
processing is that it is a two-phase method, where one first draws a large
stream of data from the probability distributions, before applying the Sinkhorn
algorithm to the discrete probability measures. More recently, there have been
several works developing stochastic versions of Sinkhorn that directly handle
continuous streams of data. In this work, we revisit the recently introduced
online Sinkhorn algorithm of [Mensch and Peyr\'e, 2020]. Our contributions are
twofold: We improve the convergence analysis for the online Sinkhorn algorithm,
the new rate that we obtain is faster than the previous rate under certain
parameter choices. We also present numerical results to verify the sharpness of
our result. Secondly, we propose the compressed online Sinkhorn algorithm which
combines measure compression techniques with the online Sinkhorn algorithm. We
provide numerical experiments to show practical numerical gains, as well as
theoretical guarantees on the efficiency of our approach.
- Abstract（参考訳）: 最適輸送(ot)距離、特にエントロピー正規化ot距離の使用は、機械学習やデータサイエンスの多くの分野において、ますます一般的な評価基準となっている。
彼らの用途は、シンクホーンアルゴリズムのような効率的なアルゴリズムが利用できることによる。
大規模データ処理におけるシンクホーンアルゴリズムの欠点の1つは、Sinkhornアルゴリズムを離散確率測度に適用する前に、まず確率分布から大量のデータを描画する2相法であることである。
最近では、連続的なデータストリームを直接処理するSinkhornの確率的なバージョンの開発がいくつか行われている。
本稿では,最近導入された[Mensch and Peyr\'e, 2020]のオンラインシンクホーンアルゴリズムを再考する。
オンラインシンクホーンアルゴリズムの収束解析を改善することで、特定のパラメータ選択下での以前のレートよりも高速に得られる新しいレートを得ることができます。
また,結果のシャープさを検証するために,数値的な結果も提示する。
第二に,オンラインシンクホーンアルゴリズムと圧縮手法を組み合わせた圧縮オンラインシンクホーンアルゴリズムを提案する。
我々は,実用的な数値ゲインを示す数値実験と,手法の効率性に関する理論的保証を提供する。
関連論文リスト
- Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。
SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
論文 参考訳（メタデータ） (2024-01-20T21:23:09Z) - Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
データストリームに現れる要素の頻度を推定することは、大規模データ分析において重要なタスクである。
理論的には,Hsu等の学習に基づくアルゴリズムを,予測を使わずに上回る新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-12T18:59:06Z) - Sinkhorn Flow: A Continuous-Time Framework for Understanding and
Generalizing the Sinkhorn Algorithm [49.45427072226592]
我々はシンクホーンアルゴリズムの連続時間アナログを導入する。
この観点から、ノイズやバイアスに頑健なシンクホーンスキームの新たな変種を導出することができる。
論文 参考訳（メタデータ） (2023-11-28T11:29:12Z) - Data Assimilation for Sign-indefinite Priors: A generalization of
Sinkhorn's algorithm [0.0]
更新された値が指定された限界値と一致するように,符号の不確定な多次元配列を再検討する。
我々のアプローチはシュル「オーディンガー問題」の理性に従っており、限界分布に一致するように「適切な」確率測度を更新することを目的としている。
論文 参考訳（メタデータ） (2023-08-22T21:13:39Z) - A Unified Framework for Implicit Sinkhorn Differentiation [58.56866763433335]
暗黙の微分によってシンクホーン層の解析勾配を求めるアルゴリズムを提案する。
特にGPUメモリなどのリソースが不足している場合には,計算効率が向上する。
論文 参考訳（メタデータ） (2022-05-13T14:45:31Z) - Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。
従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。
提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
論文 参考訳（メタデータ） (2022-03-17T19:26:00Z) - 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) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z) - Sparse Sinkhorn Attention [93.88158993722716]
Sparse Sinkhorn Attentionを提案する。
本稿では,列上の潜在置換を生成するメタソートネットワークを提案する。
ソートシーケンスが与えられた場合、局所ウィンドウのみを用いて準グロバルアテンションを計算することができる。
論文 参考訳（メタデータ） (2020-02-26T04:18:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。