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

• arxiv url: http://arxiv.org/abs/2405.12039v1
• Date: Mon, 20 May 2024 14:06:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-21 13:05:04.725712
• 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要約: 本研究では,スムーズなコスト関数の最小化を目的とした勾配流の接空間方向のランダム化について検討する。 我々は,サドル点が存在するにもかかわらず,局所最適点への収束がほぼ確実に得られることを証明した。 簡単な2次元設定でサドル点を通過させるのに必要な時間について論じる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the convergence properties of gradient descent algorithms on Riemannian manifolds. We study randomization of the tangent space directions of Riemannian gradient flows for minimizing smooth cost functions (of Morse--Bott type) to obtain convergence to local optima. We prove that through randomly projecting Riemannian gradients according to the Haar measure, convergence to local optima can be obtained almost surely despite the existence of saddle points. As an application we consider ground state preparation through quantum optimization over the unitary group. In this setting one can efficiently approximate the Haar-random projections by implementing unitary 2-designs on quantum computers. We prove that the respective algorithm almost surely converges to the global minimum that corresponds to the ground state of a desired Hamiltonian. Finally, we discuss the time required by the algorithm to pass a saddle point in a simple two-dimensional setting.
• Abstract（参考訳）: リーマン多様体上の勾配降下アルゴリズムの収束特性を解析する。 モース・ボット型(Morse-Bott型)のスムーズなコスト関数を最小化するために,リーマン勾配流の接空間方向のランダム化を検討した。 ハール測度に従ってリーマン勾配をランダムに射影することにより、サドル点が存在するにもかかわらず、局所最適への収束はほぼ確実に得られることを証明した。 応用として、一元群上の量子最適化による基底状態の準備を考える。 この設定では、量子コンピュータにユニタリ2設計を実装することで、ハールランダム射影を効率的に近似することができる。 それぞれのアルゴリズムが、所望のハミルトニアン基底状態に対応する大域最小値にほぼ確実に収束していることを証明する。 最後に,簡単な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)

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

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