論文の概要: Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization

• arxiv url: http://arxiv.org/abs/2504.03626v1
• Date: Fri, 04 Apr 2025 17:44:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-07 14:48:50.397321
• Title: Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization
• Title（参考訳）: マルコフ連鎖モンテカルロ法の量子スピードアップと最適化への応用
• Authors: Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, Chunhao Wang,
• Abstract要約: 我々はマルコフ・チェイン・モンテカルロ法に対する証明可能な高速化を提供する量子アルゴリズムを提案する。 勾配推定のための新しい手法を導入することにより,従来のサンプリング器の複雑さが向上する。
• 参考スコア（独自算出の注目度）: 12.054017903540194
• License:
• Abstract: We propose quantum algorithms that provide provable speedups for Markov Chain Monte Carlo (MCMC) methods commonly used for sampling from probability distributions of the form $\pi \propto e^{-f}$, where $f$ is a potential function. Our first approach considers Gibbs sampling for finite-sum potentials in the stochastic setting, employing an oracle that provides gradients of individual functions. In the second setting, we consider access only to a stochastic evaluation oracle, allowing simultaneous queries at two points of the potential function under the same stochastic parameter. By introducing novel techniques for stochastic gradient estimation, our algorithms improve the gradient and evaluation complexities of classical samplers, such as Hamiltonian Monte Carlo (HMC) and Langevin Monte Carlo (LMC) in terms of dimension, precision, and other problem-dependent parameters. Furthermore, we achieve quantum speedups in optimization, particularly for minimizing non-smooth and approximately convex functions that commonly appear in empirical risk minimization problems.
• Abstract（参考訳）: 我々は,マルコフ・チェイン・モンテカルロ法(MCMC)の証明可能な高速化を実現する量子アルゴリズムを提案し,確率分布を$\pi \propto e^{-f}$の形でサンプリングする。 最初のアプローチでは、個々の関数の勾配を与えるオラクルを用いて、確率的設定における有限サムポテンシャルのギブズサンプリングを考える。 2つ目の設定では、確率的評価オラクルにのみアクセスすることを検討し、同じ確率的パラメータの下でポテンシャル関数の2点での同時クエリを可能にする。 確率勾配推定の新しい手法を導入することで,ハミルトン・モンテ・カルロ (HMC) やランゲヴィン・モンテ・カルロ (LMC) といった古典的なサンプルの勾配と評価の複雑さを次元,精度,その他の問題に依存したパラメータで改善する。 さらに、特に、経験的リスク最小化問題によく現れる非滑らかで概凸関数を最小化するために、最適化において量子スピードアップを実現する。

関連論文リスト

• Non-linear Quantum Monte Carlo [1.237454174824584]
  量子コンピューティングは、平均推定のための古典モンテカルロ法よりも2次的なスピードアップを提供する。 本研究では,非線形推定問題の幅広いクラスに対して,そのような高速化を実現する量子インサイド量子モンテカルロアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-07T17:13:27Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Quantum speedups for stochastic optimization [18.32349609443295]
  オラクルに対する量子振動の連続関数を最小化する問題を考察する。 リプシュ・アヴィッツ関数を最小化するための2つの新しい方法を提案する。
  論文  参考訳（メタデータ） (2023-08-03T07:39:10Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
  非滑らかなポテンシャルからのサンプリングのための新しいMCMCアルゴリズムを提案する。 本手法は, 近似バンドル法と交互サンプリングフレームワークに基づく。 この研究の重要な貢献は、任意の凸非滑らかポテンシャルに対して制限されたガウスオラクルを実現する高速アルゴリズムである。
  論文  参考訳（メタデータ） (2021-10-09T15:26:07Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Minibatch and Momentum Model-based Methods for Stochastic Non-smooth Non-convex Optimization [3.4809730725241597]
  モデルベース手法に対する2つの重要な拡張を行う。 まず,各イテレーションのモデル関数を近似するために,サンプルの集合を用いる新しいミニバッチを提案する。 第二に、運動量法の成功により、新しい凸モデルを提案する。
  論文  参考訳（メタデータ） (2021-06-06T05:31:57Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Marginalised Gaussian Processes with Nested Sampling [10.495114898741203]
  ガウス過程(GP)モデルは、カーネル関数によって制御される帰納バイアスを持つ関数上の豊富な分布である。 本研究は,Nested Smpling (NS) を用いてカーネル関数のハイパーパラメータを疎外する学習手法を提案する。
  論文  参考訳（メタデータ） (2020-10-30T16:04:35Z)
• 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)

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

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