論文の概要: Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size
- arxiv url: http://arxiv.org/abs/2609.03762v1
- Date: Thu, 03 Sep 2026 12:29:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-04 18:28:39.056347
- Title: Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size
- Title（参考訳）: Bures-Wasserstein 境界中心に対するリーマン勾配の投射:単位ステップサイズにおける次元に依存しない線形収束
- Abstract要約: 本稿では,単位次元ステップサイズで次元非依存の線形収束を実現する計画RGDアルゴリズムを提案する。
The crux is a novel small-step guarantee(3/2$対5/2$ complexity)
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, $(1 - κ^{-3/2})$, where $κ$ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee ($κ^{3/2}$ versus $κ^{5/2}$ iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval $[α, β]$ is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set $\{S : αI \leq S \leq βI\}$ -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.
- Abstract（参考訳）: 正定行列のアンサンブルのビュール=ヴァッサーシュタイン(BW)バリセンタの計算は、機械学習、最適輸送、量子情報を通じて行われる。
単位ステップの勾配勾配勾配(RGD)は、実際は固定点反復である単位ステップサイズで急速に収束するが、既存の分析では二分法が示される: 単位ステップの保証は、その次元に対する最悪のケースの指数関数的依存を持ち、次元に依存しない保証は、経験的な速度を妨げる小さなステップサイズを必要とする。
この二分法は、単位ステップRGDの保証を改善するのではなく、単位ステップサイズで次元に依存しない線形収束を実現する投影されたRGDアルゴリズムを提案することで解決する。
1 - κ^{-3/2})$、$κ$はアンサンブルの条件数であり、最高の小ステップ保証(κ^{3/2}$対$κ^{5/2}$反復複雑性)を多項式的に改善する。
正行列の固有値を区間 $[α, β]$ に切断することは、集合 $\{S : αI \leq S \leq βI\}$ 上の閉形式で非拡張的 (1-Lipschitz) BW-メトリック射影である。
プロジェクションはより自由で、次のイテレーションで実行しなければならない固有分解を再利用するので、プロジェクションと未計画のイテレーションはステップ毎に同じコストがかかります。
同じ分析はBrahmachari et al (2025) の不変行列射影問題(英語版)(invariant matrix projection problem)をカバーしている。
関連論文リスト
- Scaling-Score Conformal Prediction for Multi-Target Regression [0.42970700836450476]
マルチターゲット回帰は、複数の関連する出力を同時に予測するモデルを必要とする。
モデルに依存しないスケーリングスコアコンフォメーション法(コンポーネント単位の絶対残差のみを要求する)を提案する。
論文 参考訳（メタデータ） (2026-09-15T12:23:57Z) - Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes [1.217503190366097]
有限水平マルコフ決定過程におけるNPG(Natural Policy Gradient)について検討する。
この設定において、このアルゴリズムに対する最初の有限時間収束保証を提供する。
我々は、この定数ステップサイズ解析を、正確な集団投影オラクルにおける線形MDPに拡張する。
論文 参考訳（メタデータ） (2026-07-25T01:37:26Z) - Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。
また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-23T02:30:01Z) - Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。
無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。
本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-02-11T21:44:20Z) - Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。
パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
論文 参考訳（メタデータ） (2025-10-06T10:53:37Z) - $k$-SVD with Gradient Descent [18.260910876411973]
任意の階数 $d geq 1$ の行列に対して、$k$-SVD を証明できるような、ステップサイズ選択のための単純で普遍的な規則を持つ勾配退化法を提案する。
我々の収束解析により、勾配法は魅力的な領域を持ち、この領域ではヘロン法のように振る舞う(バビロニア法)。
解析結果から,ネステロフの運動量に基づく加速度法により勾配法を拡張できることが示唆された。
論文 参考訳（メタデータ） (2025-02-01T05:00:28Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold [16.099883128428054]
直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
論文 参考訳（メタデータ） (2023-03-16T12:25:53Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Generalization Bounds for Stochastic Gradient Descent via Localized
$\varepsilon$-Covers [16.618918548497223]
本稿では,SGDの軌道に局在する新しい被覆手法を提案する。
このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。
これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
論文 参考訳（メタデータ） (2022-09-19T12:11:07Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。