論文の概要: Importance Sparsification for Sinkhorn Algorithm
- arxiv url: http://arxiv.org/abs/2306.06581v1
- Date: Sun, 11 Jun 2023 04:03:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-13 18:07:19.353294
- Title: Importance Sparsification for Sinkhorn Algorithm
- Title（参考訳）: シンクホーンアルゴリズムにおける重要スパーシフィケーション
- Authors: Mengyu Li, Jun Yu, Tao Li, Cheng Meng
- Abstract要約: シンクホーンアルゴリズムは最適輸送 (OT) と不均衡最適輸送 (UOT) 問題の解を近似するために広く用いられている。
本研究では, エントロピー規則化OTとUOTの解を効率的に近似するために, Spar-Sink と呼ばれる新しい重要空間分割法を提案する。
- 参考スコア（独自算出の注目度）: 19.658596636055545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sinkhorn algorithm has been used pervasively to approximate the solution to
optimal transport (OT) and unbalanced optimal transport (UOT) problems.
However, its practical application is limited due to the high computational
complexity. To alleviate the computational burden, we propose a novel
importance sparsification method, called Spar-Sink, to efficiently approximate
entropy-regularized OT and UOT solutions. Specifically, our method employs
natural upper bounds for unknown optimal transport plans to establish effective
sampling probabilities, and constructs a sparse kernel matrix to accelerate
Sinkhorn iterations, reducing the computational cost of each iteration from
$O(n^2)$ to $\widetilde{O}(n)$ for a sample of size $n$. Theoretically, we show
the proposed estimators for the regularized OT and UOT problems are consistent
under mild regularity conditions. Experiments on various synthetic data
demonstrate Spar-Sink outperforms mainstream competitors in terms of both
estimation error and speed. A real-world echocardiogram data analysis shows
Spar-Sink can effectively estimate and visualize cardiac cycles, from which one
can identify heart failure and arrhythmia. To evaluate the numerical accuracy
of cardiac cycle prediction, we consider the task of predicting the end-systole
time point using the end-diastole one. Results show Spar-Sink performs as well
as the classical Sinkhorn algorithm, requiring significantly less computational
time.
- Abstract（参考訳）: シンクホーンアルゴリズムは最適輸送(OT)と不均衡最適輸送(UOT)問題の解を近似するために広く用いられている。
しかし、その実用的応用は高い計算複雑性のために限られている。
計算負荷を軽減するため,エントロピー正規化otおよびuot溶液を効率的に近似するために,spar-sinkと呼ばれる新しい重要スパース化法を提案する。
具体的には,効率的なサンプリング確率を確立するために,未知の最適輸送計画に対して自然上界を用い,各イテレーションの計算コストを$o(n^2)$ から$\widetilde{o}(n)$ に削減して,ダウンホーン反復を高速化するスパースカーネル行列を構築した。
理論的には、正規化OTおよびOT問題に対する提案した推定器は、穏やかな規則性条件下で一貫したものである。
様々な合成データの実験では、Spar-Sinkは推定誤差と速度の両方において、主流の競合より優れていた。
実世界の心エコーデータ分析によれば、spar-sinkは心不全や不整脈を識別できる心周期を効果的に推定し可視化できる。
心臓周期予測の数値的精度を評価するために, エンドダイアソールを用いたエンドシストール時点の予測について検討する。
その結果、Spar-Sinkは古典的なシンクホーンアルゴリズムと同様に、計算時間を大幅に削減することを示した。
関連論文リスト
- An inexact Bregman proximal point method and its acceleration version
for unbalanced optimal transport [16.12354882333828]
不均衡最適輸送(UOT)問題は、計算生物学、計算イメージング、ディープラーニングにおいてますます重要な役割を担っている。
スケーリングアルゴリズムは、その利便性と優れた収束特性のために、UTTを解くために広く用いられている。
UOTを解くための不正確なBregman近点法を開発することで、この問題に対処する。
論文 参考訳（メタデータ） (2024-02-26T19:25:21Z) - Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。
SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
論文 参考訳（メタデータ） (2024-01-20T21:23:09Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。
カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。
我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-10-09T03:55:09Z) - Towards Understanding the Generalizability of Delayed Stochastic
Gradient Descent [63.43247232708004]
非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。
既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。
我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
論文 参考訳（メタデータ） (2023-08-18T10:00:27Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Robust computation of optimal transport by $\beta$-potential
regularization [79.24513412588745]
最適輸送(OT)は、確率分布間の差を測定する機械学習分野で広く使われているツールである。
我々は、いわゆる$beta$-divergenceに付随するベータポテンシャル項でOTを正規化することを提案する。
提案アルゴリズムで計算した輸送行列は,外乱が存在する場合でも確率分布を頑健に推定するのに役立つことを実験的に実証した。
論文 参考訳（メタデータ） (2022-12-26T18:37:28Z) - 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) - COT-GAN: Generating Sequential Data via Causal Optimal Transport [4.588028371034406]
逐次データを生成するために暗黙的な生成モデルを訓練する逆アルゴリズムであるCOT-GANを導入する。
アルゴリズムの成功は、学習のバイアスを減らしたシンクホーン発散の新たな改良版にも依存している。
論文 参考訳（メタデータ） (2020-06-15T17:37:15Z) - Stochastic Gradient Langevin with Delayed Gradients [29.6870062491741]
本研究では,計算に用いた遅延勾配情報による誤差が測定値の収束率に有意な影響を及ぼさないことを示す。
計算に用いた遅延勾配情報による誤差は, 測定値の収束率に有意な影響を与えず, ウォールクロック時間における高速化の可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-12T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。