論文の概要: Robust Sublinear Convergence Rates for Iterative Bregman Projections

• arxiv url: http://arxiv.org/abs/2602.01372v1
• Date: Sun, 01 Feb 2026 18:20:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:33.751071
• Title: Robust Sublinear Convergence Rates for Iterative Bregman Projections
• Title（参考訳）: 反復的ブレグマン射影に対するロバストサブ線形収束率
• Authors: Gabriel Peyré,
• Abstract要約: エントロピック正規化(entropic regularization)は、制約が2つ(またはそれ以上)のトラクタブルブロックに分割された線形プログラムに近似する。 グラフ上のWasserstein-1距離に対するフローシンクホーンアルゴリズムを導出する。
• 参考スコア（独自算出の注目度）: 21.689846521201588
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Entropic regularization provides a simple way to approximate linear programs whose constraints split into two (or more) tractable blocks. The resulting objectives are amenable to cyclic Kullback-Leibler (KL) Bregman projections, with the classical Sinkhorn algorithm for optimal transport (balanced, unbalanced, gradient flows, barycenters, \dots) as the canonical example. Assuming uniformly bounded primal mass and dual radius, we prove that the dual objective of these KL projections decreases at an $O(1/k)$ rate with a constant that scales only linearly in $1/γ$, where $γ$ is the entropic regularization parameter. This extends the guarantees known for entropic optimal transport to any such linearly constrained problem. Following the terminology introduced in [Chizat et al 2025], we call such rates "robust", because this mild dependence on $γ$ underpins favorable complexity bounds for approximating the unregularized problem via alternating KL projections. The crucial aspect of the analysis is that the dual radius should be measured according to a block-quotient dual seminorm, which depends on the structure of the split of the constraint into blocks. As an application, we derive the flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs. It achieves $ε$-additive accuracy on the transshipment cost in $O(p/ε^{4})$ arithmetic operations, where $p$ is the number of edges.
• Abstract（参考訳）: エントロピック正則化は、制約が2つ(またはそれ以上)のトラクタブルブロックに分割された線形プログラムを近似する簡単な方法を提供する。 結果として得られる目的は、周期的クルバック・リーブラー (KL) ブレグマン射影 (Bregman projections) であり、古典的なシンクホーンアルゴリズムは、標準例として最適な輸送(平衡、不均衡、勾配流、バリセンタ、ドート)を行う。 一様有界原始質量と双対半径を仮定すると、これらのKL射影の双対目的は1/γ$でのみ線形にスケールする定数を持つ$O(1/k)$レートで減少し、そこで$γ$はエントロピー正則化パラメータである。 これにより、そのような線形に制約された問題に対するエントロピー的最適輸送で知られている保証が拡張される。 例えば、[Chizat et al 2025] で導入された用語に従えば、そのようなレートは "robust" と呼ばれる。 解析の重要な側面は、双対半径はブロック商双対半ノルムに従って測定されるべきであり、これは制約のブロックへの分割の構造に依存する。 応用として、グラフ上のWasserstein-1距離に対するフローシンクホーンアルゴリズムを導出する。 これは、$O(p/ε^{4})$算術演算において、転送コストに対して$ε$-additiveの精度を達成し、$p$はエッジの数である。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Enforced Gaplessness from States with Exponentially Decaying Correlations [0.0]
  指数関数的に崩壊する相関でさえ、ギャップレス性を示唆することを示す。 我々の発見は、ギャップ化された基底状態が属するヒルベルト空間の部分集合を特定することに意味がある。
  論文  参考訳（メタデータ） (2025-03-03T19:00:37Z)
• Measurement-induced phase transition for free fermions above one dimension [46.176861415532095]
  自由フェルミオンモデルに対する$d>1$次元における測定誘起エンタングルメント相転移の理論を開発した。 臨界点は、粒子数と絡み合いエントロピーの第2累積のスケーリング$$elld-1 ln ell$でギャップのない位相を分離する。
  論文  参考訳（メタデータ） (2023-09-21T18:11:04Z)
• Theory of free fermions under random projective measurements [43.04146484262759]
  本研究では,一次元自由フェルミオンを局所的占有数のランダム射影的測定対象とする解析的手法を開発した。 問題の有効場理論として非線形シグマモデル(NLSM)を導出する。
  論文  参考訳（メタデータ） (2023-04-06T15:19:33Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Error Estimates for the Variational Training of Neural Networks with Boundary Penalty [0.0]
  空間$H1(Omega)$上の二次エネルギーに対するリッツ法による誤差の推定値を確立する。 境界ペナルティ法で処理されるディリクレ境界値に対しては,特に注意が払われる。
  論文  参考訳（メタデータ） (2021-03-01T13:55:59Z)
• Asymptotics of Entropy-Regularized Optimal Transport via Chaos Decomposition [1.7188280334580195]
  この論文は、離散的なシュル「オーディンガー橋」の性質を、N$が無限大の傾向にあるとして論じる。 最初の2つのエラー項は、それぞれ$N-1/2$と$N-1$を導出する。 1階と2階のカオスに対応するカーネルは、シンクホーンアルゴリズムの自然な解釈を持つマルコフ作用素によって与えられる。
  論文  参考訳（メタデータ） (2020-11-17T21:55:46Z)
• Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization [31.474280642125734]
  そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。 提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
  論文  参考訳（メタデータ） (2020-01-15T09:57:38Z)

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

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