論文の概要: NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization

• arxiv url: http://arxiv.org/abs/2604.07372v1
• Date: Tue, 07 Apr 2026 14:40:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-10 18:34:05.424121
• Title: NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization
• Title（参考訳）: NS-RGS:Newton-Schulzに基づく直交群同期のためのリーマン勾配法
• Authors: Haiyang Peng, Deren Han, Xin Chen, Meng Huang,
• Abstract要約: グループ同期は、一対の測定からグループ要素の回復に関わる基本的なタスクである。 グループ同期のための NS-Schulz-based Gradientian Scheme (NS-RGS) は計算コストを大幅に削減する。
• 参考スコア（独自算出の注目度）: 5.9328204956514945
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Group synchronization is a fundamental task involving the recovery of group elements from pairwise measurements. For orthogonal group synchronization, the most common approach reformulates the problem as a constrained nonconvex optimization and solves it using projection-based methods, such as the generalized power method. However, these methods rely on exact SVD or QR decompositions in each iteration, which are computationally expensive and become a bottleneck for large-scale problems. In this paper, we propose a Newton-Schulz-based Riemannian Gradient Scheme (NS-RGS) for orthogonal group synchronization that significantly reduces computational cost by replacing the SVD or QR step with the Newton-Schulz iteration. This approach leverages efficient matrix multiplications and aligns perfectly with modern GPU/TPU architectures. By employing a refined leave-one-out analysis, we overcome the challenge arising from statistical dependencies, and establish that NS-RGS with spectral initialization achieves linear convergence to the target solution up to near-optimal statistical noise levels. Experiments on synthetic data and real-world global alignment tasks demonstrate that NS-RGS attains accuracy comparable to state-of-the-art methods such as the generalized power method, while achieving nearly a 2$\times$ speedup.
• Abstract（参考訳）: グループ同期は、一対の測定からグループ要素の回復に関わる基本的なタスクである。 直交群同期について、最も一般的なアプローチは、問題を制約付き非凸最適化として再定義し、一般化パワー法のような射影的手法を用いて解決する。 しかし、これらの手法は各イテレーションにおける正確なSVDやQR分解に依存しており、計算コストがかかり、大規模問題のボトルネックとなっている。 本稿では,Newton-Schulz をベースとした直交群同期のための Remannian Gradient Scheme (NS-RGS) を提案する。 このアプローチは効率的な行列乗法を活用し、最新のGPU/TPUアーキテクチャと完全に整合する。 統計的依存性から生じる課題を克服し,スペクトル初期化によるNS-RGSが最適に近い統計雑音レベルまで対象解に線形収束することを示す。 合成データと実世界のグローバルアライメントタスクの実験は、NS-RGSが2$\times$のスピードアップを達成しつつ、一般化電力法のような最先端の手法に匹敵する精度を得ることを示した。

関連論文リスト

• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  本稿では,並列計算の理論的下界を実現する最初の非同期アルゴリズムであるリングリーダーASGDを紹介する。 我々の分析により、リングリーダーASGDは任意の勾配と時間変化速度の下で最適であることが明らかとなった。
  論文  参考訳（メタデータ） (2025-09-26T19:19:15Z)
• qNBO: quasi-Newton Meets Bilevel Optimization [26.0555315825777]
  階層的な学習タスクにおける課題に対処するバイレベル最適化は、機械学習に大きな関心を集めている。 我々はこれらの計算課題に協調的に対処するための一般的な枠組みを導入する。 具体的には、準ニュートンアルゴリズムを利用して、逆ヘッセンベクトル積を効率的に近似しながら、下層問題の解法を高速化する。
  論文  参考訳（メタデータ） (2025-02-03T05:36:45Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  不均一な環境で分散SGDのための非同期型アルゴリズムを解析する。 また,本分析の副産物として,ランダムなきついSGDのような勾配型アルゴリズムの保証を示す。
  論文  参考訳（メタデータ） (2023-10-31T13:44:53Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  2つの重要な要素に依存した、新しく、堅牢で、加速された反復を提案する。 NAG-GSと呼ばれる手法の収束と安定性は、まず広範に研究されている。 我々は、NAG-arityが、重量減衰を伴う運動量SGDや機械学習モデルのトレーニングのためのAdamWといった最先端の手法と競合していることを示す。
  論文  参考訳（メタデータ） (2022-09-29T16:54:53Z)
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization [20.413250472034143]
  我々は、スペクトル分解ステップとブロックワイドカラムピボットQR因子分解(CPQR)からなる単純なアルゴリズムを提案する。 提案アルゴリズムは効率的で,データ点数に応じて線形にスケールする。 また、最近開発されたLeft-one-out技術を利用して、クラスタメンバシップの正確なリカバリをほぼ最適に保証する。
  論文  参考訳（メタデータ） (2021-12-25T07:38:14Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• On Newton Screening [14.040371216692645]
  我々はNewton Screening (NS) と呼ばれる新しいスクリーニング手法を開発した。 NSは、一段階局所収束を達成するという意味で、最適収束特性を有することを示す。
  論文  参考訳（メタデータ） (2020-01-27T11:25:33Z)

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

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