論文の概要: Randomized Gradient Descents on Riemannian Manifolds: Almost Sure Convergence to Global Minima in and beyond Quantum Optimization

• arxiv url: http://arxiv.org/abs/2405.12039v2
• Date: Fri, 04 Jul 2025 11:36:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 17:51:39.210727
• Title: Randomized Gradient Descents on Riemannian Manifolds: Almost Sure Convergence to Global Minima in and beyond Quantum Optimization
• Title（参考訳）: リーマン多様体上のランダム化グラディエント線:量子最適化における大域最小値へのほぼ確実に収束
• Authors: Emanuel Malvetti, Christian Arenz, Gunther Dirr, Thomas Schulte-Herbrüggen,
• Abstract要約: 我々は,サドル点が存在するにもかかわらず,ランダム化勾配降下法が一局所最適化にほぼ確実に収束することを証明した。 主要な応用として、一元群上の量子最適化による基底状態の準備を考える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze convergence of gradient-descent methods on Riemannian manifolds. In particular, we study randomization of Riemannian gradient algorithms for minimizing smooth cost functions (of Morse-Bott type). We prove that randomized gradient descent methods, where the Riemannian gradient is replaced by a random projection of it, converge to a single local optimum almost surely despite the existence of saddle points. We consider both uniformly distributed and discrete random projections. We also discuss the time required to pass a saddle point. As a major application, we consider ground-state preparation through quantum optimization over the unitary group. In mathematical terms our randomized algorithm applied to the trace function $U \to \operatorname{tr}(AU\rho U^*)$ almost surely converges to its global minimum. The minimum corresponds to the smallest eigenvalue (ground state) of the selfadjoint operator $A$ (Hamiltonian) if $\rho$ is a rank-one projector (pure state). In this setting, one can efficiently replace the uniform random projections by implementing so-called discrete unitary 2-designs.
• Abstract（参考訳）: リーマン多様体上の勾配差分法の収束を解析する。 特に,(モースボット型の)スムーズなコスト関数を最小化するためのリーマン勾配アルゴリズムのランダム化について検討する。 リーマン勾配をランダムな射影に置き換えたランダムな勾配降下法は、サドル点が存在するにもかかわらず、ほぼ確実に1つの局所最適点に収束する。 我々は一様分布と離散乱射影の両方を考える。 また、サドルポイントを通過するのに必要な時間についても議論する。 主要な応用として、一元群上の量子最適化による基底状態の準備を考える。 数学的には、我々のランダム化アルゴリズムはトレース関数 $U \to \operatorname{tr}(AU\rho U^*)$ に適用され、ほぼ確実にその大域最小値に収束する。 最小値が自己随伴作用素 $A$ (Hamiltonian) の最小固有値(基底状態)に対応するのは、$\rho$ がランク1の射影子(純粋な状態)であるときである。 この設定では、いわゆる離散ユニタリな2-設計を実装することにより、均一なランダムなプロジェクションを効率的に置き換えることができる。

関連論文リスト

• Riemannian Bilevel Optimization [35.42472057648458]
  特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。 本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。 様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
  論文  参考訳（メタデータ） (2024-05-22T20:49:01Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms [19.99781875916751]
  textttZo-RASAは$epsilon$-approximation 1次定常解を生成するのに最適なサンプル複雑性を実現する。 指数写像や並列輸送の代わりに幾何とベクトル輸送を用いることで,アルゴリズムの実用性を向上させる。
  論文  参考訳（メタデータ） (2023-09-25T20:13:36Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization [15.78743548731191]
  多様体非線型性の非線型性の難しさを克服するために、ガウス滑らか化関数のオラクル版を提案する。 ニューラルネットワークに対するロボティクスとブラックボックス攻撃に対するブラックボックス剛性制御における,結果によるアルゴリズムの適用性と実世界の応用を実証する。
  論文  参考訳（メタデータ） (2020-03-25T06:58:19Z)

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

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