論文の概要: On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
- arxiv url: http://arxiv.org/abs/2604.03787v1
- Date: Sat, 04 Apr 2026 16:24:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-07 15:49:18.770452
- Title: On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
- Title（参考訳）: エントロピック規則化最適輸送におけるシンクホーン・ノックの有効性について
- Authors: Kun He,
- Abstract要約: Sinkhorn-Knoppアルゴリズムは、行列スケーリングと最適輸送のための基礎的手法である。
本稿では,局所的なバルク質量特性である well-boundedness の概念を紹介する。
事実上コストのない事前スケーリングのステップは、次元依存を完全に排除することを示す。
- 参考スコア（独自算出の注目度）: 10.787490135016155
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Sinkhorn--Knopp (SK) algorithm is a cornerstone method for matrix scaling and entropically regularized optimal transport (EOT). Despite its empirical efficiency, existing theoretical guarantees to achieve a target marginal accuracy $\varepsilon$ deteriorate severely in the presence of outliers, bottlenecked either by the global maximum regularized cost $η\|C\|_\infty$ (where $η$ is the regularization parameter and $C$ the cost matrix) or the matrix's minimum-to-maximum entry ratio $ν$. This creates a fundamental disconnect between theory and practice. In this paper, we resolve this discrepancy. For EOT, we introduce the novel concept of well-boundedness, a local bulk mass property that rigorously isolates the well-behaved portion of the data from extreme outliers. We prove that governed by this fundamental notion, SK recovers the target transport plan for a problem of dimension $n$ in $O(\log n - \log \varepsilon)$ iterations, completely independent of the regularized cost $η\|C\|_\infty$. Furthermore, we show that a virtually cost-free pre-scaling step eliminates the dimensional dependence entirely, accelerating convergence to a strictly dimension-free $O(\log(1/\varepsilon))$ iterations. Beyond EOT, we establish a sharp phase transition for general $(\boldsymbol{u},\boldsymbol{v})$-scaling governed by a critical matrix density threshold. We prove that when a matrix's density exceeds this threshold, the iteration complexity is strictly independent of $ν$. Conversely, when the density falls below this threshold, the dependence on $ν$ becomes unavoidable; in this sub-critical regime, we construct instances where SK requires $Ω(n/\varepsilon)$ iterations.
- Abstract（参考訳）: Sinkhorn-Knopp (SK) アルゴリズムは、行列スケーリングとエントロピカルに正規化された最適輸送(EOT)のための基礎的手法である。
その経験的効率にもかかわらず、既存の理論的な保証により、目標の限界精度を達成できる$\varepsilon$は、大域的な最大正規化コスト$η\|C\|_\infty$(ここで$η$は正規化パラメータ、$C$はコスト行列)か、行列の最小最大エントリー比$ν$によってボトルネックとなる。
これは理論と実践を根本的に切り離す。
本稿では,この相違を解消する。
EOTでは, 局所的なバルク質量特性である well-boundedness という新しい概念を導入し, 異常値からデータの一部を厳密に分離する。
我々は、この基本的な概念によって支配されるSKが、正規化コスト$η\|C\|_\infty$から完全に独立な、次元$n$ in $O(\log n - \log \varepsilon)$イテレーションのターゲット輸送計画を取り戻すことを証明している。
さらに、実質的にコストのない事前スケーリングステップは次元依存を完全に排除し、厳密な次元のない$O(\log(1/\varepsilon))$反復への収束を加速することを示す。
EOT以外にも、臨界行列密度閾値によって支配される一般$(\boldsymbol{u},\boldsymbol{v})$-scalingに対して鋭い位相遷移を確立する。
行列の密度がこのしきい値を超えるとき、反復複雑性は$ν$から厳密に独立であることを示す。
逆に、密度がこのしきい値を下回ると、$ν$への依存は避けられなくなり、この亜臨界状態において、SKが$Ω(n/\varepsilon)$反復を必要とするインスタンスを構築する。
関連論文リスト
- Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳（メタデータ） (2026-02-19T17:21:15Z) - Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$ [7.884611719110979]
グラディエント・Descent (SGD) は、現代のデータ科学における基礎的な手法となっている。
本研究では,オンライン最小二乗 SGD の線型汎函数に対して,非漸近的ベリー-エッセイン境界を確立する。
論文 参考訳（メタデータ） (2025-10-22T16:25:49Z) - Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。
このような悪条件下でSGDが確実に成功できるかどうかを精査する。
論文 参考訳（メタデータ） (2025-08-06T20:09:41Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。
本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。
1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
論文 参考訳（メタデータ） (2021-10-13T17:50:46Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳（メタデータ） (2021-03-01T19:48:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。