論文の概要: Robustness of Quantum Algorithms for Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2212.02548v1
- Date: Mon, 5 Dec 2022 19:10:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 20:19:11.114509
- Title: Robustness of Quantum Algorithms for Nonconvex Optimization
- Title（参考訳）: 非凸最適化のための量子アルゴリズムのロバスト性
- Authors: Weiyuan Gong, Chenyi Zhang, Tongyang Li
- Abstract要約: 量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
- 参考スコア（独自算出の注目度）: 7.191453718557392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent results suggest that quantum computers possess the potential to speed
up nonconvex optimization problems. However, a crucial factor for the
implementation of quantum optimization algorithms is their robustness against
experimental and statistical noises. In this paper, we systematically study
quantum algorithms for finding an $\epsilon$-approximate second-order
stationary point ($\epsilon$-SOSP) of a $d$-dimensional nonconvex function, a
fundamental problem in nonconvex optimization, with noisy zeroth- or
first-order oracles as inputs. We first prove that, up to noise of
$O(\epsilon^{10}/d^5)$, accelerated perturbed gradient descent with quantum
gradient estimation takes $O(\log d/\epsilon^{1.75})$ quantum queries to find
an $\epsilon$-SOSP. We then prove that perturbed gradient descent is robust to
the noise of $O(\epsilon^6/d^4)$ and $O(\epsilon/d^{0.5+\zeta})$ for $\zeta>0$
on the zeroth- and first-order oracles, respectively, which provides a quantum
algorithm with poly-logarithmic query complexity. We then propose a stochastic
gradient descent algorithm using quantum mean estimation on the Gaussian
smoothing of noisy oracles, which is robust to $O(\epsilon^{1.5}/d)$ and
$O(\epsilon/\sqrt{d})$ noise on the zeroth- and first-order oracles,
respectively. The quantum algorithm takes $O(d^{2.5}/\epsilon^{3.5})$ and
$O(d^2/\epsilon^3)$ queries to the two oracles, giving a polynomial speedup
over the classical counterparts. Moreover, we characterize the domains where
quantum algorithms can find an $\epsilon$-SOSP with poly-logarithmic,
polynomial, or exponential number of queries in $d$, or the problem is
information-theoretically unsolvable even by an infinite number of queries. In
addition, we prove an $\Omega(\epsilon^{-12/7})$ lower bound in $\epsilon$ for
any randomized classical and quantum algorithm to find an $\epsilon$-SOSP using
either noisy zeroth- or first-order oracles.
- Abstract（参考訳）: 最近の結果は、量子コンピュータが非凸最適化問題を高速化する可能性を示唆している。
しかし、量子最適化アルゴリズムの実装において重要な要素は、実験的および統計的ノイズに対する堅牢性である。
本稿では,非凸最適化の基本問題であるd$-dimensional nonconvex関数の2次定常点(\epsilon$-sosp)を入力として,ノイズゼロまたは1次オラクルを入力として,量子アルゴリズムを体系的に研究する。
我々はまず、$O(\epsilon^{10}/d^5)$の雑音に対して、量子勾配推定による摂動勾配の加速は$O(\log d/\epsilon^{1.75})$の量子クエリを$\epsilon$-SOSPを求める。
次に,摂動勾配降下は,0次および1次オラクルにおいて$o(\epsilon^6/d^4)$と$o(\epsilon/d^{0.5+\zeta})$が$\zeta>0$の雑音に対して頑健であることを証明する。
次に,0次および1次オラクルでは,それぞれ$o(\epsilon^{1.5}/d)$と$o(\epsilon/\sqrt{d})$にロバストであるガウス平滑化の量子平均推定を用いた確率的勾配降下アルゴリズムを提案する。
量子アルゴリズムは、$O(d^{2.5}/\epsilon^{3.5})$と$O(d^2/\epsilon^3)$のクエリを2つのオラクルに受け取り、古典的なアルゴリズムよりも多項式の高速化を与える。
さらに、量子アルゴリズムが多対数、多項式、指数的なクエリ数を持つ$\epsilon$-SOSPを$d$で見つけることができる領域を特徴づける。
さらに、任意のランダム化された古典的および量子的アルゴリズムに対して、$\Omega(\epsilon^{-12/7})$ lower bound in $\epsilon$を証明し、ノイズの多いゼロトまたは1次オラクルを用いて$\epsilon$-SOSPを求める。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
論文 参考訳（メタデータ） (2024-02-20T06:23:36Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。