論文の概要: Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory
- arxiv url: http://arxiv.org/abs/2609.33814v1
- Date: Sun, 27 Sep 2026 18:09:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-04 16:34:22.153124
- Title: Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory
- Title（参考訳）: モメンタム付焼成シンクホーン--リニアメモリにおける不規則化最適輸送の証明
- Abstract要約: 非正規化された離散的最適輸送に対してBDRS(Bregman Douglas-Rachford splitting)を特徴付ける。
線形メモリにおける任意の原始双対証明書を開発する。
- 参考スコア（独自算出の注目度）: 3.248584983235657
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We characterize Bregman Douglas-Rachford splitting (BDRS) for unregularized discrete optimal transport and develop an anytime primal-dual certificate in linear memory. We first establish that BDRS coincides with warm-started Inexact Proximal point method for exact Optimal Transport (IPOT) using a single inner Sinkhorn iteration. By eliminating the primal transport plan from the updates, we derive an equivalent dual formulation that reveals BDRS as annealed Sinkhorn under an implicit inverse-linear temperature schedule, with an additional log-scaling momentum term and a cooler kernel. While this explains the role of the temperature parameter in BDRS as an initial temperature, it also reduces the solver's memory requirement from quadratic to linear. Utilizing this annealing perspective, we introduce overrelaxed BDRS, which combines annealing and overrelaxed scaling within a single recursion. We derive a primal-dual certificate for both methods that can be evaluated in linear memory without transport plan construction, thus providing a computable stopping rule. On the DOTmark benchmark, combining momentum with the cooler kernel produces substantially smaller optimality gaps than annealed Sinkhorn under the same schedule. For pixel-level color transfer between $1024\times1024$ images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9$\times$ speed up, reaching a relative duality gap of $1.59\%$ in 24 minutes. We further demonstrate a color transfer with $4238\times2365$ images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of $2.41\%$ and $2.80\%$ within 35 hours in each direction on a single NVIDIA L40S GPU.
- Abstract（参考訳）: 本稿では,非正規化された離散的最適輸送のためのBregman Douglas-Rachfordスプリッティング(BDRS)を特徴付け,線形メモリにおける任意の原始双対証明書を開発する。
まず,BDRSは,1つの内部シンクホーン繰り返しを用いた正確な最適輸送(IPOT)のための暖かく開始した不正確な近点法と一致することを確認した。
更新から一次輸送計画を排除することにより、暗黙の逆線形温度スケジュールの下で、BDRSをアニールしたシンクホーンとして表す等価な二重定式化が導出され、追加の対数スケーリングモーメント項とクーラーカーネルが提供される。
このことは、BDRSにおける温度パラメータが初期温度としての役割を説明する一方で、ソルバのメモリ要求を2次から線形に減少させる。
このアニーリングの観点を利用して,1回の再帰でアニーリングとオーバーラックスのスケーリングを組み合わせたオーバーラックスBDRSを導入する。
我々は、輸送計画構築なしで線形メモリで評価できる2つの手法の原始双対証明を導出し、計算可能な停止規則を提供する。
DOTmarkベンチマークでは、冷却されたカーネルと組み合わせることで、同じスケジュールでアニールされたシンクホーンよりもかなり小さな最適性ギャップが生成される。
1024\times1024$画像間のピクセルレベルのカラー転送では、BDRSはMDOT-TNTよりも低コストで9$\times$スピードアップし、24分で1.59\%の相対的な双対性ギャップに達する。
さらに、4238\times2365$イメージによるカラー転送を実証し、画像当たり1000万ピクセル、約100兆の暗黙のトランスポートエントリを生成し、単一のNVIDIA L40S GPU上で各方向に35時間以内に2.41\%と2.80\%の相対双対性ギャップに達した。
関連論文リスト
- Demystifying Pipeline Parallelism: First Theory for PipeDream [53.657104889705856]
本稿では、PDスタイルの手法に対して、クリーンな非収束性をもたらす固定ブロック-SGD抽象化としてランダム化PipeDream(PD)を導入する。
定常PDによって引き起こされる遅延は、$S2 - S/2 + O(1)$ for $S$として増大するので、スタイルリードのコントリビューションは、チューナレート形式で$(2S4)$、同等に$(S4/K)$としてスケールする。
論文 参考訳（メタデータ） (2026-06-02T11:14:57Z) - RiT: Vanilla Diffusion Transformers Suffice in Representation Space [12.711808725422108]
x$prediction とのフローマッチングは、ピクセル空間 citeli2025back において、低次元多様体構造を効果的に活用することが知られている。
事前学習された表現空間は、本質的な次元に匹敵する低次元データ多様体を含むが、フローマッチング学習に好適な分布を提供するかどうかを問う。
論文 参考訳（メタデータ） (2026-05-21T04:21:43Z) - IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback [0.0]
意思決定にフォーカスした学習トレインは、下流の意思決定損失に対してエンドツーエンドでモデルをモデル化するが、オンライン設定は遅延したフィードバックに悩まされる。
遅延下での2レベル最適化に特有の障害モードであるエンフスタレンス増幅を同定する。
ブラックボックス遅延勾配が内部解法近似誤差から既約後悔コストを生じることを証明した。
論文 参考訳（メタデータ） (2026-05-12T19:43:49Z) - DualTCN: A Physics-Constrained Temporal Convolutional Network for 2 Time-Domain Marine CSEM Inversion [1.2031796234206138]
DualTCNは、時間領域の海洋電磁制御源(MCSEM)過渡データを反転させるための最初のディープラーニングフレームワークである。
このフレームワークは、4つのアースモデルパラメータを回帰し、微分可能なソフトステップデコーダを用いてプロファイルを再構成する。
このフレームワークは、カリキュラムベースの振幅増大によるノイズに対する高い堅牢性を示し、平均$barR2$ 0.858 at $pm2%$ランダム振幅誤差を維持している。
論文 参考訳（メタデータ） (2026-05-06T14:58:17Z) - Optimal Decay Spectra for Linear Recurrences [6.508284558109273]
PoSTは任意の対角線再帰をオーバーヘッドなく統合する。
Mamba RWKV-7、Gated DeltaNet、Gated Linear Attention、RetNetでインスタンス化します。
論文 参考訳（メタデータ） (2026-04-08T23:54:57Z) - Robust Sublinear Convergence Rates for Iterative Bregman Projections [21.689846521201588]
エントロピック正規化(entropic regularization)は、制約が2つ(またはそれ以上)のトラクタブルブロックに分割された線形プログラムに近似する。
グラフ上のWasserstein-1距離に対するフローシンクホーンアルゴリズムを導出する。
論文 参考訳（メタデータ） (2026-02-01T18:20:19Z) - Robust Layerwise Scaling Rules by Proper Weight Decay Tuning [50.11170157029911]
現代のスケール不変アーキテクチャでは、トレーニングは急速に劣化したグラデーション状態に入る。
我々は,AdamWに対して,幅をまたいだサブ層ゲインを保ったウェイトデカイスケーリングルールを導入する。
この結果は,パラメータが設定した定常スケールを明示的に制御することにより,ほぼ入出力体制を超えて$mu$Pを拡大する。
論文 参考訳（メタデータ） (2025-10-17T02:58:35Z) - Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
最適輸送(OT)理論はそのようなマッピングを構築するための原則的な枠組みを提供する。
We propose a novel solver based on Wasserstein-1 (W$) dual formulation。
我々の実験は、提案した$W$のニューラル・トランスポート・ソルバが、ユニークなモンマップを見つける際に、$W$のOTを模倣できることを実証した。
論文 参考訳（メタデータ） (2024-11-01T14:23:19Z) - Achieving Constant Regret in Linear Markov Decision Processes [57.34287648914407]
我々は不特定線形マルコフ決定過程(MDP)に対するアルゴリズムCert-LSVI-UCBを導入する。
Cert-LSVI-UCB は $tildemathcalO(d3H5/Delta)$ の累積後悔を高い確率で示し、不特定度 $zeta$ が $tildemathcalO(Delta / (sqrtdH2))$ 以下であることを示す。
論文 参考訳（メタデータ） (2024-04-16T17:23:19Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。