論文の概要: Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

• arxiv url: http://arxiv.org/abs/2608.11760v2
• Date: Thu, 13 Aug 2026 02:05:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-14 14:00:09.799114
• Title: Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
• Title（参考訳）: Sinkhorn-Knopp の高度無症候性局所収束
• Authors: Wenzhi Gao, Zhaonan Qu, Yinyu Ye, Madeleine Udell,
• Abstract要約: Sinkhorn-Knoppアルゴリズムを行列スケーリング問題のために再検討する。 ある条件下では、SKは2倍の行列スケーリングのための収束時間アルゴリズムであることを示す。
• 参考スコア（独自算出の注目度）: 21.37855446714896
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We show that under certain connectivity conditions, SK is a polynomial-time algorithm for doubly stochastic matrix scaling. With the developed tools, we showcase the local suboptimality of SK and provide accelerated variants. Finally, for dense matrices, we improve the complexity of existing first-order matrix scaling algorithms from $O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})$ to $O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})$.
• Abstract（参考訳）: Sinkhorn-Knopp (SK) アルゴリズムを行列スケーリング問題に対して再検討する。 SKとその変種の大域収束に関する広範な文献にもかかわらず、その局所収束挙動はいまだに理解されていない。 我々は、既存の漸近的ヤコビアンベースの議論から得られる率と一致するSKの最初の漸近的局所解析を提供することにより、このギャップに対処する。 ある種の接続条件下では、SKは2倍確率行列スケーリングのための多項式時間アルゴリズムであることを示す。 開発したツールを用いて,SKの局所的部分最適性を示し,高速化された変種を提供する。 最後に、高密度行列に対しては、既存の一階行列スケーリングアルゴリズムの複雑さを$O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})$から$O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})$へと改善する。

関連論文リスト

• Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
  本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。 SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
  論文  参考訳（メタデータ） (2024-01-20T21:23:09Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties [8.294148737585543]
  本稿では,非二次絶対および非平滑収束ペナルティの存在下での凹凸および切断された量子レグレッションについて検討する。 本稿では,スパース回帰に特化してSIADと呼ばれるペナルティ乗算器が増加する新しいループADMアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-04T21:48:51Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。