論文の概要: SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport
- arxiv url: http://arxiv.org/abs/2608.28262v1
- Date: Fri, 28 Aug 2026 12:24:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-31 17:16:04.314218
- Title: SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport
- Title（参考訳）: SinkSLOT: Sinkhorn:Sparse Lifted Optimal Transport
- Abstract要約: Standard Sinkhorn-Knoppアルゴリズムには2つの制限がある。
SinkSLOTは、Gibsカーネルを非依存の事前結合でスパースする自然な方法として、期待されるスライスされたリフテッドトランスポート計画を公開した。
合成ベンチマークの実験により、SinkSLOTは最先端の高密度でスパースなEOT法よりもかなり高速であることが示された。
- 参考スコア（独自算出の注目度）: 3.4494862188977637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with $N$ points, each iteration requires $O(N^2)$ operations, which restricts its use on large-scale datasets (e.g. $N\geq10^4$). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with $L$ slices, each resulting sparse Sinkhorn iteration costs $O(LN)$; and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.
- Abstract（参考訳）: エントロピック最適輸送(EOT)は、正確な最適輸送に対する計算計算可能な近似を提供することが示されている。
しかし、Sinkhorn-Knoppアルゴリズムには2つの大きな制限がある。
まず、$N$ポイントの離散測度が与えられた場合、各反復は$O(N^2)$演算を必要とし、大規模なデータセットでの使用を制限する(例:$N\geq10^4$)。
第二に、独立結合を正規化の基準尺度として使う。
これにより、中程度の正則化強度で高速輸送エッジに質量を割り当てる。
本稿では,Gibsカーネルを非依存の事前結合でスパースする自然な方法として,期待されるスライスリフト輸送計画を設定することにより,両方の制約に対処するSinkSLOTを提案する。
私たちはそれを証明します。
1) SinkSLOT が収束する。
2)$L$スライスすると、それぞれのスパークのSinkhornイテレーションは$O(LN)$; そして
3) 結果の目的は, 偏見を伴わない分散である。
合成ベンチマークの実験により、SinkSLOTは最先端の高密度でスパースなEOT法よりも大幅にスピードアップすることが示された。
また,勾配流実験において提案手法の適用性を示す。
コードはhttps://github.com/cai4cai/SinkSLOT.comで公開されている。
関連論文リスト
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport [10.787490135016155]
Sinkhorn-Knoppアルゴリズムは、行列スケーリングと最適輸送のための基礎的手法である。
本稿では,局所的なバルク質量特性である well-boundedness の概念を紹介する。
事実上コストのない事前スケーリングのステップは、次元依存を完全に排除することを示す。
論文 参考訳（メタデータ） (2026-04-04T16:24:19Z) - Accelerated Sinkhorn Algorithms for Partial Optimal Transport [1.6528632644902823]
我々は,POT設定においてNesterovスタイルの加速度と交互に最小化を統合するASPOT(Accelerated Sinkhorn for POT)を導入する。
エントロピーパラメータを$$で選択することで、古典的なシンクホーン法の精度が向上することを示す。
論文 参考訳（メタデータ） (2026-01-23T21:55:27Z) - Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文 参考訳（メタデータ） (2025-02-11T19:54:11Z) - Quantum state preparation with optimal T-count [1.9402062012850008]
任意の$n$-qubit量子状態を誤差$varepsilon$に近似するために、Tゲートがいくつ必要かを示す。
また、これは任意の対角線$n$-qubitユニタリをエラー$varepsilon$に実装するための最適なTカウントであることを示す。
論文 参考訳（メタデータ） (2024-11-07T15:29:33Z) - Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - 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) - On Unbalanced Optimal Transport: Gradient Methods, Sparsity and
Approximation Error [18.19398247972205]
我々は、少なくとも$n$の成分を持つ、おそらく異なる質量の2つの測度の間の不均衡最適輸送(UOT)について研究する。
UOT問題に対する$varepsilon$-approximateの解を求めるために,GEM-UOT(Gradient Extrapolation Method)に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-08T03:22:39Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。