論文の概要: On the Local Linear Rate of Consensus on the Stiefel Manifold
- arxiv url: http://arxiv.org/abs/2101.09346v1
- Date: Fri, 22 Jan 2021 21:52:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-20 18:19:30.826777
- Title: On the Local Linear Rate of Consensus on the Stiefel Manifold
- Title(参考訳): スティフェル多様体上のコンセンサスの局所直線速度について
- Authors: Shixiang Chen, Alfredo Garcia, Mingyi Hong, Shahin Shahrampour
- Abstract要約: 我々は(連結でない問題に対して)シュティーフェル問題上のシュティーフェル勾配の性質の収束を制限する。
主な課題は、(i)分析のための技術を開発すること、(ii)常にローカルに留まっている状況(例えば、適切なステップサイズと、その下に常にローカルに留まっている状態)を特定することである。
- 参考スコア(独自算出の注目度): 39.750623187256735
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the convergence properties of Riemannian gradient method for solving
the consensus problem (for an undirected connected graph) over the Stiefel
manifold. The Stiefel manifold is a non-convex set and the standard notion of
averaging in the Euclidean space does not work for this problem. We propose
Distributed Riemannian Consensus on Stiefel Manifold (DRCS) and prove that it
enjoys a local linear convergence rate to global consensus. More importantly,
this local rate asymptotically scales with the second largest singular value of
the communication matrix, which is on par with the well-known rate in the
Euclidean space. To the best of our knowledge, this is the first work showing
the equality of the two rates. The main technical challenges include (i)
developing a Riemannian restricted secant inequality for convergence analysis,
and (ii) to identify the conditions (e.g., suitable step-size and
initialization) under which the algorithm always stays in the local region.
- Abstract(参考訳): リーマン勾配法の収束特性を調べ、スティフェル多様体上のコンセンサス問題(非有向連結グラフ)を解く。
スティーフェル多様体は非凸集合であり、ユークリッド空間における平均化の標準概念はこの問題には効かない。
stiefel manifold (drcs) 上の分散リーマン的コンセンサスを提案し,大域的コンセンサスに対して局所線形収束率を享受することを示す。
さらに重要なことに、この局所速度は、ユークリッド空間のよく知られた速度と同等の、通信行列の第二の最大の特異値と漸近的にスケールする。
私たちの知る限りでは、これは2つのレートの平等を示す最初の作品です。
主な技術的課題は、(i)収束解析のためのリーマン制限された離散不等式の開発、(ii)アルゴリズムが常に局所領域に留まっている条件(例えば、適切なステップサイズと初期化)を特定することである。
関連論文リスト
- Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [115.64182929032334]
そこで本稿では,制約のないmin-max問題の大域的サドル点を求めるために,正確にかつ不正確なニュートン型手法を提案し,解析する。
1次法と比較して、min-maxの2次法の研究は比較的限られている。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Riemannian Natural Gradient Methods [21.14740680011498]
本稿では, 自然勾配法の自然な拡張と見なすことができる, 多様体設定におけるフィッシャー情報行列の概念を紹介する。
提案手法のほぼ完全な大域収束を標準仮定の下で確立する。
機械学習による応用に関する数値実験は、最先端の手法よりも提案手法の利点を実証している。
論文 参考訳(メタデータ) (2022-07-15T04:33:10Z) - Convergence of the Riemannian Langevin Algorithm [10.279748604797911]
計量$g$の多様体上の自然測度に関して、密度$nu$の分布からサンプリングする問題を研究する。
対数障壁によって定義されるポリトープに制限された等尺的密度をサンプリングする手法が,本手法の特例である。
論文 参考訳(メタデータ) (2022-04-22T16:56:00Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Averaging on the Bures-Wasserstein manifold: dimension-free convergence
of gradient descent [2.9631016562930546]
我々は,新たな測地的凸性の結果を証明し,イテレートのより強力な制御,自由収束を実現した。
また, この手法により, 平均化の概念, エントロピック規則化バリセンタ, 幾何中央値の2つの解析が可能となった。
論文 参考訳(メタデータ) (2021-06-16T01:05:19Z) - Decentralized Riemannian Gradient Descent on the Stiefel Manifold [39.750623187256735]
エージェントのネットワークがStiefel多様体上のグローバル関数を最小化することを目的としている分散非センシアン最適化を考える。
一定の使用条件を満たすために、Stiefel多様体のための分散勾配(DRA)も提案する。
論文 参考訳(メタデータ) (2021-02-14T07:30:23Z) - Global Riemannian Acceleration in Hyperbolic and Spherical Spaces [0.0]
第1次大域一階法によるユークリッド曲率の加速現象の研究
第一次方法は、加速勾配降下と同じ速度をユークリッド勾配で達成する。
論文 参考訳(メタデータ) (2020-12-07T12:09:30Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳(メタデータ) (2020-06-06T19:08:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。