論文の概要: Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
- arxiv url: http://arxiv.org/abs/2607.25492v2
- Date: Thu, 30 Jul 2026 02:31:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-31 12:52:12.261627
- Title: Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
- Title（参考訳）: 重音を用いた確率最適化のための量子スピードアップ
- Abstract要約: 重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
- 参考スコア（独自算出の注目度）: 49.730496294398726
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension $d$ of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index $p>4/3$, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method ($\texttt{QNSGD}$), which finds an $ε$-stationary point using $\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)$ queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method ($\texttt{QPSGD}$), which computes a solution with $ε$-optimal solution using $\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)$ queries in expectation. These sharper bounds improve upon the classical lower bounds $Ω\big(ε^{-\frac{3p-2}{p-1}}\big)$ for nonconvex problems and $Ω\big(ε^{-\frac{p}{p-1}}\big)$ for convex problems in the low-dimensional regimes $d\lesssimε^{-\frac{p}{p-1}}$ and $d\lesssimε^{-\frac{2-p}{p-1}}$, respectively.
- Abstract（参考訳）: 重み付き勾配雑音を用いた確率最適化について検討する。
まず,多変量重み付き確率変数に対する新しい量子平均推定器を提案する。
我々はさらに、一般化されたマルチレベルモンテカルロ法を適用して、非バイアス量子平均推定器を開発する。
我々は、ランダムベクトルの次元$d$が小さく、定数と見なせる場合、量子推定器は対数因子まで最適であることを示す量子下界を証明した。
さらに、尾指数 $p>4/3$ に対してより強い次元依存下界を導出し、この次元への非自明な依存が低次元状態において避けられないことを示す。
これらの推定値に基づいて量子正規化確率勾配降下法(\texttt{QNSGD}$)を提案し、量子確率勾配オラクルへのクエリに対して$\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)を用いてε$-定常点を求める。
凸目的関数に対しては、$\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)$クエリを期待して解を求める量子射影確率勾配降下法(\textt{QPSGD}$)を提案する。
これらのシャープな境界は、古典的な下界の$Ω\big(ε^{-\frac{3p-2}{p-1}}\big)$ と $Ω\big(ε^{-\frac{p}{p-1}}\big)$ 低次元のレジームにおける凸問題に対して$d\lesssimε^{-\frac{p}{p-1}}$ と$d\lesssimε^{-\frac{2-p}{p-1}}$ でそれぞれ改善される。
関連論文リスト
- Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise [27.792016944321627]
本稿では、目的関数がリプシッツ連続である非滑らかな問題を考察する。
本稿では,提案アルゴリズムのオンライン応用の枠組みを洗練することを提案する。
提案手法の有効性を示す数値実験を行った。
論文 参考訳（メタデータ） (2026-05-23T10:55:34Z) - Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
量子ビット効率の最適化を幾何学的問題として再検討する。
局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
論文 参考訳（メタデータ） (2025-11-11T15:38:57Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions [8.495749905129278]
非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。
最初の設定について、Omegabig(frac-1+ppp)$。
第二設定については、おめがの()$。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
論文 参考訳（メタデータ） (2022-12-07T19:02:36Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。