論文の概要: 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$はエッジの数である。
関連論文リスト
- Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。
標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。
対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
論文 参考訳（メタデータ） (2026-02-14T13:09:29Z) - 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) - Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。